I hope you enjoyed the contest!

Author: PurpleCrayon

**Tutorial**

Author: PurpleCrayon

**Tutorial**

Author: Monogon

**Tutorial**

Author: PurpleCrayon

**Tutorial**

Author: PurpleCrayon

**Tutorial**

Author: PurpleCrayon

**Tutorial**

1615G - Maximum Adjacent Pairs

Author: BledDest

**Tutorial**

Author: Monogon

**Tutorial**

As someone who got WA pretest 8, was G doable with flows?

By making a test case like $$$(a_i$$$ $$$0$$$ $$$0$$$ $$$b_i$$$ $$$n)$$$ repeated $$$m$$$ times the answer is quite clearly $$$m+($$$size of maximum matching where edges are $$$a_i-b_i)$$$, so unless you can solve maximum matching with flows the answer is no.

MemeI solved upto E in the contest and have ready code for F to submit now lol. Amazing problems.

How to solve problem b for l and r less than equal to 10^9.

Maths

solve by doing pre-computation... and in this precomputation use prefix sum method to store no. of zeros bitwise ... so at the end you can get answer of each testcase in o(1) time

This works only for l, r <= 2 * 10^5 no ? Correct me if i'm wrong.

Yes Bcoz test case is up to 10^4

But ... "How to solve problem b for l and r less than equal to 10^9.

"

Do you literally think , Test case<= 10^4 And then l and r <= 10^9 Will this work bro?

Correct me if I'm wrong, but you said : solve by doing pre-computation... and in this precomputation use prefix sum method to store no. of zeros bitwise ... so at the end you can get answer of each testcase in o(1) time

Have I misinterpreted something ?

Then it'll work... Definately i guess... What you say according to your opinion?

IMO, your algorithm works only for l,r <= 2*10^5 no ?

Yes...

so your algorithm doesn't work for 2*10^5 <= l, r <= 10^9

UPD : sorry everyone for the long conversation

we can calculate the number of set bits at jth position in [1,n] in O(log n)

Yeaa... Sigma( 2^(i-1)) ;i = pos of set bits greater than Or equal to j in n. Correct?

Edit- with some modifications for the equality thing

count of numbers in [1,x] having jth bit set is floor(x/(2^(j+1))) + max(0,x%(2^(j+1))-2^j).

Can you please explain the purpose of max() func here? Because IMO x%(2^(j+1) — 2^j) would always result in +ve number which ultimately will be the maximum.

look closely i have written [x%(2^(j+1))]-2^j which can be negative

Sorry, my bad!

It can be easily done in

O(log2(r))HintCount No of kth set bits in L to R in O(1). (Here you go)

CodeCongrats for being the Legendary Grandmaster : )

Thanks ^-^, You too for becoming International Master. Merry Christmas Everyone :)

O(log(r))*

Yeah sorry! It is of O(log2(r)).

Can you explain how your code for finding total numbers having Kth bit set is working

What is the logic for count function?

You may find here

Hope it helps :)

Bro, I did not understand how does your getcount function work. Could you please explain how does it work?

For all the bits greater than kth bit, he shifted them right by 1 , and deleted all the smaller bits. Second expression is to add more stuff if kth bit itself is set in n.

Can you please explain why you used l and r+1 in calculating x and y? I think it should be l-1 and r+1, but got WA using this.

Actually, this

`getcount(int N, int K)`

function returns the no of Kth set bits in`[1, N-1]`

. So we have to give arguments`getcount(N + 1, K)`

to get no of Kth set bits in`[1, N]`

. You may find clear explanation hereSo to get the no of Kth set bits in

`[L, R]`

we can have`x = getcount(L, K)`

that gives No of Kth set bits in`[1, L-1]`

and`y = getcount(R + 1, K)`

that gives No of Kth set bits in`[1, R]`

so by substracting

`x`

from`y`

we can get no of Kth set bits in`[L, R]`

.Hope you got it :)

My solution to B(without precomputation)

140459589

Hey! I actually found some different solution for problem C and I guess it's supposed to work? I started with the same observation than the editorial: we will consider the count of different types of candles.

The four types are: $$$10, 00, 01, 11$$$

