oops, fixed it

why is he getting downvoted I do not understand how this works bunch of crazy people

This problem is constructed without providing any information. Most of the time, unless we find out that the lack of information doesn't affect something.But the Problem D in last contest which is Div.1 has difficulty of 2800,why are you angry about not doing it.

Imo div2 D was actually pretty good. It was construction which is pretty meh but you could solve it by writing things down instead of just guessing so it wasn't so bad.

hey no offense but why do it with DP when there is a pretty simple solution, it involves just counting the number of leading 1's in differences between consecutive elements of array sorted in ascending order.

I didnt use the editorial approach but the idea is similar:

• sort the array for better understanding
• [Assumption 1] we solve it more list if there are piles with rocks > 1 you will win irrespective of the number of piles --> if there is one pile you pick up all rocks else you pick up n-1 forcing next person to pick 1 -- as that is the min acc. to the question.

• obvious question --> how do I track the number of rocks per move when rocks are being removed from all piles??? --> you can sore the piles as delta difference for each pile and ignore repeating numbers --> now you can simply deduce which valid moves can be made.

• after this calculation now you have a delta vector and a base condition that if there is just one pile Alice wins.

• now treat this as a dp problem so while delta[i]>1 Alice wins --> first assumption if delta[i] == 1 winner 'Bob' now simply maintain who was wining at position n+1 while moving back and toggle it whenever you find 1;

The editorial does this much simply by just checking if there is an increasing sequence but I couldnt really get to such a simple solution in the contest.

This is my solution from the contest using recursion with memoization.

First I sort the array and remove duplicates for convenience. In the array dp I remember whether or not the player wins if it's his turn on a certain index. If there is a move that the current player can make such that the opposing player is in a losing position on the next index, then he is in a winning position on the current index. The current player is also in a winning position if he can make it so he is in a winning position on the next index.

It is possible to do both moves if the difference between the current pile and the previous one is greater than 1, so we take both into account. This works because you can leave 1 rock in the current pile and then it is your turn on the next index, or you can take all the rocks and then it is the opponent's turn on the next index. If the difference between the current pile and the previous one is equal to 1 then is impossible to have the next move on the next index, so it is only the opponents.

Look at the code as well, I think it is quite clean.

Div2-C dp solution Initially sort the numbers and remove the duplicates and then take difference with respect to previous element. Now start iterating from backward. We can say that when the the diff is not equal to 1 the first player always wins. but when it is equal to the 1 the player who wins i+1 will lose so dp state is dp[i]=1^dp[i+1] when 1 is diff value at an index, dp[i]=1 when the diff is equal to any value other than 1

https://codeforces.net/blog/entry/128935

If you view the problem as: "construct the smallest possible final strip such that you can create a 'walk' on the strip that corresponds to the original string", then you can see that any repeated 00 or 11 is 'suboptimal'. From there there's only one possible string you can create and you can simulate it.

Of course, formally proving that the final string cannot contain any 00s or 11s is harder (and I eventually did it using the same solution as the editorial) however for my original submission I just used 'proof by AC' after it passed the samples.

I thought, if you have three consecutive characters you can "merge" them into 1 by doing the zig-zag fold. By doing this repeatedly you end up with a string with maximally 2 consecutive characters. Also it's never bad to do this because if there was an optimal folding which contained an overlap between more than 2 consecutive characters, both sides of the fold could be merged, resulting in a better solution. When the max number of consecutive characters is 2, I felt like it was pretty intuitive that you should always fold between the consecutive pairs because it always works and you do maximum folding.

Nim games (Game theory) — gfg link

You should try to find out when someone has control over the rest of the game the one who does wins the rest doesnt matter thats how i solved C

The CF problems usually don't require any knowledge other than basic math and number theory, these are called game theory problems, when you're trying to play optimally as bad ur opponent plays is called Maximin strategy, the kind of game where the participants remove objects, etc is called nim games, which for CP, in general, there is no need other than just simple logic + math.

Learn the “plus-minus” principle (retroanalysis of the game).

How to force player to play the only possible bad move

Taking input is O(nm).

or may be like this 258432643

