yes

and a - x.

Try looking yourself how they behave on some examples, like a = 3, a = 2 and some reasonable x's.

A claim is that (always) and equality holds if and only if bits of x form a subset of bits of a.

a^x = a + x — 2 * (a & x) [ XOR property]

So, a^x = a-x => a + x — 2 * (a & x) = a — x => a & x = x

So, this is true when we take any subset of ones (set bit) of 'a' => ans = (1 << (cnt of set bit in a))

Consider we are now at (i,j).If the problem doesn't have the limit about move left and right,It's just a simple bfs problem.

With limit,if one point can be reached by move (left,right) with many different ways, it is obviously that using less (left,right) move is optimal,because it maybe can reach more points.

So we can just use bfs to record the less (left,right) move.

See My Code 44337946

Just using simple bfs , move down or up with affect the order about move left and right

See this sample from ez_zh

Because the fastest way to reach some block from the starting block may exceed the left and right constraints.

Because there are two kinds of edges.(i.e. Which costs zero and which costs one).So when you are doing bfs, you need to insert a node in the front of the queue if its dist equals to the previous dist,and insert in the back if its dist equals to the previous dist plus one. You can also use dijkstra by heap optimize or Bellmen-ford by queue optimize. Sorry for My poor English.:)

That's div 2 C. You are a div 2 participant.

Some questions:

1. In definition of rem, did you mean k - r·num instead of k - r·sum?

2. Given that there may be someone with a sweet tooth in x, why the 4th inequation isn't 0 ≤ rem ≤ 2x?

3. What does the 5th inequation mean? I can't understand it.

Thanks in advance.

Since 'c' has x number of occurrences, thus palindrome with 'c' are x , palindrome which are 'cc' are x-1 , palindrome which are 'ccc' are x-2 and so on.

so we get x+x-1+....+2+1 = x(x+1)/2 for 'c' which has frequency x.

4 5 4 2 1 2 ...** .*... .***. .....
Correct ans: 10. Your bfs will reach 2,3 but not with minimum left or right moves. That's why simple bfs with all edge weights same won't work as moving more up and down is feasible rather than moving left or right.

Fixed it, thanks.

I think I have a proof for O(n). Assume that the dp is from left to right and dp[i] = length of the longest trip ending at i.

Let S(i) be the set of the smallest dp[j] substrings ending at j for each j from 1 to i. Let c1(i) be the number of distinct strings of the set S(i).

Call an index i type A if the second last string of the trip ending at [i-dp[i]+1, i] is equal to [i-dp[i]+1, i-1] and type B if it is [i-dp[i]+2, i].

It seems that c1(i) <= 2*i-dp[i+1]+O(1) (O(1) is some constant that I'm too lazy to find). We'll proceed by induction.

Case 1: i is type A and i+1 is type A

Since i+1 is type A, there is an occurrence of the string [i+1-dp[i+1]+1, i] before i+1-dp[i+1]+1. Thus, the substrings [i+1-dp[i+1]+1..i, i] do not contribute to c1(i), so c1(i) <= c1(i-1)+(i+1-dp[i+1]+1)-(i-dp[i]+1) <= 2*(i-1)-dp[i+1]+1+O(1).

Case 2: i is type A and i+1 is type B

Similar argument to Case 1, c1(i) <= 2*(i-1)-dp[i+1]+2+O(1).

Case 3: i is type B

Only [i-dp[i]+1, i] can be a new distinct string and dp[i+1]-1 <= dp[i], so c1(i) <= c2(i)+1+dp[i]-dp[i+1]+1 <= 2*(i-1)+2-dp[i+1]+O(1).

Actually we treat t as a constant, and a+b is parametric of z.

Now we just have to say the parametric

a = a0 + (t+1)z

b = b0 + tz, z is element of integers

is a line.

Solve for z = (a-a0)/(t+1) = (b-b0)/t

Since t, a0, b0 are constants this is actually just point-slope form of a line. (slopes are 1/(t+1) and 1/t)

let, describe each cell as a struct { row, col, leftCount, rightCount }

assume, you have a visited cell C and your current cell is CC;

where (CC.row == C.row) and (C.col == CC.col+1)

if(C.rightCount>(CC.rightCount + 1) || C.leftCount>CC.leftCount){

you have to call dfs with cell C again; 
   why?
  because, now C has lesser leftCount or rightCount than before....so it may 
           able to visit more cells than before

} here is my code with bfs https://mirror.codeforces.com/contest/1064/submission/44414320

I did the same to you.

You are supposed to give the interactor the position of point first, and then the interactor would tell you the color.

The way I like to think of it is trying all size "windows" on a single letter.

So imagine we have the string

a .... a .... a .... a where a's are evenly spaced out

In the optimal solution, the whole string is a palindrome and this satisfies the window of size 4. For example: abababa. Maximum there is 1 such window.

Now lets look at window of size 3. We need [a ... a ... a] to be a palindrome. There are maximum of 2 such windows.

Eventually we get 1+2+...cntA windows where cntA = amount of a's in the string.

Each letter should contribute 1+2+3...cnt = (cnt)(cnt+1)/2 palindromes in an optimal solution.

It is easy to see that a sorted string will always be optimal, because this property holds true. Actually any solution that "bunches" same letters together is optimal, so you can have ab O(n) solution (counting sort idea)

Handle the case where l or r hits negative (they are invalid)

You are doing a 0-1 BFS where each (i,j) is connected to up to 4 neighbors, with cost of vertical edges being 1 and cost of horizontal edges being 0. This means that at the end of the search, costTo[i][j] = numLeftsUsed+numRightsUsed.

Now since you are starting in column c and ending in column j, you must have numRightsUsed-numLeftsUsed = j-c. For instance if you start in column 1 and end in column 3, you might have used 0 lefts and 2 rights, or 1 lefts and 3 rights, or 2 lefts and 4 rights, etc.

This lets you solve for costTo[i][j] in terms of just numLeftsUsed or numRightsUsed:

numRightsUsed=j-c+numLeftsUsed so costTo[i][j] = numLeftsUsed + j — c + numLeftsUsed and similarly for expressing in terms of just numRightUsed.

Minimizing costTo[i][j] = numLeftsUsed+numRightsUsed = j-c+2*numLeftsUsed is equivalent to minimizing numLeftsUsed.