Auto comment: topic has been updated by misteg168 (previous revision, new revision, compare).

DP Code for C pls...

For the solution for $$$D$$$, how does this show that it's never optimal to merge numbers?

I can't view the codes that are linked elsewhere

please add rate problem section

Auto comment: topic has been updated by Pablo-No (previous revision, new revision, compare).

Can anyone help me find issue with the logic for Problem C. I used greedy, first fixing the direction of rabbit for those pots where they dont have any other option like 11010 or 01011, then find if I can find the pair for them and then for rest of the rabbits which have options chose them greedily for left or right. Left those on the border or consecutive 0s as they always find a direction to not jump: https://mirror.codeforces.com/contest/2147/submission/339602741. Please suggest a simple testcase where it might fail, I am not able to find any, also it failed on 1705th testcase can't view that.

D should have been placed before C, imo... I had to think for a decent bit to come up with the critical observations in C, whereas in D it was very easy to guess that even numbers are split, well, evenly.

Thanks for the awesome contest! Had a lot of fun solving and implementing problem C and (unexpectedly) D.

For problem C, there's another DP with just one parameter. Whenever we put a rabbit, we make sure it can be placed, either looking at an adjacent rabbit or paired with the next rabbit in a $$$\texttt{010}$$$ pattern.

Expressed as forward DP:

• $$$f(i)$$$ is whether prefix up to $$$i$$$ is solvable
• $$$f(0)$$$ is true
• if $$$s_i == \texttt{1}$$$ (flower), we do $$$f(i+1) \operatorname{{|}{=}} f(i)$$$
• if $$$s_i == \texttt{0}$$$ (rabbit) and $$$s_{i-1} == \texttt{0}$$$ or non-existent, we do $$$f(i+1) \operatorname{{|}{=}} f(i)$$$
• if $$$s_i == \texttt{0}$$$ (rabbit) and $$$s_{i+1} == \texttt{0}$$$ or non-existent, we do $$$f(i+1) \operatorname{{|}{=}} f(i)$$$
• if $$$s_i == \texttt{0}$$$ (rabbit) and and $$$s[i..i{+}3) == \texttt{010}$$$, we do $$$f(i+3) \operatorname{{|}{=}} f(i)$$$
• $$$f(n)$$$ is the answer

Backward DP is similar.

Was it intended in problem F to cut $$$O((n + q) \sqrt{n})$$$ solution ?

For C, we can also solve by generating a bipartite graph. You can check this comment for more details: Comment

any one who is looking for D

see my submission 339613047

you will get an idea about the even odd simulation

for those who want to submit by there own take this idea:-

eg:-n=4

1 1 2 3

you can just calculate freq :-

1-2, 2-1, 3-1,

sort it in the pair in decr order of freq the main idea is that if 1 with count 2 and 2 with count 1 you can always chose the max count number because if you choose 1 then all the one we can decr and get the point equal to the count of the 1 i.e 2. but in the case for number 2 with count 1 you get only 1 point for the decr operation. i think that is pretty much required hint to solve or implement this one!

For C, only the run of 0101...1010 matters, which has >1 1s on both ends. For these, if there are odd 0s, we don't have an answer; otherwise, we always have an answer.

Proof: It's trivial that >1 consecutive 0s always have an answer. For single 0s with <=1 1s on both sides, if we have a group of >1 0s on a side (otherwise your run is incomplete), then we can imagine this run to always be of even parity, so the answer exists. (If it's odd, simply make the rabbit near the group to face the group). This considers all possibilities.

There's a pretty simple solution for $$$I_2$$$:

Make $$$46$$$ blocks of $$$301$$$ vertices each, the center of the $$$i$$$-th block being at [ $$$2^{\,{i+12}} - 2^{13}$$$ ] and $$$150$$$ vertices just to the left of the center and $$$150$$$ to the right.
That is, if the center is $$$c_i$$$, then there are points at [ $$$c_i - 150, \; c_i - 149, \; \dots, \; c_i + 150$$$ ]

