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
we 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 Observation you 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!
Interactive tasks may occur in this round
I always get stuck on C in a div 2 contest.
Not just you.
Waiting for starship launch as well as div2
Hoping +ve delta after 2 bad contest for me
int score=500; while(score<=3000) { cout<<score<<" "; score+=500; }Good 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 ~~~~~
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); }
double sum = 0; for (int i = 0; i < n; ++i) { sum += (1.0 / k[i]); } if (sum >= 1) { std::cout << -1 << std::endl; return; } long long lcm = 1; for (int i = 0; i < n; ++i) { lcm = (lcm * k[i]) / gcd(lcm, static_cast<int>(k[i])); } double double_p = static_cast<double>(n) / (1.0 - sum); int p = static_cast<int>(ceil(double_p)); double double_phi = p * (1.0 - sum) - n; int phi = static_cast<int>(ceil(double_phi)); for (int i = 0; i < n; ++i) { if (k[i] == minm) { std::cout << 1 + p / k[i] + phi << " "; continue; } std::cout << 1 + p / k[i] << " "; } std::cout << std::endl;}
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://mirror.codeforces.com/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://mirror.codeforces.com/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://mirror.codeforces.com/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://mirror.codeforces.com/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 newbiews to overcome cheaters
solution 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://mirror.codeforces.com/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://mirror.codeforces.com/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 xBj = j xor yIf
Ai == Bj=>(i xor x) == (j xor y)=>
i xor x xor y == jWe can replace
x xor y = kSo 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 == jAnd
(i + x) xor k == (j + x)Then
(i xor (i + x)) & k == 0The 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:
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://mirror.codeforces.com/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 n cost me 4 WA and > 90 min
great 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
The 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 k0, then k1... or k0, then k1, then k0... For example, if k=3, then its something like111000111000...or000111000...If the string is already k good, then you can output n directly. Otherwise, you just need to check the first place it 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 you the number of vertex $$$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://mirror.codeforces.com/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://mirror.codeforces.com/contest/1979/submission/264444231
Problem C can be solved in O(nlogn) by using LCM This is my solution https://mirror.codeforces.com/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://mirror.codeforces.com/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://mirror.codeforces.com/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://mirror.codeforces.com/contest/1979/submission/264433381
Could you tell what test cases you are using?
https://mirror.codeforces.com/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://mirror.codeforces.com/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://mirror.codeforces.com/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://mirror.codeforces.com/profile/aadarshsingh12345 to my another account https://mirror.codeforces.com/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.