I'm not the one to decide the contest name, but, as I heard, it depends on the sponsor. Sometimes we have ARC sponsored by XXX, sometimes XXX contest.

Hey AnandOza do you make a solution video for this contest..?

We will think in DP.

First, we can know that, if the behavior of Snuke taking some candy doesn't affect Ant immediately, we can just delay it until it gives effect to Ant. So, if we want to take a candy far from Ant, we don't have to take it now, we will take it sometime later.

Now let's define the table as follows:

$$$DP[i][j][k]$$$: if candy 1~i and j~n remains, and we have k chances to take a candy, what will be the maximum score for Snuke?

Now we can calculate this easily.

Similar problem — D. Two Pirates — 2

I learnt very important lesson.

Case1 — $$$long[][][] dp=new\, long[n][m][3]$$$

Case2 — $$$long[][] dp1\,,dp2\,,dp3=new \,long[n][m]$$$
Case2 is much more efficient(3 times faster in my case) than Case1.(due to cach missing?) Ac_C

Can you explain your solution? It seems like its different from editorial's. I tried calculating number of ways dividing $$$t$$$ into $$$k$$$ segments, where each segment should fit in one period, multiplied by number of times to choose each of this segment in a period. "simple formula" from editorial wasn't so simple to me :(

By double counting on the number of pairs of people on the same team, we find that the number of games played is a multiple of $$$p-1$$$. Then we can construct a set of $$$p-1$$$ games that works using recursion (or using bitwise magic as described in the editorial).

solution fails with
7 6
0 0 0 1 1 5
Answer should be 5, yours gives 6

Maybe using a modular class or struct will help you. As you can treat it like type int (in c++) you probably won’t face problems like this anymore.

i think runtime error is due to the value of x becoming < 0 for some testcases.i submitted your code after changing x=cnt[i-1][j+1]-cnt[i-1][j] to x=max(0,cnt[i-1][j+1]-cnt[i-1][j]) and it passed.

As the author of the problem(CF1406A), I was pretty surprised when I saw problem B. I could have been the first accepted if my local laptop compiles a little bit faster...

Really liked the problems, but sadly I failed to solve D because my guess for the smallest K was wrong.

Suppose robot is present at position $$$(x,y)$$$.

If it moves toward $$$(x+1,y)$$$ then it would never travel cells in row $$$x$$$ from column $$$y+1$$$ to $$$w$$$ . Let say number of not assigned cells in segment $$$[x,y+1]$$$ to $$$[x,w]$$$ is $$$C$$$ . Then number of ways it can move toward $$$(x+1,y)$$$ from $$$(x,y)$$$ will be $$$ans[i][j]*3^C*T$$$.Where $$$T=2$$$ if $$$(x,y)$$$ not assigned any value,$$$T=1$$$ if it's 'D' or 'X' else $$$0$$$. $$$3^C$$$ because we can assign any value to the part which it doesn't travel.

Similar analogy if it's move toward $$$(x,y+1)$$$.

Thus it can be solved using 2 state DP with little pre-processing (Like powers of 3 , prefix sum matrices for row and column).

submission

See this

And, what is the meaning of $$$O(HW(H+W))$$$ ? Is $$$HW(x)$$$ some multiplication or what?

Let's say $$$dp[i][j][k]$$$ is no of ways to assign value in matrix $$$M_{i,j}$$$ such that $$$grid[i][j]=k$$$ and we can reach from $$$(1,1)$$$ to $$$(i,j)$$$ . If the current cell of grid i.e. $$$grid[i][j]$$$ has already assigned a value then the number of ways to construct new matrix i.e. $$$Z=dp[i][j][grid[i][j]] = (dp[i][j-1][R]+dp[i][j-1][X])*3^x+(dp[i-1][j][D]+dp[i-1][j][X])*3^y$$$. where $$$x$$$ is no of empty cell in the $$$i^th$$$ row with column value $$$< j$$$ and $$$y$$$ is no of empty cell in the $$$j^th$$$ column with row value $$$< i$$$. Now If $$$grid[i][j]$$$ has not already assigned a value then put the above value calculated in all three possible ways i.e. $$$dp[i][j][R]=dp[i][j][D]=dp[i][j][X]=Z$$$. My_Acc_sol
Note- It's different from the editorial because I have defined $$$dp$$$ in different way see here

Let us assume the robot is currently at position (i,j)
let val_right = number of paths from (i,j) to (h,w) if it moves right val_down = number of paths from (i,j) to (h,w) if it moves down

dp[i][j] = number of ways to move from (i,j) to (h,w)

val_right = dp[i][j+1]; if the robot moves towards right then it will never visit any cell below it in it's current column therefore all the cell in the current column below it which have not been assigned any character('R','D' or 'X') (lets call it empty cell) can take any of the 3 value and independent of those value robot will move towards it's destination. Therefore valright gets multiplied by 3^(number of empty cell in current column below the current cell)

val_down = dp[i+1][j]; similar to above logic val_down gets multiplied 3^(number of empty cells in current row to the right of current cell)

if(c[i][j]=='R') dp[i][j] = val_right else if(c[i][j]=='D') dp[i][j] =val_down else if(c[i][j]=='X') dp[i][j] =val_down+val_right else dp[i][j] = 2*(val_right+val_down) (because empty can be assigned either 'R' or 'D' or 'X')

Taking mod at appropriate positions and prestoring modulus of power of 3 (upto 5000)) will give AC

