It's me again!
Codeforces round #717 will take place on Apr/21/2021 16:35 (Moscow time), an hour early than the usual timing. It's rated for the second division, but, as usual, first division participants can take part out of competition.
The problems were created by me, and some of them are based on the Egyptian IOI qualification. I'd like to thank:
- KAN and Aleks5d for their excellent coordination.
- Akulyat, __cucumber__, Randle, Riladavin, Waley, MForest, Stefan2417, RabbitPower, and the official contestants, I guess, for testing the round.
- MikeMirzayanov for the great Codeforces and Polygon platforms.
You'll be given 5 problems, but this time you'll have 2 hours to solve them.
UPD: the scoring distribution will be 500-1000-1500-2000-2750.
UPD: the editorial.
UPD: congratulations to the winners:
Div.1:-
- LJC00118
- antontrygubO_o because he has to get a mention
- Mehrdad_Sohrabi
- zscoder
- SSRS_
Div.2:-
Good luck & Have fun :D
Codeforces : So how much contribution do you want?
mohammedehab2002 : YES
Username. xD
As a tester, I can confirm that the problems are brilliant. Also, the statements are very short and clear :)
Number theory again?)
please I hope not ... Number theory is that kind of question that if you dont know that you cant solve it prefer data structure and some problems requring some special tricks !
No offense, but how do number theory problems fall into "that kind of question that if you dont know that you cant solve it", while data structure problems don't fall into the same category?
At least in number theory, you can usually build up some intuition to solve the questions from more fundamental ideas, while data structure problems are practically unsolvable if you haven't come across the data structure before.
Granted there are some number theory problems that are basically "apply some strange formula that no one has heard of before unless they've read this paper", but those are rare in well coordinated contests.
In my opinion, both are tools, use them appropriately to solve a problem and its nice, design a problem to fit the tool (outside of educational contests) and its usually boring.
I agree, but nowadays contests usually contain only math, number theory and constructive algorithms, these kind of problems aren't unnecessary, but we aren't seeing algorithms like dfs, bfs, etc in problems with difficulty lower than 2000. I know if a problem with rating say 1700 requires such algorithms will be pointless, but if someone wants to improve their skills in these algorithms it has to be with easier problems, not difficult problems they can't solve.
I think there are a lot of problems rating under 2000 requires implementation of classic algorithms so you don't need to solve them on the official contest if you want to improve skills
Perhaps it would be better to say testing skills instead of improving, in an official contest participant tries to focus and think continuously, but if they try to solve a problem not in an official contest it probably won't have the same concentration because there is no time limit to solve it.
I ve regret for what ive said,cannot agree with you more!
Those who have agreed to this , your mind will change see first 2 3 minutes of the legend Ben Awad's opinion on CP.
https://www.youtube.com/watch?v=2ndv5-3CIrs
Weak SYSTEM tests in problem A!!!
Two consecutive mohammedehab2002 rounds. Hope I'll perform well.
More Baby Ehab on way!!!
I'm having 1504A - Déjà Vu
As a tester, I can confrim that problems are interesting and tests are strong. Also, the statements are short and clear. :)
is it another math contest instead of being a programming contest? also, are the tests as strong as they were today? PS: not trying to be satirical, these are genuine concerns I have.
CP can be better described as a discrete math puzzle solving contest than a programming contest.......
Of course, I understand that. So would you say Round #716 had very interesting questions and a very nice difficulty slope?
Classic, answering something entirely different instead of addressing the original question.
He did address your original query. You said "Is it another math contest instead of being a programming contest ?". I dont see why you are considering math and CP to be independent things. CP is more than a programming contest. Math makes it way more interesting and challenging
Programming itself is maths, what else you do with programming apart from solving big mathematical computations which you can't manually.
Unless you are writing some HTML code, no maths is used in that
Remove all the maths from programming show me what you will be left with
Weak SYSTEM tests in A!!!
How do you call not putting x x x 0
in pretests
"strong pretests"
Мама, я в телевизоре!!!
Как ты туда попал? :c
xorz again
I guess the XOR will be in this contest instead. I have hopes.
)
Great, now I have to skip one more round : )
Why would you skip it? It's unrated for you:)
hope problem b is easier !
Now the missing XOR problem will come in this round.
This time How many problems did antontrygubO_o rejected without reading them ? :D
again google forces?
Whoa, that's the shortest contest announcement I have seen in all my time here on Codeforces.....at least from among the contest announcements that I remember :) . Looking forward to a nice contest. See you at the scoreboard.
Good luck to all！
Hoping for less google problems :)
Note : An hour early of the usual timing.
In the Codeforces Round #716 announcement, it was written "This may be the most and only balanced round I've ever set.", which means Round #717 will be an unbalanced round. Hence, participate at your own risk :)
As a tester, I can confrim that problems are interesting and tests are strong. Also, the statements are short and clear. :)
bitwise and number theory again XD
please put strong test cases in pretest and special cases problem a hacked from me last round :(
XOR again?
Someone: Ehab round is tomorrow or yesterday?
Me: Yes
Can you move the start of the round to 17: 35?
No problem, anything else you need?
I have a pair for random processes ends at 16: 55, I would really like to have time for the round to start :)
Ok then I have random processes starting at 2100 utc I would really like contest to start early
Suck
Why the round isn't started yet?
Because it is tomorrow, not today.
Thanx bro. I was waiting till now. So stupid I'm.
We all do silly mistakes in life. All the best for the contest.
@mohammedehab2002 I enjoyed your yesterday's contest, Problems were good and were not having the story drama and all
Нижегородское ОПГ на тестерах
Пешки Ехаба :)
Hoping to see concise statements again and Ehab's X-OR won't be missed this time ig
I really enjoy mathy rounds, so while I can not surely assume it will be, it is still a nice round to look forward
orz
And actually why did the last problemset did not involve your favourite XOR ?
no xor last time :(...
as a tester i tested negative for covid 19 thanks to god!
.
Sorry! wrote it on the wrong page!
I believe it is a wonderful problemset :D
mohammedehab2002 Scoring Distribution?
Will the amount of question you solve change after getting the scoring distribution? so why does it matter so much
Why do you think the scoring distribution is posted hours before every contest?
Good Luck Everyone
Ramanujan mode ON
And here we have the signature XORRRRR problem for us XD
this fuckin baby again????
Didn't know registration closes for the whole contest if you're not able to register before for the contest on codeforces :(
When you begin with 500-th place and end up with 5000, because of 2-nd problem
Same here, fourth test case was cursed :(
My solution failed on 4-th test case too
partitionForces
I hate u
Why is it so hard to make word adjacent bold... spent half of the contest searching for this word
Same here, misread Problem B until close to the end of the contest
I noticed this word in B 7 minutes before the end. Barely got my 300 points (minimum score for this task) xD
/Making tricky statement such a good thing/
I didn't even notice that untill I just read your comment. Couldn't solve B due to that throught the whole round xd.
Fuck, I realized this only after reading your comment.
Wow same, didn't notice it till now XD
Noticed half hour later but fst :(
PRETEST 3 !!!!
PRETEST 4 !!!!
PRETEST 69
Main Test 16
How to solve C ?
Finding 2 Subsets with Equal Sums seems to be a popular DP problem considering that its solutions are widely available on the internet...
BTW, usage of one of these prewritten solutions is permitted by Codeforces or not?
permitted
Firstly, if sum / 2 is not possible, whether due to sum is odd or other way .The ans is zero. This can be checked using a simple do. From, now the sum is at least even. Next, the answer can be achieved by just removing a number. Let the numbers have a odd number, then you can remove that odd number and sum/2 won't be possible as sum will become odd. This actually comes out as removing as the number with minimum power of 2. As, Let that power be p. The sum = 2^p * (some number that has a odd contribution=A) and if sum / 2 is possible then it also means it is of forms = 2^p*(some number) => sum = 2^p*(some even number) means A is even. So, if we remove any number having maximum power of 2 as p. Then, above conditions won't be able to get satisfied. As now sum = 2^p*(A-odd) = 2^p*(odd). Again, the left numbers have minimum power of 2 as p, so sum / 2 = 2^p*(some number) =>sum = 2^p*(even) which is a contradiction, thus now sum / 2 won't be possible
Can u please explain this line
"The sum = 2^p * (some number that has a odd contribution=A) and if sum / 2 is possible then it also means it is of forms = 2^p*(some odd number) => sum = 2^p*(some even number) means A is even."
It means that sum will be of the form 2^p*A, then sum / 2 will be 2^p*(A / 2) . A should be even. You can prove this by contradiction. If A is odd then 2^p*A is sum ,also if sum / 2 is possible, it comes due to the numbers which have a minimum power of 2 as p, so sum / 2 = 2^p*(some number). But if, A is odd then, sum / 2 = 2^(p-1) * (odd number) which is not true as sum / 2 also has at least 2^p factor. So, sum should be of form 2^p*A, where A is even if sum / 2 is possible with numbers having minimum power of 2 as p.
ow I have got it. Thanks a lot
The contest was really brilliant in my opinion. Kudos to the author! Even after having not performed that well, you still made my day! :)
What's the point in problem E if it's OEIS-able?
http://oeis.org/A087644
Why didn't you AC then?
You can't solve for $$$n \le 10^9$$$ with the info on OEIS or anywhere I searched, and solving for small $$$n$$$ is really easy compared to the rest of the solution.
Even after finding the OEIS sequence , I don't think the problem is solved.
Well,you can just use the $$$O(nk)$$$ DP and optimize it with Lagrange Interpolation(not sure whether it is called this in English).
Can you please elaborate on how to optimize it with Lagrange interpolation?
Most people did the same mistake in B.
Checking if xor of all elements is zero or not.
nice trap
i would say question B is a good problem...
I realized today CP is not for everyone. Even after 7-8 months I can't maintain specialist. I know nobody cares and its fine but I'm really devastated ;(
Cheer Up, I too lost Expert yesterday. In my case, whenever I fall to a lower position, this motivates me to perform better in the next one and regain the same place back.
Thanks for the words. Will see how it goes.
You are not alone bro i gained expert back yesterday and losing it today :( but i will not give up (*_*) ( Fire in the eyes emoji)
u got this i believe :)
Don't give up.
Try to solve at least 1 problem you couldn't solve during this round after the contest without looking at the solution.
Read the editorial for all the problems, try to understand the solution and implement each one until they pass. Reach out to people with a higher rating for help if you can't get the solution to pass.
Will do this and see how it goes. :)
i lost expert and am currently stabilised on pupil :(
so familiar...
It's ok to lose, and it's important to keep going. Even if i am not good at this, i will still keep on trying.
I agree with you mate. But I am having a hard time giving it up.
Chin up king, dont lose hope. You just have to push yourself and solve harder problems so that you learn something new.
Important words should have been bolded in the problems like "adjacent" in problem B because due to this I was solving completely different versions of problem B and C.
Me same broo)
How to solve B? with some proof
The xor sum of the array remains the same no matter which operation you make. So if the sum is 0, then you can just combine the last n — 1 elements and your array will consist of equal elements. Otherwise, if the xor sum is k, find the shortest subarray from the start position that will have xor k, take combine all these elements into one element, and then start this process again at the next position.
B asks if you can partition the array such that each subarray has the same xor.
If you can partition it into an even number of subarrays, you can always combine some to get 2 subarrays. If odd number of subarrays, you can get 3 subarrays. Then just brute force.
me when i thought you could remove any 2 elements for b and not just any two adjecent ones....
Me just realized that...
mohammedehab2002 be like
In Problem D, I believe I'm not the only one who think of subrange as subsequence wrongly...
:)
How to solve B?
Is there any penalty if you get WA on pretest 1?
nope
Pretest 1 is special. It has no penalty if you fail on it.
Mainly because it usually means you've submitted the wrong file
I am noticing a continual upward trend in the difficulty of Div 2 contests ever since the change (around December/January) which meant that only orange and red coders could set contests. I think there is a disconnect between the people setting these contests and what level of difficulty is appropriate. Today was another unnecessarily difficult Div 2. It makes the contest a lottery of who can get A/B quickly.
I also notice increase in difficulty
Though I've attributed it to the number of cheaters that somewhat raises the bar. But I like your explanation more
Possibly a bit of both
I feel say for not being able to solve D and I even missed the registration before the contest. But I do think D is an interesting problem.
on the contrary, having difficult contests reduce the speedforces effect. it somewhat increases the probability of a gradual increase in difficulty from b to c and c to d
Theoretically that could be true, but it's not how it's playing out. What you have is a jump from very accessible questions to very difficult questions, without the middle ground that could more reasonably distinguish between people of that middle range of abilities.
He is exactly talking about people like specialists and experts.
I know what he's talking about, but that isn't how it is playing out. The jump is routinely from questions < 1400 level to > 2000 level with nothing in between. That makes for poor distinctions between anyone within that range.
This is the first time I've seen that pretests were weak enough that a pretest was added during the contest.
Screencast with commentary
A said choose different elements, means different value or different index?
different index
unclear description :(
Problems were not clear. In Problem A, it said different elements. It didn't mention if elements could be same or distinct. I considered different elements as distinct and wasted my entire time. For example, 1 4 10 6 5 5 4 if elements are considered distinct 0 1 6 13 should have been the answer. 5 5 6 4 0 5 6 9 0 1 6 13
Слабые системные тесты!!!
Problem A statement says that two chosen element must be different
Which means that the answer for the test 2 100 1 1 should be "1 1" instead of "0 2" since there is no pair of two different elements
Two elements are different if they are at different indices. That's what I thought.
That's not what the statement said though
https://www.geeksforgeeks.org/partition-a-set-into-two-subsets-such-that-the-difference-of-subset-sums-is-minimum/
MikeMirzayanov Solution of C available online
doesn't look like the same problem at all
I knew this problem. It's a classic DP problem. But how to use this in Problem C?
My solution and is taken from gfg's open avialabe article. As ypu can see in these pics. GFG's and Mine These state it was an pre released code. I got plag on this. I already wrote comment for this code ...
Weak system tests!!!
My friend's solve is not true. A. Sorry for my English
I want to know why for the third problem, if we pick the minimum element, it will be giving wrong answer?
2 3 3 4 4
Even if you remove 2, you can still partition it into 3 + 4 = 3 + 4
Consider this case:
7
2 2 2 2 2 3 5
you have 2 + 2 + 2 + 3 == 5 + 2 + 2
If you removed the first element, you will have 2 + 2 + 2 + 2 == 3 + 5
If you removed the second element also, you will have 2 + 2 + 3 == 5 + 2
For 4 4 6 6 8 16 then first set 4 4 6 8 , 16,6 now if you will remove 4 then 16,4 and 8,6,6 will be the case
Sigh. Failed problem B in the main test #16.
Anyhow, for problem C, can someone provide a test case where the following fails :
I understanding that this is failing in the last step (#4) but can't think of a test case.
I think this case may work : 7-- 16 22 16 18 24 4 32
Yup that kills it
same for B test 16: I think I found a counterexample to my code:
should be true, but my code outputs false :((((
Darn, that's likely it!
Can you please explain why the answer should have been true for this case?
These partitions are all equal: [3], [3], [3,0] (They all XOR to 3)
Ah! got it thanks
I removed all 0's from the array before I process it, and it passed systests (without any other changes). The tricky edge case here was a 0 at the end of a good array.
hm... does that really work? I'd expect it to fail for the testcase
which should be "YES"
Edit: yeah, it looks like the sys tests are weak and don't contain any test case like that... Unfortunately I'm not div 1 anymore so I can't "uphack" the solution.
Edit 2: Here's how I fixed my solution, FWIW: 113794695
You're right — all 0's would still fail my solution since the "good" variable is set to false by default. I'd need to fix by adding an additional check for an empty array and setting good to true in that case.
2 4 6 10
7
6 6 4 4 4 4 4 this one fails if we remove the smallest
In this case, the sum is odd, so no number needs to be removed
Oops my bad here 7 is the length of the array
I see now — that's a good example
Can someone explain the "smallest lexographical array" from A
"An array x is lexicographically smaller than an array y if there exists an index i such that xi<yi, and xj=yj for all 1≤j<i. Less formally, at the first index i in which they differ, xi<yi."
Wouldn't this mean that all xi<yi and all the elements before i from both arrays must be equal? Something like this: original: 5 3 8 2 new: 5 2 8 2
Not necessarily. Say we have two arrays, A and B. All that sentence really means is that if there are two arrays and they are equivalent until index i (so this can be index zero too), then array A is lexicographical smaller if, and only if, it's first element at which they are different is less than that of array B's element at that spot.
Can anybody help that in C when array is 'good' at beginning and none of its element is odd. Why are we choosing the element with smallest power of 2 to be removed from it ? Thanks!
Let us consider the following array ->
24,12,16,28.On dividing by 2, the array becomes
12,6,8,14. The subsequence sums are still even.On dividing again, we get:
8,3,4,7.You can clearly see
3and7are odd and removing either will make the already even equal subsequence sum odd. Now you know that in the original array, on removing the corresponding numbers, the remaining array sum cannot be split into two subsequences of equal sum as had it been possible, it would have been a simple multiple of 2^x of the current subsequence sums obtained on removing an odd element.Hence, the number which has the smallest power of 2 within it will be one of the fastest to reveal itself. That is why we are choosing the element with the smallest power of 2
I am not getting the part where we are seeing it by dividing the whole array by 2 again and again .. like why dividing it by 2 again and again wont change our answer
In the reduced array, if on removing some member, we manage to obtain two subsequences with equal sum s1 and s2, then the actual sequence on removing the corresponding element would have sums s1*(2^x) and s2*(2^x)
If s1! =s2, then no matter how many times you multiply both sides by 2, they will never be equal.
Thanks! Got it finally :)
Check this for an intuitive approach
In the last round A had weak pretests, now in this round B & C have weak pretests :)
Yes. Weak SYSTEM tests for A.
Failed System Test 16 in B. So, here it comes:
"The Pretests should have been StRoNgEr..."
Weaker pretests mean some opportunities for hacks.
And without hacks Codeforces rounds woudn't be so interesting.
questions are short and clear and also begiener friendly....i really enjoy the contest
Being 100% honest those are the types of problems i would expect in a educational round. Very "there is a page on geeksforgeeks for this"-esque. Not that it's necessarily bad but it's my impression
I failed task C because I printed 0-indexed solution
There was no hint at all, that it was supposed to be 1-indexed.....
The second line contains n integers a1, a2, …, an
I don't see a0 here
It is explicitly stated in the problem description and it is also clear from the examples not to mention it is a common practice.
How the hell is it "no hint"
Weak system test for c. My random solution is passing.
Can we hack solutions now?
How to solve D if we partition into subsequences rather than contiguous subarrays?
Answer for given range is maximal count of numbers with the same divisor. You can iterate over prime numbers, count how many numbers are divide by some prime number for every prefix and then using it, calculate answer how many numbers in given range are divide by some prime number. To fit in memory limit you should get answer for every range for one prime number and then calculate for another (maximalizing final result).
I don't think this is correct; this was my first thought too.
For example, given three numbers: 6 10 15, wouldn't you need three buckets (no two of them can go in the same bucket). But, any prime only divides into 2 out of the 3 numbers.
Almost 50% submission for problem "B" and "C" got rejected...It's really astonishing!!!
Really nice question set with good difficulty balance and fast editorial, that two in a row. Waiting for your next one buddy.
To not keep you waiting, the ratings updated preliminarily. In a few hours, I will remove cheaters and update the ratings again!
Can someone hack this submission? I'm doing knapsack dp n times in worst case it should TLE I guess
Can someone provide test cases for B. Still failing for pretest 4
try this array [2,2,2]
No problem with this. Verdict YES
try this array [3 2 1 3]
YES
Could you tell your logic?
Everybody missing "adjacent" in B. Me missing "at least" in B.
This missing of atleast almost ruined my contest. I was busy thinking how come it is going wrong on pretest 3 again and again, later realized the mistake.
Can we do D without binary lifting?
Good problems, good round. Hopefully such rounds will be more.
Note: the person in the meme is my friend Ahmadsm2005 in the ioi qualifications contest XD
Meme by: Nakeeb
That fridge was full of yogurt drinks. It literally never ended xD
yes you're a yogurt drink addict
as the setter of this meme give me contribution.
HELP: I really don't know what's wrong with my solution for B ;( Name the prefix-xor array as S[], then enumerate the index x (1<=x<N), and suppose S[x] to be the element of the final array. Then check it by the following way: Let i from x+1 to N, set a variable t=0, and for each time, t = t XOR a_i, and if t==S[x] then t=0, which means an interval with the same XOR has been found. And when the traverse of i is finished, the answer is "YES" only if t==0 in the end. Could you please hack my solution? Or please let me know if my description is not clear :) Thanks! My contest submission number：113743632
I guess by saying "Could you please hack my solution" you are asking for the test case where your code fails. Check the test case 2 0 ( array having two elements 2 and 0 ). Here we cannot not divide the elements into two sets having equal xor, But according to your solution, for indx i = 1, t value is zero, hence it prints "YES" But the answer is "NO".
Thank you so much! :)
Please update problem ratings.
D can be done using square root decomposition. First find for every index, the next index that is not co-prime with it. Then to answer the queries, we can use square root decomposition My solution
System MikeMirzayanov I have received a message regarding my solution coinciding with some other solution. But, during the contest, I have used the code snippet from the Leetcode discussion form. https://leetcode.com/problems/partition-equal-subset-sum/discuss/853769/01-knapsack-cpp-solution which is published on September 20, 2020. Rest all code and logic is mine. Probably the guy had used the same code. Extremely sorry for using code from the Internet. Apologies for the blunder I had. I will make sure this doesn't happen again. Extremely sorry again. Thanks
Some people in this round are plagiarized and their submissions have been skipped. However their ratings haven't been affected. Like they were not regarded for the rating change, however they should have got some negative or positive ratings according to the system formula.
Contest organizers mohammedehab2002 & MikeMirzayanov please look in this matter
I can also point out the users privately if you want
My solution and is taken from gfg's open avialabe article. As ypu can see in these pics. GFG's and Mine These state it was an pre released code. It is clearly not a voilation .