## Hello, Codeforces!

I am glad to invite you to participate in Codeforces Round 951 (Div. 2), which will take place at Jun/06/2024 17:35 (Moscow time).

This round will be **rated** for participants with a rating below **2100**. Participants with a higher rating can take part out of competition.

You will be offered **6 problems** and **2 hours** to solve them! **Interactive tasks** may occur in the round. Please read this blog to get familiar with this type of problems.

All tasks are authored and prepared by me. However, I'd like to thank Greg908 for discussing ideas about problems and useful feedback!

I would like to thank:

Artyom123 for his amazing coordination!

74TrAkToR for the initial help with this round.

isaf27 for LGM testing.

dorijanlendvaj, A_G, Mangooste, andrei_boaca and BucketPotato for red testing.

ArtAlex, salyg1n, Kihihihi, 127.0.0.1, max0000561, ilyakrasnovv and a.nasretdinov for orange testing.

Semen07 for purple testing.

newb_programmer for blue testing.

A1st for cyan testing.

ishaandas1 for green testing.

TimoSvyato and HatakeyamaLeo for grey testing.

MikeMirzayanov and the entire Codeforces team for creating the wonderful platforms Codeforces and Polygon.

The goal was to create problems **interesting** to solve. Hope you'll enjoy them all!

**Score distribution:** $$$500 - 1000 - 1500 - 2000 - 2500 - 3000$$$;

Good luck!

**UPD: Congratulations to the winners!**

**Div. 2:**

**Div. 1 + Div 2:**

Editorial is out!

Scoring is an AP! Been waiting for such a round.

Look who's doing purple testing

Yeah, we get it. Kinda common as an East Slavic name tho.

ifte2001

Hoping +ve Delta

Forget about +ve delta dude. CF is brutal.

agreed, solved C before B , B took almost 90 mins. again i am going down from so close from expert

lmao, author so obsessed with cyclic shifts he applied one to the problem ordering of B,C,D

Underrated comment

how did you solve the B. I quite didn't get how the XOR would work in that.

how did you come up with the idea of B?

dont know why but smallest set bit in xor is giving answer

I did it like this let rth term of seq a be coincides with sth term of seq b. Then we will have rth term as x^r and sth term y^s which are equal so x^r = y^s Taking xor on both sides we have r = x^y^s So for all values of s [1,...] we will have a value of r now this seq will continue until no bit of s coincides with set bit of x^y. When they do the coresponding value of r will be differnt for that s

So number of possible results are the lsb in their xor

The answer is

pow(2,the number of identical last bits of two numbers)It's easier to see it as the biggest power of 2 that divides the diference between x and y

Or that divides their bitwise XOR.

what made you come up with the idea of taking their difference?

I just guessed that by the samples, when u notice that every answer in the output is a power of 2 then u tries to guess where it came from, I used the sample with the bigger numbers to confirm my intuition.

How is that derived?