We can apply operations on types: $$$10$$$ and $$$11$$$ because these types are the only ones having the candle of string $$$a$$$ setted to $$$1$$$ (and we can only to operations on $$$1$$$ candles)

Now, what will happen if we apply an operation on a char of type $$$10$$$ ? Let's call $$$[a_ib_i]_{old}$$$ the count of the type $$$a_ib_i$$$ before the operation and $$$[a_ib_i]_{new}$$$ the count of the type $$$a_ib_i$$$ after the operation.

So if we apply an operation on a char of type $$$10$$$ we'll have:

$$$[10]_{new} = 1 + [00]_{old}$$$

$$$[01]_{new} = [11]_{old}$$$

$$$[11]_{new} = [01]_{old}$$$

$$$[00]_{new} = [10]_{old} - 1$$$

In a similar way we can find how $$$[a_ib_i]$$$ will change if make an operation on a char of type $$$11$$$.

Furthermore, doing the same operation twice is useless as we will comeback to the same string.

As an operation only do a small local change (+/- 1) and let two counts invariant (it just swaps them) we may think there is not that much reachable strings.

So one could implement a BFS where the nodes contains the count of each type and the transitions are: apply operation on $$$10$$$ or apply operation on $$$11$$$.

It appears that it works quite fast. Here is my AC code (~90ms): 140494838

I have some intuitive ideas of why it's fast. I'll try to think a bit more and I'll update this comment if I found something :)

The total number of nodes and edges is $$$O(n)$$$ due to the observations. Basically, we always have that $$$c(10)+c(00)$$$ and $$$c(01)+c(11)$$$ are fixed because the string $$$b$$$ doesn't change, and after an even number of operations we also have $$$c(10)+c(11)$$$ is fixed because two operations is just a swap. From these three equations, the count $$$c(10)$$$ uniquely determines the other counts.

The nodes that correspond to an odd number of operations are just one step away from an even number of operations, so we conclude the size of the graph overall is $$$O(n)$$$.

I got the same idea, but without BFS part: https://codeforces.com/contest/1615/submission/140485290 so the idea is that it is enough to check only one action on each type

