Sereja and Subsegment Increasings
All submissions for this problem are available.
Read problems statements in Mandarin Chinese and Russian.
Sereja has an array A that contains n integers: A1, A2, ..., An. Sereja also has an array B that contains n integers B1, B2, ..., Bn. In a single step Sereja can choose two indexes i and j (1 <= i <= j <= n) , and increase all the elements of A with indices between i and j inclusively by one, modulo 4. In other words, we make Ap equal to (Ap + 1) modulo 4 if p is an integer from the range [i; j].
Now Sereja is interested in the following question: what is the mininal number of steps necessary in order to make the array A equal to the array B.
The first line contains an integer T - the number of the testcases. Then, T tests follow.
The first line of each testcase contains the integer n.
The next line conatins n single space separated integers - A1, A2, ..., An.
The next line conatin n single space separated integers - B1, B2, ..., Bn.
For each testcase output an answer - the mininal number of steps necessary.
- 1 ≤ T ≤ 10
- 1 ≤ n ≤ 105
- 0 ≤ Ai, Bi ≤ 3
Input: 1 5 2 1 3 0 3 2 2 0 1 0 Output: 1
|Tags||greedy, may14, medium-hard, sereja|
|Time Limit:||1 sec|
|Source Limit:||50000 Bytes|
|Languages:||ADA, ASM, BASH, BF, C, C99 strict, CAML, CLOJ, CLPS, CPP 4.3.2, CPP 6.3, CPP14, CS2, D, ERL, FORT, FS, GO, HASK, ICK, ICON, JAVA, JS, LISP clisp, LISP sbcl, LUA, NEM, NICE, NODEJS, PAS fpc, PAS gpc, PERL, PERL6, PHP, PIKE, PRLG, PYTH, PYTH 3.5, RUBY, SCALA, SCM guile, SCM qobi, ST, TCL, TEXT, WSPC|
Fetching successful submissions
If you are still having problems, see a sample solution here.