Not as close as me :(

whoa that crazy

Spoilerwe both are from surat

Gujju? lol

Damn you applied binary search, thought but couldnt make it on time

B is easy with the right observation approach. C was more tricky, and D kinda casework-heavy. Managed to solve up to D.

can anyone help me by telling if this approach can work for b or not so lets say there is a common segment of length n between the sequences a and b.

now since both these sums are equal (sum1 = sum2) therefore, (sum1) xor (sum2) = 0

if anyone can help me , can this work

I have no idea why you make it so complicated. B was literally this easy, I solved it in 5 minutes:

man, i am absolutely terrible at bit manipulation. even though i am noob at cp, but at bitmasks and all my mind just gets stuck. how do you even come to this 2^k conclusion. any tips ?

Okay, so here's my thought process: If two XORs are equal, that means XORing both sides produces 0. Therefore, you can introduce a new variable, $$$Z=X \oplus Y$$$. So XORing something with $$$Z$$$ produces 0 when the other mask has the same bits. Therefore $$$a_{i} \oplus b_{i}$$$ must be $$$Z$$$. It is achievable when they differ in bits where $$$Z$$$ has 1, and have the same bits where $$$Z$$$ has 0. That means, if we know $$$a_i$$$, we know exactly what $$$b_i$$$ should be. So the last 0s in $$$Z$$$ means that there is a match between $$$a_i$$$ bits and $$$b_i$$$ bits. Increasing $$$a_i$$$ will result in an increasing $$$b_i$$$ as well. But when the bit flips at the first position where $$$Z$$$ has 1 in $$$a_i$$$, $$$b_i$$$ should flip too, which spoils the increasing pattern. Therefore, check the least significant bit of $$$Z$$$. It is well known, that

`x&(-x)`

returns the LSB of $$$x$$$.so it was like, the maximum range of numbers will be no of 0 bits at end . for example if it was two 0 bits , then the possible numbers would have been i,i+1,i+2,i+3 (similarly for j) and at i+4 the third bit would have changed for both i and j and it would have gotten equal and hence there xor would have become 0 whereas there is 1 bit at that position in Z.

it was an observation problem. I read the problem and got a rough idea that solution might contain something like checking which bits are matching and not, and doing something from there on. Then read the test cases.

The test cases were a huge giveaway for this question. The output of 8 (1000) for 4 (100) and 12 (1100) (first 3 bits match from LSB and ans is 2^3) hinted that we might need to check for first few matching bits in binary representation. So just pulled up a calculator, and converted all test cases input to binary, matched with output, saw the pattern. That's it.

Pattern: 1000...(as many zeroes as no. of matching bits in both nos. from LSB)...000

Now the idea was not directly

`ll ans=(X^Y)&-(X^Y)`

, but it can easily be simplified to that. You do need to worry about that. You could have just converted both numbers to binary and checked bit by bit manually for matching bits from LSB, and got the right answer. The notation is just an easier and mathematical way to do the same thing, which just comes over time.damn. so as soon as i see a bit manipulation problem i should just straight away start thinking and writing in binary representation.

bit manipulation by definition means

bit— which in most cases refers to digits in binary form of numbers. Although I am only a specialist so you should take my words with some salt, but in general, bit manipulation problems are (almost?) always solved by using binary representation.The tough part is not decide whether we have to use binary form for the bit manipulation, it is to identify whether the problem is of bit manipulation or not. To identify that, sometimes author of problem puts hints in problem statement, or constraints (like m<30, bcz 2^30 is 10^9, etc.), or in the sample cases (like this question, where analyzing cases gave away the entire trick). Sometimes there are no hints at all and we have to analyze the problem ourselves and come to a conclusion, other times a problem may look like "obviously" a bit manipulation problem but turn out to be something else.

okk. thanks for the advice. i will start practicing on some bit manipulation problems keeping in mind these things. btw what basic things would you advice me to learn for bit-manipulation like how to find OR of range of numbers and all.

I learnt all this quite some time ago so I don't remember where exactly I learnt it from, but there are plenty of resources on google, maybe some resources on codeforces catalogue section also might be there.

Another and probably the most important thing you should do is once you have solved a question, see others' solution. That way you can see different techniques which might be useful at other places. For example, in this question, you can explore why

`(X^Y)&-(X^Y)`

gives the same answer as the pattern matching I stated above (giving the position of lowest set bit), and in the process you may learn many new things. Just try to always explore and learn. Read editorials and everything.hmm got it. thanks

What is +ve delta,dude?

On

Observationyou may notice that the only changeable quantity after CF rounds ( or the most obvious one :P) is the rating of participants." A positive delta " hence denotes a positive change in the changeable quantity.

ohh,thanks!

I'm Salah Eldeen Al-Ayoubi

me too

Also you will be negative

I'm wondering if any time when authors had indicated that interactive task "may" occur eventually it didn't appear. Since there is an exact number of tasks aka 6, I understand the author knows exactly what tasks are the final ones, unlike when you are not sure which tasks will be final and provide a spread (like 5-7 tasks) where indeed interactive tasks may but may not occur. Is there any reason to be not explicit in such cases? ;)

Maybe they haven't decided between two tasks and only one of them will be in the contest?

Yes, it might be the case, but I consider all the contests when interactive problems occur. In 80 or more percent of cases when an interactive problem was mentioned, it is formulated like "Interactive problem may occur" and seldom "One or more problems will be interactive".

If an interactive task is coming, I hope it's not E or F again, it's always sad that I never get to try the interactive ones because they are obviously beyond my competetence...

It kinda partially happened in my contest 4 years ago, I stated that interactive problem(s) might have appeared, and in fact the only interactive found was Div1E (and no interactive in Div2 at all).

Time to test my limits again , hoping for an interesting round :)

Can't wait!