Now take $$$2$$$ pairs of points such that the first pair of points are in the $$$a$$$-th and $$$b$$$-th block (with $$$a \lt b$$$), and the second pair of points are in the $$$c$$$-th and $$$d$$$-th block (with $$$c \lt d$$$).
It can easily be shown that if $$$b \gt d$$$ or if $$$b=d$$$ and $$$a \lt c$$$, then the distance of the first pair is more than that of the second pair.

So the main idea is: choose $$$2$$$ blocks.
Say the points of the first block are [ $$$p_{1} \lt p_{2} \lt \dots \lt p_{301}$$$ ] and the points of the second block are [ $$$q_{1} \lt q_{2} \lt \dots \lt q_{301}$$$ ]

Then jumping like this will ensure the differences are increasing: [ $$$p_{301},\; q_{1},\; p_{300},\; q_{2},\; \dots,\; p_{1},\; q_{301}$$$ ]

Basically, we are going back and going ahead $$$1$$$ extra step, then going back $$$1$$$ extra step, and so on.

We will do this procedure between the blocks in this order:

$$$(1,2),\; (2,3),\; (1,3),\; (3,4),\; (2,4),\; (1,4),\; \dots$$$

With some careful transitions between changing blocks, we can ensure the differences remain increasing.

We use $$$46 \times 301 = 13846$$$ points here, and an additional $$$990$$$ extra points to handle transitions, keeping the number of distinct points within the limit.

This solution works up to $$$n = 622935$$$ and can be extended to around $$$700{,}000$$$--$$$800{,}000$$$ by tweaking the numbers used.

Submission : https://mirror.codeforces.com/contest/2147/submission/339611687

There is a solution for E that take $$$O(nb + b^3)$$$ time instead of $$$O(nb^2)$$$. At each bit position $$$i$$$ we need to sort all numbers restricted to bits $$$0..i$$$ and choose the largest number out of the ones that we didn't pick for previous bits. note that we picked at most $$$b-1$$$ numbers for previous bits so for every $$$i$$$ we only need to store top $$$b$$$ largest values. You can obtain those in $$$O(nb+b^2 \log b)$$$ time using std::nth_element. After this preprocessing stage we can forget about the initial array, and the whole algorithm takes just $$$O(b^3)$$$ time.

P.S. This $$$O(b^3)$$$ factor could be dangerous if we had $$$t \le 10^5$$$ instead of $$$t \le 10^3$$$ but one can overserve that this stage of the algorithm actually takes $$$O(b^2 \cdot \min(b, n))$$$ time so we're good.

I feel this is a pretty clean solution for E : 339628766

I like this implementation for C rather than a flag / counter based implementation since it runs on the intuitive idea of removing what's unnecessary like 11->1 or 00->0 . Had a lot of fun solving this : 339628766

I submitted a greedy solution for D where the player always picks the available number with the highest frequency and I assumed NO merging happens but it passed. Can someone prove why it works?

Example

2 2 1

Alice picks 2 to get +2 points — > 1 1 1, then Bob picks 1 but I assumed that no merging happens so he also gets +2. — > 0 0 1.

Alice picks 1 and gets +1. So final answer is 3 2

This method is wrong but it passed somehow. Don't know why.

I wrote a problem very similar to B before.

523552D - A + B = Cookie

My version is actually harder since the distance between the elements of $$$x$$$ should be exactly $$$x$$$. Still took me 40 minutes to solve B though..

Today's contest had some really high quality problems absolutely loved C but I couldn't solve C during the contest.

for B I did something greedy we know that there are more choices for two pairs for small numbers compared to larger numbers, so if we just start fixing larger numbers first then we can fill the smaller numbers in the "holes".

D was a good Problem I noticed the fact that for a Person if the highest frequency element is odd then its best to choose it and if even then we can see that if we take any element which occurs odd times then its better to take that