The idea I used was instead of finding number of paths for each 3^(HW-k) configurations , I counted for a valid path from (1,1) to (H,W) in how many configurations will it occur.

It is O(n^2), not O(n)

Try this.
15 12
13 7 7 0 11 0 2 4 7 10 10 6 4 0 1
o/p:5 urs:4

$$$c[i]=max(c[i-1], max(a[0..i]*b[i]));$$$

Let f(N) be the function that solves this problem, that is, it returns a $$$vector<string>$$$.

Through observation, we can find out that the number of operations is $$$2^N-1$$$ and that $$$m = 2^{N-1}$$$.

Also, we can try the recursive algorithm, and consider the relationship between f(N-1) and f(N).

First, let L be $$$[0, 2^{N-1})$$$ number people and R be $$$[2^{N-1}, 2^N)$$$ number people.

Let's do doubling all the strings in the result of f(N-1) (vector with size $$$2^{N-1}-1$$$). (For example, "AB" to "ABAB")

Then, when looking at only L's, m = $$$2^{N-2}.$$$

Moreover, it is exactly half of R that opposes to element of each L. (Because it was doubling)

To make a pair where each element of L is opposed to the other half of R, we can add all of the strings in f(N-1) by flipping them. (For example, "AB" to "ABBA")

Then, each element of L forms $$$2^{N-1}-1$$$ oppositions with the elements of R, and $$$2^{N-2}*2=2^{N-1}$$$ oppositions between L's. , The total number of operations is $$$2^{N-1}-2.$$$

Now, if we add AAAA....BBBB...., the elements of L will oppose the elements of R $$$2^{N-1}$$$ times, and the number of operations will also match our prediction.

To summarize this,

1) Doubling all strings of f(N-1), and reversely add them to the original string.

2) Add an operation of the form AAA...BBB...

In fact, I don't know if this is intuitive.

I want to know how to intuitively think of bit & solution

Maybe you can try reading my submission.

I also didn't solve it.And I asked some people who solved it during the contest , most of them says : they just try to solve some small case (n=3 is enough) by hand and find the law in the end.

Edit: and there is a better way ,you can guess you need at least $$$2^n-1$$$ operations and use dfs to solve some small case and find the law behind it.

For me: constructive problem with only one integer as input? Try to solve for N=1 then use an answer for N to solve N+1. So just think about mathematical induction.

Left side is no of sequences times no of possible pairs in different teams.
Right side is no of different pairs times how many times each pair is in a different team.

Both of them should be equal since they are two different ways to count the same thing.

Use spoiler tag. Otherwise people will just downvote it for pasting long code.