How to do B??? :(((( Can someone give an easy explanation plzzz!

This is how I solved B.

Notice that the maximum value you can have in all test cases is 2 * 10^5, so let's precompute a prefix sum arrays ps[i][j], i is from 0 to 200000, j is from 0 to 19. ps[i][j] is the total count of bit 1 in bit position j for all numbers from 0 to i.

Then each test case becomes checking the prefix sum in range [L, R] for all bit positions. In order to use minimum deletions, we want to take a bit position that has the most 1s.

Sorry if this is a stupid question but can you tell me why

`j is from 0 to 19`

. An int is represented by 32 bits shouldn't it be 0 to 31As 2^19 > 2 * 10^5 therefore if we check for larger values of j the count is always zero.

I'm not sure, but I think that it's possible to solve H using slope trick.

Just wanted to say, D was brilliant

Tasks are good but time to think about them no so much :(

Can anyone give the proof of bonus in problem C?

Take a look at the submission: 140511019. If we do operation on 10, we end up scoring (#00 + 1) * 2 + 1. If we do operation on 11, we end up scoring #00 * 2 + 1.

And if #11 is 0, then doing operation on 10 won't work either, since #00 + 1 should be equal to #11, which is impossible.

could you please elaborate how you concluded

#00 + 1 should be equal to #11Here's a chunk of code that explains it:

For result to be updated,

`newType01`

should be equal to`newType10`

, thus #00 + 1 is equal to #11.Problem D was very nice imho.

Hey !

I actually solved $$$C$$$ quite differently. First check if two strings are equal if yes answer is $$$0$$$. Otherwise, Consider two pairs: $$$E$$$ = (count of equal $$$0s$$$, count of equal $$$1s$$$) and $$$NE$$$ = (count of not equal $$$0s$$$, count of not equal $$$1s$$$). Consider these two pairs as starting state. Now, we can simply run $$$BFS/DFS$$$ to check if we can reach to goal state which is $$$E$$$ = ($$$0$$$, $$$1$$$) and $$$NE$$$ = ($$$x$$$, $$$y$$$) where $$$x + y = N - 1$$$. This is the goal state because last move we do will have this kind of form. At each step, we can either take $$$1$$$ from $$$E$$$ or $$$NE$$$ and then we swap $$$N$$$ and $$$NE$$$ (we also swap number of $$$0$$$s and $$$1$$$s in each pair while handling picked $$$1$$$ separately). If we can't reach goal state answer is obviously $$$-1$$$ otherwise we can simply output current level of $$$BFS/DFS$$$. I had an intuition that this process will not continue forever and will end in after some small number of steps (I didn't prove correctness do reply if you can prove it).

My Submission

This is also my way. I also need someone to prove it. My submission

Another way to solve $$$C$$$:

First of all, selecting the same candle twice will not change anything, so each candle will either be selected once or not at all.

If we select $$$x$$$ candles, the number of ones in them must be $$$\lceil\frac{x}{2}\rceil$$$, because the sequence of selected candles must be those with initial values 1010101...

If $$$x$$$ is even, at the end the selected candles will be inverted and the others will not. If $$$x$$$ is odd, the selected candles will not change and others will be inverted.

As we know the invalid candles that need to be inverted having count $$$cnt$$$, if $$$cnt$$$ is even we can try to select the invalid candles, and if $$$n-cnt$$$ is odd, we can try to select the correct candles.

At the end take the minimum answer found or -1 if both trials failed. If a trial succeeds, its answer is the count of selected candles.

$$$\lceil{\frac{n}{2}}\rceil$$$ should be $$$\lceil{\frac{x}{2}}\rceil$$$.

Corrected, thanks.

had very much same logic ...got 3 WA during contest bcz i made count of 1 >=ceil(x/2) istead of ==ceil(x/2) (sob)

I have solved so many problems similar to problem D and yet again during the contest struggles to do it

It will be helpful if you send the link to those similar ones. And also some good resources I should go through before solving them.

Problem E has an N*sqrtN*logN solution which is good enough to pass system tests but can be hacked. I hacked 1 and 2

The solution constructs some sort of a longest-path decomposition.

A sketch of a proof why that's the complexity, as discussed with kostia244:

There can be at most $$$O(\sqrt{n})$$$ paths of length $$$> \sqrt{n}$$$, so the dfs works $$$O(n \sqrt{n})$$$ times. For the shorter paths, consider the forest at some time instant. If you give a potential equal to the depth of a tree to each node in that tree, doing a dfs and taking away 1 from the potential of each affected node reduces the potential of each affected node to at least the actual potential of the affected node after the tree has been split into a forest by removing the longest path. So the total change in the potential is at most the initial potential, which is $$$O(n \sqrt{n})$$$, since only the short paths remain.

The extra log comes from the usage of std::set.

Does anyone know the ratings for each of the problems?

In the editorial for problem F, $$$p_{ij}$$$ is defined as the number of ways to get $$$\sum_{i=1}^{k} |a_i-b_i| = j$$$. I think the $$$\sum_{i=1}^{k}$$$ shouldn't be there.

In problem B

What I did is count the number of 0s of every array element at every bit position and the ans will be the minimum of all those counts

My solution

Its complexity is O(32*n) which should pass the given constraints, isn't it?

since the maximum constraints is 2*10^5.

Am I wrong?

It's $$$O(32\times \sum (r - l))$$$, and the sum of (r-l) will be $$$10^4 \times 2\times 10^5 = 2\times 10^9$$$, so you will get TLE.

Thank you for the reply but why is this summation sign is coming. The 1st loop runs for 32 times and the second loop runs for (r-l) time times so all together it will be 32*(r-l) isn't it?

t test cases.

That I was meaning to ask you in competitive programming do we have to consider the constraints of t(the number of test cases) also? Sorry, if its a stupid question I don't know about it.

Always consider it unless there's a constraint of $$$\sum (r-l)$$$.

The Problem H is well-known in China...

Maybe the G and H are both useless algorithms.

Really? I never heard about it ...

Check this: https://www.luogu.com.cn/problem/P6621 .

Thanks .

Hello Monogon, I think there is a typo in your editorial.

In problem H's editorial,

I think it's supposed to be $$$s \rightarrow u$$$ and $$$u \rightarrow t$$$, right?

Yes, I'll fix it

which problem was interactive ?

Every problem is interactive when you talk about it with friends.

What if you don't have coding friends? :(

https://codeforces.com/contest/1615/submission/140504399 problem B. I dont know why i got a time limit error at pretest 3 .

you are doing 2e9 operations in 2 second which will surely give you TLE. note that in problem there is no limit on sum of all test cases.

but for each test case the time limit is 2s right. i dont think my code takes more than that(for each test case) even in the worst case. or am i wrong?

you have 2s for t test cases not for each test case

Is there anyone can use DP to solve problem E? Thank you in advance.

[ignore, sorted] i was returning without taking complete input on a multi — test.

Problem D was not original. I think a similar problem appeared once on codechef PARITREE

Can someone explain why we only check bits 1-30 at problem B? Shouldnt we also include the 0th bit?

I think in explanation , 1-based indexing is considers.

so 1 here is LSB- least significant bit

You're still considering 30 bits, when an int has 31 bits (excluding the sign bit). Shouldnt it only make sense to check all 31 bits?

check constraint, 2*10^5, I only checked 20 bits, checking more bits than that is not required

Thanks for the info!

could someone elaborate the bonus statement of problem C

I only want to know how to find the Key observation of 'F'? It is too difficult for me.

The most sensible way to reach the key observation is by noticing the invariant of the problem.

An invariant is some property of the string which doesn't change under the operations available to you. For example, one possible invariant in this problem is the parity of the number of ones in the string: If we started with an even/odd amount, every operation will add/subtract two ones, therefore keeping its parity.

However, we want to find a tighter invariant. We want to be able to say that if $$$s_1$$$ and $$$s_2$$$ have that property, then we can reach $$$s_2$$$ from $$$s_1$$$ (or vice versa, of course). It is not possible with the previous invariant, as $$$0101$$$ is not reachable from $$$1010$$$.

The correct invariant to look at is the number of zeros on even positions plus the number of ones in odd positions. It is indeed an invariant (check). Now we construct $$$s\prime$$$ which will act as a "dual" problem: for every bit $$$i$$$, if $$$s_i$$$ adds to the score of the string (so either $$$i$$$ is odd and $$$s_i$$$ is 1 or $$$i$$$ is even and $$$s_i$$$ is 0), we choose $$$s\prime_i = 1$$$, otherwise $$$s\prime_i = 0$$$. Also, every operation on $$$s\prime$$$ would be to flip two adjacent different bits (check that it indeed corresponds to a basic operation on $$$s$$$).

Notice that:

where is D problem standard code?

Problem C : Menorah

My Code with explanation : click here

I'm not sure whether the proof in E is called contradiction or exchange argument. Can somebody elaborate?

Edit: Oh, the editorial is updated! There was the word "contradiction" sometime and I commented on that. I also had too many doubts about the first revision of the proof but everything is now clear to me. Thanks!

In problem D,how can I find out the final r_i for each node? Could anyone please show me a sample of the code to problem D?Thank you!

Nice contest!!

Can anyone share their code for C that worked? Thanks in advance

Why are we able to add a direct edge between nodes $$$a$$$ and $$$b$$$? Or more precisely, how is a path relationship converted into a parent-child relationship?

Also if we add direct edges, won't we be creating a graph rather than a tree? PurpleCrayon

Got it, thank you so much!

How to Solve the Challenge Problem given in Editorial in Problem B

`Challenge: solve the problem with 1≤l≤r≤109.`

You can count the number of bits set as $$$1$$$ in the $$$i-$$$th bit from $$$[0,n]$$$ inclusive by noticing that the number of set bits alternates every $$$2^i$$$ numbers. For example for $$$i=1$$$, and the range $$$[0,7]$$$, the numbers are $$$000,001,010,011,100,101,110,111$$$. Notice that $$$i=1$$$ (the second bit from right) changes like this: $$$0,0,1,1,0,0,1,1$$$, it alternates between $$$0$$$ and $$$1$$$ every $$$2^i=2$$$ numbers. So you can use this pattern to count the number of ones in the range $$$[0,n]$$$ by dividing $$$\lfloor (n+1)/(2^{i+1}) \rfloor $$$ and handling the remainder separately.

See submission here: https://codeforces.com/contest/1615/submission/151272206