int N; cin >> N;
    ll S = 0, diff = 0;
    vector<int> cnts, a(N);
    rep(i, 0, N) cin >> a[i];
    sort(all(a));
    for (int i = 0, j = 0; i < N; i = j) {
    	while (j < N && a[j] == a[i]) j++;
    	if (a[i] % 2) cnts.pb(j - i);
    }
    S = accumulate(all(a), 0LL);
    sort(all(cnts));
    reverse(all(cnts));
    rep(i, 0, cnts.size()) {
    	if (i & 1) diff -= cnts[i];
    	else diff += cnts[i];
    }
    cout << (S + diff >> 1) << ' ' << ((S - diff) >> 1) << nline;

After seeing potato167's code I understood C (so beautiful) So the main observation in C was having two consecutive same chars split the problems into different sub parts so now in one part I don't have consecutive stuff so only thing to deal with is the sequence 1010101010101. 0 before and after doesn't matter as its L and R respectively Now this sequence can only be good if no. of zeros is even so condition is length of this sequence is 3(mod 4)

Problem D code TLE https://mirror.codeforces.com/contest/2147/submission/339616363 If someone could share why I would really appreciate it

The solution for problem D demonstrates that merging numbers is never the best strategy.

The idea of problem F is to find all $$$\max_{1\dots p}a_p=p$$$ positions, so another solution is using a segment tree that maintains max $$$a_i$$$ and the info of SCCs of its right son, while the answer of a node can be calculated in $$$O(\log n)$$$ time.(I can't come up with the name of this data structure.) It's $$$O(n\log^2n)$$$ (because the pushup function takes $$$O(\log n)$$$ times) but enough to pass though.

C can be solved using 2-SAT as well. I feel like it is kind of an overkill but it was the first thing that came to my mind so I just went with it :))

In the solution of problem G, is that all $$$ord_a(m)$$$ should be $$$ord_m(a)$$$?

It was a swap(C, D) contest. Anyways, thanks for the round.

Although many people solved C with DP and basic if-else's there is a bit easier solution via DSU. First of all, we can see that two sections of rabbits are independent if the size of border in between is bigger or equal to 1. But, if it's equal to one, we can solve them together. Let's merge all of those. Now, we consider a group of rabbits, when are they solvable?

1- If there's any rabbit section of size >= 2. (We can show it) 2- If there's any rabbit that is either in the beginning or ending of the whole string. 3- If 1-2 are false, the total number of rabbits in this group must be even. 4- Else, answer is false.

We can manage all those via DSU easily. (We just need a flag for checking, and sizes.)

My code (although a bit rushed in the contest): 339545851

proving E was diabolical

First of all, the answer is bounded by $$$31$$$ because the maximum number that can appear in the array is: $$$2 \cdot 10^{9}$$$ and $$$2^{30} \leq 2 \cdot 10^{19} \lt 2^{31}$$$ so the only bits that can be set on are bits $$$0$$$ through $$$30$$$, giving a maximum of $$$31$$$ bits on.

Seems that there's a typo in the solution of E, it should be $$$2^{30} \leq 2 \cdot 10^{9} \lt 2^{31}$$$. (~.~)

The editorial of H explains nothing, could you write a more detailed one instead of forcing me to guess everything?

In problem E, it should be $$$2^{30} \leq 2*10^{9} \lt 2^{31}$$$.