wishing to get +4 and not brick like I did last time when I needed +3 for cyan :)

I hope you get +204

thank you so so much :D

Why? If that happens you wont be able to become cyan too.

+204 >> cyan

i hope. to become green ,,, quite noob right now

liar

u r definitely not noob

hope to reach specialist this round <3

Get a cloth first.

Hope to return blue color for my handle ;)))

Is this round mathforces or algoforces?

Or interactiveforces?

Good luck to everyone except no one!

Interactivetasks may occur in this roundI always get stuck on

Cin a div 2 contest.Not just you.

Waiting for starship launch as well as div2

Hoping +ve delta after 2 bad contest for me

Score distributionGood Luck Have Fun!!

sorry

No because contest is after 3 minutes

Best wishes for everyone's A, B, C and D.

good luck everyone:)

I want to thank to the cosmic entity which come from heaven that come up with Problem B was great problem. I mean who in the right mind thought , ya problem B looks super cool and amazing , people will observe the test case even if it takes 80 minutes , btw solved C in 20 minutes

how c in 20 minutes?what was the observation?(sample cases?)

binary search on total sum and to check distribute in array with ceil(sum/a[i])

i did the same thing lol. I was actually surprised it worked xd

now i am also in doubt if its correct

I didn't even think of binary search, I just found the Lowest Common Multiple and it worked. Sum should be < LCM if not "no solution".

I just take sum as 1e9 and It Worked

mathforces

Samplecase forces ,or maybe I need a lot more practice

Same, I didn't know why my solution to C of LCM is right until I read the tutorial

I still don't know why I took the sum as 10^9 and it worked. I will take it, but I want to understand lol.

My solution to C without LCM 264475190

I have proof for the binary search solution, but i dont have proof for the lcm solution

I just came here and read the comments abt lcm. I'm really puzzled how it occurred to ppl and how they solved it using lcm. Only BS occurred to me at the moment

Guessforces

Hint for C anyone? ;)