To solve problems like Div2-D one must always try to see the problem using different perspectives especially when it is less intuitive. In other words, if one approach doesn't work then jump to other approaches. I tried to solve using greedy and dp but could not do it.

it says: you want have every possible sum, how? One way is to have n ones. but something else, there is always a way to represent a number as the sum of powers of 2, so you think of log and power 2-based solution, now the main point is how to tweak those powers of 2 such that, there won't be a possible sum but others will be possible, there is a trap I fell into in the contest time:

To make it work, How to remove/add some other integers based on k to the {1, 2, 4, 8, 16, ...} sequence.

which may be possible but requires a lot of case forking on the set bits in k.

there is also another important observation, $$$k = k/2 + k/4 + \cdots$$$

which with a little bit of tweaking with the math, you get that you can go from $$$(k-1)/2$$$ to $$$1$$$ and $$$k+1$$$ to $$$2*n$$$, using multiplying by 2. which will give you the solution, now there is left to prove that you can create anything, but k.
which is the proof represented in the editorial

I hope this was helpful to let you understand the intuition to how to get the solution.

Read the Question Once Again

You should read this ...

The color you fill the rectangle with is the color that the cells you select are.

Yes, correct answer is Bob

I failed...

it is so correct.

I also got the idea in the last few minutes, but luckily solved 2 minutes before contest ended

I got it, nevermind

what a beautiful profile picture

I took 2k, 4k, 8k... until 2^i*k is less than n, I also took 3k; also another k+1; then to be able to make all the numbers smaller than k:

         k--;
         while(k!=0){
           add((k+1)/2);
            k/=2;
         }

So we have numbers from 1 to k-1, if we add k+1 we have all from k+2 to 2k

2k,4k,8k.. helps us to get any M*k, if M is odd we can take 3k add this to (M-3)*k

If we use it, we can make all M*k+x, x<=k-1

if v>k there are two cases for v-k-1 Case 1: v-k-1 does not have ith digit on,in that case we already have all the power of 2 from 0 to 19 except i so v-k-1 can be easily obtained by combining those numbers; Case 2: v-k-1 have ith digit on, in that case lets remove the ith digit by subtracting (1<<i) from it ,hence instead of subtracting k+1 from v , we subtract k+1+(1<<i) , now v-k-1 has turned to case 1 because we have already removed ith digit.

thats a damn cool solution bro

could you explain the implementation ?

First observe that when the smallest pile contains 1 then the player is forced to choose 1. Thus it is a forcing move. Now remove all the duplicates in array and sort it in ascending order, as this does not affect the answer.

Now consider the case when no consecutive numbers in the new array have a difference of 1 between them. You will see that when a person is forced to move (that is, the least pile is 1 in the person's chance), he/she will definitely lose.

Now let's focus on the case when there are is some sequence of consecutive numbers starting from the least element.

Case 1 -> they start from 1. For eg: 1 2 3 4 8 9 .... In this case Alice can convert this to 1 8 9 .... for Bob. Hence Alice wins. eg2: 1 2 3 8 9.... In this case Alice will only be able to convert this to 1 8 9... for herself. Hence she loses.

Case 2 -> they do not start from 1. For eg: 2 3 4 5 8.. In this case Alice always wins because she can convert this situation to 1 2 3 6... for bob and the situation 2 3 4 8 to 1 2 3 7 for Bob.

Hence we have covered all the cases. You can see my code for more clarity. You will have to try these examples yourself and convince yourself.

When the condition is "2 5 11" and it is Bob's turn, Bob can choose $$$k = 1$$$ and the stones will be "1 4 10". Now Alice must choose $$$k = 1$$$ and the stones will be "3 9". Then Bob can choose $$$k = 2$$$ and it will be "1 7". So Alice has to choose $$$k = 1$$$ and there will be only one pile of stones which has 6 stones. It means that Bob can remove all of them and win the game.

I think the key of this problem is when the least number of stones is $$$1$$$, the player who should remove some stones does not have any choice but let $$$k = 1$$$. So Alice and Bob should jump out of this "rule" and force each other to be trapped in this "rule".

Hope to help you.

:D

Yes, try CF1922E : Increasing Subsequences