I love problems B, C, E and F but I hate problem D. I rather quickly guessed the solution but failed to prove it for quite long and failed :( I was really surprised to see it get accepted. E was great because once you had the correct guess/observation, it was easy to prove its correctness. F was absolutely perfect but no time to code :( So overall thank you for the great contest!

In E what if we had to minimize the popcount instead?

Can Anybody help with why my code is giving the wrong answer? I was very convinced that it should work, but it's failing somewhere on test case 2 for Problem C — Rabbits, and I badly want to see where it's breaking.

What I am doing is basically seeing where the current rabbit is facing, if its face is to its left — In this case, I will need some right counter which means rabit facing left.

If the current rabbit can face either left or right, or it's not decided yet, I will mark undecided so that I can resolve it based on the next rabbit. If the next rabbit is undecided too, I'll pass the counter undecided until it's resolved.

Solution Link

I think the official editorial is too complex on problem I. I found a much better solution that can solve I2 even if $$$M=7182$$$. 339845253. I didn't use any DP or random. Are there solution even better?

Problem H.

The constructive proof for $$$d=2$$$ was surprising to me.

My question: Is it difficult to prove this problem using only general facts about the linear algebra of graphs?

For example, the problem can be restated as constructing a vector $$$x = (x_v)_v$$$ such that $$$Lx = (\deg(v))_v$$$, where $$$L$$$ is the Laplacian matrix. Let $$$B$$$ be the incidence matrix, then it can be written as $$$BB^{T}x=B \cdot \mathbf{1}_E$$$.

I tried to derive the conclusion from this kind of reformulation, together with well-known facts about the cycle space and the cut space, but I couldn't manage to find a proof.

If there is a neat proof along these lines, I'd love to see it.

I'm struggling to understand the proof presented in the editorial for D. More specifically I don't get the 'by induction' step in the first two of the three cases presented. Can someone help clarify please?

I get the logic behind removing the most frequent odd element first, and then even if it there's more frequent even numbers after that step it doesn't matter because they're going to get equal points for that anyways and so it's more beneficial for the second player to go for the next most frequent odd. I'm guessing that's what the inductive proof is trying to say because it's now a smaller case but it's got a lot more detail and I'm struggling with that.

Also is there an alternative inductive or other type of proof that is a little simpler? thanks

How will they know (for question G) which submissions are genuine and which are from cheaters? Past data or something else ??

I find the editorial for F to be totally unintelligible (maybe it's because I don't know what a tournament graph is), so I'll explain my solution here (btw, orz to the author for creating such a beautiful problem in this dark era of anti-gpt problems).

Let's sort $$$p$$$ and $$$s$$$ in decreasing order of values to get permutations $$$a$$$ and $$$b$$$ respectively, and then relabel every value with its position in the original permutation. For example, $$$[3, 4, 2, 1, 5]$$$ upon sorting becomes $$$[5, 4, 3, 2, 1]$$$, and upon relabelling becomes $$$[5, 2, 1, 3, 4]$$$. This simplifies analysis because now we can swap element $$$i$$$ for $$$j$$$ if $$$i$$$ occurs before $$$j$$$ in $$$a$$$ or $$$b$$$.

Define $$$v_a(i)$$$ to be the position of $$$i$$$ in $$$a$$$, and $$$v_b(i)$$$ to be the position of $$$i$$$ in $$$b$$$.

Let's consider an item $$$i$$$, and analyse the set $$$S(i)$$$ of all the items that $$$i$$$ is at least as valuable as.

Observation 1: The set of elements $$$S(i)$$$ lies on the contiguous range $$$a[l(i), n]$$$ where $$$l(i) \leq v_a(i)$$$.

The answer is then simply $$$\sum_{i = 1}^{n} n - l(i) + 1 = n \cdot (n + 1) - \sum_{i = 1} ^ {n} l(i)$$$, and all that remains is to figure out how to maintain $$$\sum_{i = 1} ^ {n} l(i)$$$ quickly.

Firstly, what even is $$$l(i)$$$?

Observation 2: We define an index $$$j$$$ to be "good" if the set of elements in the subarray $$$a[j, n]$$$ is equal to the set of elements in the subarray $$$b[j, n]$$$. Then, $$$l(i)$$$ is the greatest $$$j \leq i$$$ such that $$$j$$$ is a good index.

Now, how do we maintain $$$\sum_{i = 1} ^ {n} l(i)$$$ efficiently? Notice that to preserve the definition of $$$a$$$ after swapping $$$p[i]$$$ and $$$p[j]$$$, we only need to swap the values $$$i$$$ and $$$j$$$ in $$$a$$$ (and the same is symmetrically true for $$$b$$$ and $$$s$$$).

The task now reduces to this:

You're given two permutations $$$a$$$ and $$$b$$$, and have to perform updates where you swap two values in one of the two permutations.

Let $$$G$$$ be the sorted sequence of good indices w.r.t. $$$a$$$ and $$$b$$$. After every query find $$$\sum_{i \lt \vert G \vert}{G_i \cdot (G_{i + 1} - G_{i})}$$$ (the last element of $$$G$$$ is $$$n + 1$$$).

We'll maintain $$$G$$$ using a segment tree, and store $$$G_i \cdot (G_{i + 1} - G_{i})$$$ at location $$$G_i$$$ in the segment tree. How can we do this? Let's start off with an array of 0s, and for every $$$i$$$, add $$$1$$$ on the segment $$$(\min(v_a(i), v_b(i), max(v_a(i), v_b(i))]$$$. It's not difficult to see that the value at position $$$i$$$ in this array will now be $$$0$$$ iff $$$i \in G$$$. So we simply maintain this array using a segment tree, and at every position with a value of $$$0$$$ (a good index), we store $$$G_i \cdot (G_{i + 1} - G_{i})$$$. A swap will simply require removing the $$$2$$$ affected ranges by pushing a range update of $$$-1$$$, and then including the new ones by pushing a range update of $$$1$$$. The answer at any given point of time is simply the sum over all good indices (the entire range). Here's my code.

I also implemented a square-root decomposition solution with XOR hashing (to trivially compare suffix sets) just to see if a mindless cheese could be squeezed within the TL, and it's unfortunately a bit slow (runs in 2.7 seconds when tested with a higher TL on a custom mashup).

Interesting problem D

please help me understand the proof of problem E

Isn't D way too easy for 1700???

absolute genius

Can someone explain, why is the transition in G when we group terms by their rad correct? The process was that you pick a divisor of $$$p_i - 1$$$ for all primes of $$$m$$$ and then multiply their $$$\phi$$$, then add this value to the $$$lcm$$$ of the divisors. But then it changes somehow to picking divisors of $$$\phi(m)$$$ which are comprime with $$$m$$$ and I just don't understand why does it work?

The editorial solution itself is failing on testcase 1!

We want visualiser again

In the problem G's solution, the notation $$$[t]$$$ appears, but I searched through the entire explanation and couldn’t find any definition of it. Is this a commonly known symbol that I just don’t know about?

edit: I know what it is, sry. G is very good problem and hit my weakness of math theory, thx to problem preparer.

I think div2C editorial has some inaccuracies: "We should also take care of boundary conditions. If the string starts or ends with a zero, we can ignore that position by placing the rabbit looking towards the border; these cases were present in the sample tests." Counter-example — 01011 , here first 0 should look to the right (the only possibility).

"The last observation is that if we have two consecutive 0 's, we can split the problem using them in a way that every subproblem looks like this alternating pattern (101010…0101 ) with an odd number of 0 's. Thus, the only thing we need to look for is a substring with this alternating pattern that has an odd number of zeros." Can't say I fully understand what's meant by this statement, but I imagine idea is (according to code) that if we find 00 pattern, then we can discard 0 counts from before as it's always possible to make last fragment counting from 1|1 / _|1 / _|0 valid and continue validating only from the next occurence of 1|1.

The code given in question 3 gives YES for case 100101 but in reality the answer should be NO. Can anyone tell me the logic i can apply, as we cannot divide the string if there are 2 00 together.

C was preety good

In D explanation, I think there are slight inaccuracies. It states "if k>0 choose f0 , otherwise choose any x". From equation before, f0>=f1>=...>=fk, so k>0 means there are at least 2 odds, which is not true in case of "2 1 1" test case (1 needs to be necessarily taken first for the maximum).

In the block, which mentions 3 cases: for 1), it's not specified which odd i player 2 takes, difference equals to S at the end only if odd i is with the maximum currently available frequency at odd indices.

For 2), I think the formula should be S-2f{i}+2f{i-1}.

In 3) (even x for P2), editorial only discusses assumption when one fi is removed, what happens with two or more (I believe it can be proved that it's still >= S)? Also, proof on why strategy to merge numbers is not optimal, is not covered, unless that sort of overlaps with the "Assume you remove one..." part?

For problem C As per editorial for the last part if curr=false then answer is always yes string : ..... 1 1 0 1 0 1 0 1 0 0 1 0 1 0 1 last part : 1 0 1 0 1 0 1 0 0 1 0 1 0 1 ( we are having 0 0 , so curr=false) for this part answer is No ?? Can somebody explain this to me