LCM. (I just somehow guessed it, couldn't prove it in-contest either)

it involves basic math

Let $$$S=\sum x_i$$$

$$$x_i*k_i > S \implies x_i > S/k_i $$$

Sum over all $$$i$$$: $$$S > \sum{S/k_i}$$$

Divide both sides by S: $$$1 > \sum{1/k_i}$$$. If this condition is true $$$S$$$ can be anything, otherwise no solution. But since we need integers simplest is to take LCM

Sad I was one hour-late, problems look interesting

how can S be anything? If you choose S as 1 even if it satisfies the above condition, it won't work right! Can you be a little more specific

S can't satisfy the condition or not. If you choose S=1 for k=3,2,7 as in samples then:

x=14/41, 21/41, 6/41. Each $$$x_ik_i$$$>1

Whats the problem in this code line ? I have used some multiplier times LCM to be the sum. ~~~~~ code ~~~~~

Spoiler## include

## include

## include

## include

int gcd(int a, int b) { if (b == 0) return a; return gcd(b, a % b); }

void foo() { int n; std::cin >> n; std::vector k(n); int minm = INT_MAX; for (int i = 0; i < n; ++i) { std::cin >> k[i]; minm = std::min(k[i], minm); }

}

int main() { std::ios_base::sync_with_stdio(0); std::cin.tie(0); std::cout.tie(0); int t = 1; std::cin >> t; while (t--) { foo(); } return 0; }

in the editorial its being said that the condition 1>sigma(1/k) is a sufficient condition for answer to exist how can this be proven ? as such necessary condition i can prove using the method you used . vstiff iNNNo

Just check if

sum of money = $$$10^9$$$is possible or not. I don't have any proof either.I gave up on E, so here is your partial editorial

A:

Hint 1: What is the way to get the smallest maximum of a range of more than one element.

Hint 2: Look at only pairs of adjacent elements

Sol:

Search every pair of elements. Answer is minimum of the maximum of pairs — 1.

Code:

https://codeforces.net/contest/1979/submission/264409254

B:

Hint 1: Think about BITwise.

Hint 2: Look only at the first few elements in the list until items differ.

Sol:

Find the difference between a and b. Answer is the maximum power of 2 that divides this difference.

Code:

https://codeforces.net/contest/1979/submission/264415773

C:

Hint 1: Think of a way to equalize earnings.

Hint 2: What is the smallest number that is a multiple of all numbers.

Hint 3: How do we check if there is no solution.

Sol:

Code: https://codeforces.net/contest/1979/submission/264427427

D:

Hint 1: How much change can one operation do to the string.

Hint 2: look at lengths of consecutive elements.

Hint 3: Is there any equivalent operation in the context of k-complete strings.

Debugging Hint 1: Pay attention to the last consecutive elements.

Sol: 1.Check each length of consecutive elements. 2.If all lengths are k, then output n. 3.If more than one length is not length k or last is greater than k, output -1. 4.Else, if broken length is less than k, set operation length to first c characters where c is the current charcter you are in the string. 5. If broken length is more than k, do the same but for the c — kth character. 6. Do the operation with the designated length or the easier to implement equivalent operation of reversing the remaining characters. 7. Check is string is k-complete. Code: https://codeforces.net/contest/1979/submission/264452915

can you please prove your solution for problem c

Not really, but it is intuitive that all outputs must be the same, to maximize minimum output relative to input.

how did you come up with the idea of B?

Came up with answer with sample cases.

I proved it by looking at first n numbers of each array. If the last k bits of both numbers are same, then for all numbers 0 to 2^k-1, the elements in the array must be the same. As the bits being compared to are the same.

Can i share my not so concrete thoughts.. Let's say the longest common sequence is of length n , a_i = b_j , a_(i+1) = b_(j+1).. and so on. since a_i = i^x and b_j = j^y . Equating and simplifying gives i^j = x^y . For simplicity lets start i = 0 (i know i start from 1 but any (2<<k)-1 can be chosen as i )and find j correspondingly..then u wanna find largest n only...

correct?

holy cow i lost 55 min to find out i wrote var=- instead of var-=, how the hell i'm working in this sector?

I work in mathematics related field, trust me the number of times I have read incorrect "number of balls in a bag" in a probability example is probably infinite.

it's really hard for us ,

honest pupils and newbiewsto overcome cheaterssolution problem C was leaked . i didn't solve problem C though.

I just became Newbie, solved A and B on my own thought this going good tried my hand on C thought it was tough and then the RESULTS. Only way to over come this cheaters is actually equipping ourselves to solve that particular problem.

I predicted solution for B, C using case 4 in test 1

Should have solved C first instead of wasting whole time on D

Anyway, can anyone say how to solve D? I tried a lot. My idea was to divide the string into chunks of k size, and handle how many chunks are not of k size, excluding first and last chunk (handled separately).

Here is my submission, if anyone could debug it would be helpful : https://codeforces.net/contest/1979/submission/264475276

Hint: Use hashing

My crumbs of thoughts:

`-1`

.Solved on similar line of thought. If you need, you can take a look at my submission for reference :https://codeforces.net/contest/1979/submission/264493423

Solved just a few minutes after the contest :(

UPD: I think it should get hacked, because this should give TLE.

Did more than 13k+ people get B from observation only or was it the case that it's proof was trivial and simple?

I think this was a really nice problem.

`Ai = i xor x`

`Bj = j xor y`

If

`Ai == Bj`

=>`(i xor x) == (j xor y)`

=>

`i xor x xor y == j`

We can replace

`x xor y = k`

So we want

`i xor k == j`

`(i + 1) xor k == (j + 1)`

and so on.And now one nice thing is that if

`i xor k == j`

And

`(i + x) xor k == (j + x)`

Then

`(i xor (i + x)) & k == 0`

The above statement basically means that all the bits changed from i to i+x are unset in k.

Using this we can find the answer.

I think the line of reasoning can be like this:

xoring all integers will not cause any duplicates or missing numbers, but numbers are instead shuffled and gradually increase. Choosing $$$x=1$$$ causes adjacent elements to be swapped. If $$$x$$$ is even and $$$y$$$ is odd, then they cannot have more than 1 consecutive equal element. Testing powers of 2, choosingx=8will swap adjacent blocks of size $$$8$$$, giving $$$[8,9,10,11,12,13,14,15,0,1,2,3,4,5,6,7,...]$$$. Ifydoes not have the same bit set to 1, then any equal subarray between the two can have at most size 8.Yes, I got the hint only by noticing that 33554432 is a power of 2, but it was too late as so many people had already submitted.

Random approach for C, I don't know if it is legal or not: 264455549.

Hack welcome.

Lmao how? This proves guessforces is real.

Went on solving a completely different problem due to the typo in D

Just completed my code for E rip

how did u solve E.

Let's say we have a pair of points x,y and a,b at d manhattan distance, you can notice that the intersection of the pair of points will always be at x+-d/2,y+-d/2. Basically this means that out of the 3 points, atleast 1 pair of points must have a difference of +d/2 or -d/2 for both x and y coordinate. So, for each point out of n points you can just check if one of the 4 points exist or not, if they do, you can find the 3rd point using a set.

For 3rd point, make two types of set, one set will be indexed by x+y and one by x-y, now you can just binary search for the third point.

I still haven't accepted my code, so i might be making a mistake

I didn't feel that Problem C was easy. How come so many people have solved it? Was there something simple in the problem that I missed?

It is a standard LCM problem.

Please send the link of the problem.

Also , why was the constraint on N so low (N<=50)?

TBH The constraint on N doesn't matter. The LCM sol would've worked if N <=10^5 as well. The constaint on max (a) does.

My sol: https://codeforces.net/contest/1979/submission/264427427

I meant the link of the standard LCM problem. Also then why didn't they set N <= 10^5?

By that I meant that it used standard LCM techniques. and I guess N<50, because with high N, it is impossible to create a solution.

So that LCM of array may be small.

I think that depends on the range of values of K.

I also didn't find C obvious.

It was leaked on internet. I wasn't able to do it, but I guess I was close

Nice problems

Maybe that's skill issue on my side, but problem E is the worst problem I've seen in a year. It's just annoying copy-paste of several cases resulting in 200+ LOC.

Yeah, saw that and gave up on implementing it.

You can try to rotate the grid 4 times and each time looking for one direction only.

My implementation was also terrible. However, it is my own fault. My casework started with two cases and didn't look that bad. Then two turned into four, and four turned into eight. At this point, I was too invested to turn back.

Looking back, there were multiple ways to eliminate a big chunk of the casework. You can take this opportunity to learn useful techniques and avoid extensive casework in the future. Or you can shift the blame to the setters and fall for the same mistake next time. The choice is yours.

Thanks for a good round! Pleased to come back for such a contest.

problem 3 was interesting . Enjoy the problem do you?

k is divisor of ncost me 4 WA and > 90 mingreat passion...

Shit, that is an essential hint. I still know how it will help me to reduce the time complexity but alleast now I have something to think lol

High rating guys are saying like questions getting relatively tough in nowadays contests,then how come large no of people are able to solve problems upto C,like around 9000 submission on C is insane.It's really getting demotivating.

What was the intution for D? My solution was O(N2) ;P

Just use hashing for checking if the string after doing a given operation is equal to 000111000111... or 111000111000111... You have to do like rolling hashing or something like that in order to get the hash of the transformed string at each step

Well, I didn't understand any comment haha. I guess I got new stuff learn. I'll learn them and now and try again.

Just brute-froced with hashes, I hope they won't FST :p

Lol, I did the same, my solution got AC 264460961

You notice final string should be K size blocks like 111000111(for k = 3). Then you notice transformation is taking prefix, reversing it and addind to the end of the string. Then it is kinda obvious prefix must end on the first symbol where something gets wrong(because else this "wrong" part will get between good blocks and we can't do anything about it). Also if you see a block with size greater than k you should leave k last symbols of it and take the rest.

Trick is to release that only one possible location can be flipped to create a k-complete string.

find the first group whose size is $$$!= \ k$$$

if group $$$size$$$ is $$$< \ k$$$ consider the group in operation

if group $$$size$$$ is $$$< \ k$$$ consider first $$$k \ - \ size$$$ elements of group in operation

then check if the resulting string is good

Somewhat of an explanationThe pattern of the final string is something like $$$[00...0][11...1][00...0]..$$$ (All boxes are of size $$$k$$$ and alternating in parity).

Also, if you start with $$$s_1 s_2 s_3 s_4 ... s_n$$$, the final string (after 1 operation) will be like $$$s_{p+1} ... s_n | s_p s_{p-1} ... s_1$$$. So basically you have to choose a prefix, invert it and add it to the end.

So, consider the string as segments of continous blocks (each either $$$0$$$ or $$$1$$$). If the string is already of this form, print $$$n$$$. Otherwise, if a segment has length $$$len \neq k$$$, you need to cut this segment and $$$p$$$ must be inside this segment. Also, if $$$len<k$$$, then $$$s_p$$$ should be equal to $$$s_n$$$. So, you will need to cut the string as take $$$s.substr(0,p+k-d)$$$. Here, $$$d$$$ denotes the number of continous elements from the end, modulo $$$k$$$. (Example: string $$$s=01100111$$$ has $$$d=3$$$). If you do not, this part of the string will remain a substring, hence a substring $$$s[l..r]$$$ will exist and will have $$$(r-l+1) < k$$$, which violates the condition.

Now, you just have to check if this "cut" of the string yields a valid string. You can do this in $$$O(n)$$$. Also, this is done at most once. Because if the string cannot be cut here, then you cannot receive an answer.

I hope this gives you somewhat of a hint. Good luck!

How to solve E?

we can notice that if triangle is correct and $$$(x, y)$$$ is one of point of this triangle, than $$$(x + \frac{d}{2}, y + \frac{d}{2})$$$ also belong to this triangle. now all we need is to check that third point exist.

Don't we also need to check for (x+d/2,y-d/2)?

yes, we need, forgot about it

That's a nice observation. Thank you.

Transform cords by [x-y][x+y]. Now distance function is max of dX and dY. Aka the square. Then for point A with cords [X, Y] point B could be [X, Y + D] and C [X + D, (anything between Y and Y + D)]. Same with minus and Y cord.

(and you check it with two sets) with pairs [X, y] and [Y, X])

Hello where can I find the explanations and solutions for the questions?

Lucky again this round! \(^o^)/

B and C is pure guessing game for me and I guessed it!

And D is also kind of easy, maybe waste some time on debugging :)

No————

I should have solved E if even luckier, now I submitted my code and got AC after contest QAQ

Could you explain how to solve D? Thanks! I feel like I definitely overcomplicated my thinking.

The valid k good string must have k

`1`

, then k`0`

, then k`1`

... or k`0`

, then k`1`

, then k`0`

... For example, if k=3, then its something like`111000111000...`

or`000111000...`

If the string is already k good, then you can output n directly. Otherwise, you just need to check

the first placeit gets invalid(when continuous characters's cnt != k), try to do the operation and check: after the operation, whether the string become a valid k good string or not. If it become valid, then you find the answer, otherwise you can absolutely not find the answer and you can output -1.ohhhh, thanks!

MathForces!!

Codeforces should bring "report cheating" option..so many submissions on B and C.

Clicked submit on D with 30 seconds left. It didn't go through. Is this normal? 1st time I've left it that late, so was a bit confused.

guessforces, no prove but ac

guessforces lol,so true

Am I the only one missread the statement of problem F?

Kostyanych tells youthe number ofvertex $$$v$$$ with a degree at least $$$d$$$It takes me a long time, to realize that

the number of, means the index of $$$v$$$, not how many vertexs $$$v$$$ satisfie the condition...Fingers crossed for a positive delta ... Guessing theorems is kinda interesting :)

Problem B was tougher than C, at least for me, back to pupil.

Question C, I implemented it using binary search, but can someone explain the monotonicity issue?

https://codeforces.net/contest/1979/submission/264454069

Yeah also implemented it with binary search, no clue why it works; Funny enough you can just stop the binary search when your check ist True

https://codeforces.net/contest/1979/submission/264444231

Problem C can be solved in O(nlogn) by using LCM This is my solution https://codeforces.net/contest/1979/submission/264436019

I think time complexity for finding gcd is 0(logn) and that makes your solution 0(nlogn).

Oh yes, sorry for that

éditorial !!!!!!

I think tests for D are weak, because +-40000-optimization has passed: 264461313

quite curious, did none of the testers notice the typo in problem D?

I solved C without lcm. Lets S = 1e9 be the sum of all numbers. Then $$$x_i \cdot k_i > S$$$ for all $$$i$$$. Lets assign $$$\lfloor {x_i = (S + k_i)/k_i} \rfloor $$$ for $$$i \neq n. x_n = S - (x_1+x_2 ... +x_{n-1})$$$. if $$$x_n \cdot k_n > S$$$ we found solution.

Same for me, but I used 1e9 + 7 instead. I find out that the bigger the S, the more probability the answer is valid, though I don't know how it works.

I had the exact same approach in mind , but somehow I contradicted myself and didn't code it...:(

I have some reasoning behind this. We know that $$$x_i > \frac{S}{k_i} \Rightarrow S > \frac{S}{k_1} + \frac{S}{k_2} \ldots \frac{S}{k_n} \Rightarrow 1 > \sum_{}{\frac{1}{k_i}} (*) $$$ Its not hard to see if (*) true then solution exist. Lets consider solution with smallest sum of $$$x_i$$$. Then $$$x_i$$$ should be equal to least integer that greater than $$$\frac{S}{k_i}$$$.(otherwise we can decrease it). So we can assign $$$x_i = \lfloor (S + k_i)/k_i \rfloor$$$ and choose big enough S.

This reminds me of some math problems :)

Very elegant. Thanks for sharing.

Damn! Such a nice approach. Why didn't I think of this!

so elegant

Thanks for a great contest, maybe I am biased but more math related problems helped me solve 3 (when I usually solve 1 or 2). D looked like fun too. Too bad I can't write basic code, xD.

The math helped me too, first I solved C in under 20 minutes.

lol I just set $$$x_i$$$ where $$$i$$$ is the index of the minimum $$$k$$$ value to maximum possible ($$$10^9$$$), then set the other $$$x$$$ values accordingly and did a check

Ohh I wish I had skipped B to attempt C first, Bit Manipulation gives me a headache every time. Hope we get more such math related contests.

Finally I got out of 1700

Nice, congrats!

Thanks, man))

I am a little curious and would love to see the stats of blue,cyan,green,and gray users who submitted b,c

Thanks for great problems, found D very interesting by solving with hashes

I tried my best and solved 3 problems for the first time in div2. I was confused in contest time about why some many people passed the problem C and thought about maybe be easy this time. Now I figure out the real reasons in comments section....

Finally becoming expert Thanks for such a great round

:D

congrats!

Thanks :D

Thanks iNNNo for the contest! Problems were quite good! I hope everyone was good today!

https://codeforces.net/contest/1979/submission/264408353 bruh

lol

$$$B$$$ $$$C$$$ I have no proof I guessed solution , $$$A$$$ semi-proof , only in $$$D$$$ I had solution with proof but not quick enough to submit in time , AC after contest , such a bad contest for me

Does anybody know why my submission to B (264416480) shows "Pretests passed" still? Or is it only on my side?

Edit: seems to be fixed now!

'C' was something else today!

The system testing today felt like a cool breeze bcz of such a short duration after last div3 with 150+ test cases only for problem c.

I felt so happy solving C after a long time, only to see later that it had 9k solves :')

Thanks for the contest nevertheless, it was amazing iNNNo and all testers.

Are ya alting son?

264415415 My submission for A got WA because I didn't realize (1e9 — 1) = 999999999.0 instead of 999999999. It's so over for me

System test is far too weak ....

Even this $$$\mathcal{O}(n^2)$$$ memory and $$$\mathcal{O}(n^3)$$$ time complexity solution can pass the system test, and still I hack it:

https://codeforces.net/contest/1979/submission/264463080

bro wtf, I can up with a O(n) mememory and O(n^1.5) time complexity solution, and thought that would fail.

You sure that is $$$\mathcal{O}(n^{1.5})$$$ ? If you connect each pair with an edge, the number of edges can be $$$\mathcal{O}(n^2)$$$ if you see my case, which leads to a $$$\mathcal{O}(n^3)$$$ time complexity to find a circle of $$$3$$$ .

I'm not sure what you are thinking about, but if what you do is something different, please tell me.

No, I am talking abt a solution I came up with, in hindsight it is more like n^5/3

That's kind of impressive, but it may still seem hard to pass. I'm really interested in the solution now lol.

Trick is there are two solutions. Both hash all points such that it is possible to look up a point in O(1) time.

If d is small. For each item look around the permiter of all points of distance d, maintain two pointers that are d apart from each other, and see if there is a place where both pointers land on two points. This is a O(nd) solution

If d is big. Put each point into a box based of (x+y)%d. Brute force ech pair of points, and find third point in O(1). This works in O([40000^2/d]^2). I think.

$$$O(n^2)$$$ solution for problem D passed system test

https://codeforces.net/contest/1979/submission/264433381

Could you tell what test cases you are using?

https://codeforces.net/contest/1979/hacks/1033217/test

For those who used string hashing brute force in D, how did you compute the hash for a given $$$p$$$ quickly?

Just precompute the hash and reverse for the original string.

build two possible answer string hashes.

let's say for input:

8 4

two possible answer strings are 11110000 or 00001111

get hash value of both of these strings.

Then finally for each p,

1) get the reverse hash of the string consisting of $$$s_1$$$$$$s_2$$$$$$...$$$$$$s_p$$$

2) get the forward hash of the string consisting of $$$s_{p+1}$$$$$$s_{p+2}$$$$$$...$$$$$$s_n$$$

3) merge the two hashes you got from step 1 and step 2 to get the desired hash value of the string if you had choosen this specific p.

4) Finally, check if the hash you got in step 3 matches with any of the two answer hashes.

The problems are interesting, but maybe the system tests are not strong enough

Yes, D's system testing is simply not too watery

I really messed myself up misreading D lol

I blanked out on the first condition and thought something like 101101001011 would be 4-proper..

https://codeforces.net/contest/1979/submission/264486510

Can anyone help with C

I would recommend thinking abt LCM.

Sorry, but I am unable to find the editorial has it been released yet?

I have wriitten a partial editorial in the comments if you are intersted. Covers A-D.

Finally able to WOW at CM! Like the problems!

Wow such fast updation of rating, just after 1.5hrs of the round!

My funny binary search solution to C Link

would anyone mind telling me why this linear submission for D resulted in TLE on test 2?

https://codeforces.net/contest/1979/submission/264488685

thanks!

nvm figured it out

D was an absolutely boring problem without any idea underneath

I found it useful if you want to practice hashes

Would it be doable without hashes?

I have no idea what hashes are and I WA'd problem D

It can be. Notice that unless the string is already $$$k$$$-proper, there's only one $$$p$$$ that might be correct, so apply it and then check the result string.

More on that at my previous comment.

My submission in contest (a bit cryptic): 264443229

Oh I was trying to do that guess I implemented it wrong rip

I've noticed that some people's code in the D issue uses string addition, which I think will cause a timeout, but their code is ac, is the test point not rigorous enough, or is the string concatenation not o(n)?

Is it really correct to use binary search for problem C? Why do I feel like there's no monotonicity?

It's quite useless. Even if monotonicity exists, why not print the max value directly (if it works).

Tests on problem D are kinda sad. Many brute-force $$$\mathcal{O}(n^2)$$$ solutions passed because they typically come with very light operations such as erasing the first element from a string or comparing two strings. From what I see in the original tests the strongest test that counters this is $$$k=100$$$, but with this test the 'comparison' ends too early so these solutions normally took ~1.5s only.

With $$$k=1$$$ and an almost-$$$k$$$-proper string, dozens of such solutions fail. There are some variations needed for some solutions that has additional checks, or have opposite direction check etc, but the basic pattern is the same.

I am unsure how this contest became rated. In Problem B, the original problem statement referred to a subsequence, not a subsegment. Instead of updating the judge's validation code and rejudging the solutions, the problem statement was altered during the contest without any announcements !!!

Artyom123

is there any conflict with solution if it was subsequence actually? as subsegment is also a subsequence.

Yes, a big difference

X = 0, Y = 18 (10010)

Because in case of subsequence you should consider the zeros before the last 1 because if this bit is 1 in both the xoring is 0

It's a totally different problem

I really like the sample testcase for the D problem It actually help me a lot for AC

okay so i participated in this contest, and i copied answer from my one account https://codeforces.net/profile/aadarshsingh12345 to my another account https://codeforces.net/profile/zaprodiaq .I have ID/password of both, you can verify whichever way you want.. can i get my rating back ?

Participating with 2 accounts is also not allowed as its unfair because you can check whether your solution is correct in one account and submit on another without penalty.

yes, i did it by mistake.. what are repurcutions ? and can i get rating back ?

I don't think so your rating will be back. Don't worry about this contest focus on future contests keep practicing if you improve your skills, ratings will automatically increase so don't worry about it too much.

and this is my second account

ObservationForces, worst round i had ever attemepted.

Codeforces -> Guessforces

much implementation type contest

Can anyone tell me why I have used "fflush(stdout)" but it still shows "Idleness limit exceeded"? My Submission

Not sure what this did in your

`main`

, but this line clearly doesn't follow the interaction rules, thus the interactor would hang indefinitely, causing IL.Thanks so much. I made a mistake in my understanding of the topic.