### mohammedehab2002's blog

By mohammedehab2002, 14 months ago,

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:

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:-

1. LJC00118
2. antontrygubO_o because he has to get a mention
4. zscoder
5. SSRS_

Div.2:-

Good luck & Have fun :D

• +637

 » 14 months ago, # |   +182 Codeforces : So how much contribution do you want?mohammedehab2002 : YES
•  » » 14 months ago, # ^ |   +11 Username. xD
•  » » » 14 months ago, # ^ |   0 since 1965
 » 14 months ago, # |   +106 As a tester, I can confirm that the problems are brilliant. Also, the statements are very short and clear :)
•  » » 14 months ago, # ^ |   +46 Number theory again?)
•  » » » 14 months ago, # ^ |   -49 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 !
•  » » » » 14 months ago, # ^ | ← Rev. 3 →   +127 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.
•  » » » » » 14 months ago, # ^ | ← Rev. 2 →   +22 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.
•  » » » » » » 14 months ago, # ^ |   +9 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
•  » » » » » » » 14 months ago, # ^ |   +12 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.
•  » » » » » 14 months ago, # ^ |   +19 I ve regret for what ive said,cannot agree with you more!
•  » » » » » 14 months ago, # ^ |   -29 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
•  » » 14 months ago, # ^ |   0 Weak SYSTEM tests in problem A!!!
 » 14 months ago, # |   +1 Two consecutive mohammedehab2002 rounds. Hope I'll perform well.
•  » » 14 months ago, # ^ |   0 I see you don't pray. You hope, Shelby.
 » 14 months ago, # | ← Rev. 2 →   +48 More Baby Ehab on way!!!
 » 14 months ago, # |   +121 I'm having 1504A - Déjà Vu
 » 14 months ago, # | ← Rev. 2 →   +53 As a tester, I can confrim that problems are interesting and tests are strong. Also, the statements are short and clear. :)
•  » » 14 months ago, # ^ | ← Rev. 2 →   -74 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.
•  » » » 14 months ago, # ^ |   +49 CP can be better described as a discrete math puzzle solving contest than a programming contest.......
•  » » » » 14 months ago, # ^ |   -64 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.
•  » » » » » 14 months ago, # ^ |   +22 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
•  » » » » 14 months ago, # ^ |   +24 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 thatRemove all the maths from programming show me what you will be left with
•  » » » » » 14 months ago, # ^ |   -6 print("Hello world")
•  » » 14 months ago, # ^ |   0 pretests weren't strong enough!!!!!
•  » » 14 months ago, # ^ |   0 Weak SYSTEM tests in A!!!
•  » » 14 months ago, # ^ | ← Rev. 2 →   +3 How do you call not putting x x x 0in pretests"strong pretests"
 » 14 months ago, # |   -10 More number theory problems incoming.
 » 14 months ago, # |   -25 Another mathforces i guess.
 » 14 months ago, # |   0 xorz again
 » 14 months ago, # |   +22 I guess the XOR will be in this contest instead. I have hopes.
 » 14 months ago, # |   0 Once again we are going to enjoy a dashboard of 5 problems.But the time is 15 minutes lesser than the last contest!!!
 » 14 months ago, # |   +20
 » 14 months ago, # | ← Rev. 6 →   +60 ![ ]()
 » 14 months ago, # |   -41 Great, now I have to skip one more round : )
•  » » 14 months ago, # ^ |   +38 Why would you skip it? It's unrated for you:)
 » 14 months ago, # |   +5 hope problem b is easier !
 » 14 months ago, # |   +13 Now the missing XOR problem will come in this round.
•  » » 14 months ago, # ^ |   0 GOD OR WHAT???
 » 14 months ago, # |   -25 Math problems again ... i love those
 » 14 months ago, # |   0 This time How many problems did antontrygubO_o rejected without reading them ? :D
 » 14 months ago, # |   +41 again google forces?
 » 14 months ago, # |   +6 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.
 » 14 months ago, # |   0 Good luck to all！
 » 14 months ago, # |   0 Hoping for less google problems :)
 » 14 months ago, # |   0 His announcements are just as precise as the problem statements. Loved it :D
 » 14 months ago, # |   0 Note : An hour early of the usual timing.
 » 14 months ago, # |   +50 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 :)
 » 14 months ago, # |   +9 As a tester, I can confrim that problems are interesting and tests are strong. Also, the statements are short and clear. :)
 » 14 months ago, # |   0 Previous Round was amazing learnt few new things.Hope to Learn new things this round also. BTW why timming is 7 pm from last 2 contests.
 » 14 months ago, # |   +2 bitwise and number theory again XD
 » 14 months ago, # |   +3 please put strong test cases in pretest and special cases problem a hacked from me last round :(
 » 14 months ago, # |   -18 XOR again?
 » 14 months ago, # | ← Rev. 8 →   +2
•  » » 14 months ago, # ^ | ← Rev. 2 →   0 I'm making a semi-ellipse with my rating graph :(
 » 14 months ago, # | ← Rev. 2 →   +284 Someone: Ehab round is tomorrow or yesterday?Me: Yes
•  » » 14 months ago, # ^ |   0 petition to send ehab to rehab
 » 14 months ago, # |   -22 Can you move the start of the round to 17: 35?
•  » » 14 months ago, # ^ |   +167 No problem, anything else you need?
•  » » » 14 months ago, # ^ |   -42 I have a pair for random processes ends at 16: 55, I would really like to have time for the round to start :)
•  » » » » 14 months ago, # ^ | ← Rev. 4 →   +71 Ok then I have random processes starting at 2100 utc I would really like contest to start early
•  » » » » » 14 months ago, # ^ |   -40 Suck
 » 14 months ago, # |   0 Why the round isn't started yet?
•  » » 14 months ago, # ^ |   +3 Because it is tomorrow, not today.
•  » » » 14 months ago, # ^ |   +55 Thanx bro. I was waiting till now. So stupid I'm.
•  » » » » 14 months ago, # ^ |   +2 We all do silly mistakes in life. All the best for the contest.
 » 14 months ago, # |   -27 Again on the day of CSK's game..The only good thing is 1 hr early start..
 » 14 months ago, # |   0 Really Excited :)
 » 14 months ago, # |   -38 why did you gave 15 minutes extra last time and not this time? any specific reason or did u applied a random function yesterday to decide the amount of extra time?.... p.s. — pun intended
 » 14 months ago, # |   +14 @mohammedehab2002 I enjoyed your yesterday's contest, Problems were good and were not having the story drama and all
 » 14 months ago, # | ← Rev. 2 →   +1 Hoping to see concise statements again and Ehab's X-OR won't be missed this time ig
 » 14 months ago, # |   0 I really enjoy mathy rounds, so while I can not surely assume it will be, it is still a nice round to look forward
 » 14 months ago, # |   0 Please update the scoring distribution :)
 » 14 months ago, # |   0 orz
 » 14 months ago, # |   +15 And actually why did the last problemset did not involve your favourite XOR ?
 » 14 months ago, # |   +3 no xor last time :(...
 » 14 months ago, # |   +56 as a tester i tested negative for covid 19 thanks to god!
 » 14 months ago, # | ← Rev. 3 →   +22 .
•  » » 14 months ago, # ^ |   +15 Sorry! wrote it on the wrong page!
 » 14 months ago, # | ← Rev. 2 →   0 I believe it is a wonderful problemset :D
 » 14 months ago, # | ← Rev. 2 →   +14 mohammedehab2002 Scoring Distribution?
•  » » 14 months ago, # ^ |   -31 Will the amount of question you solve change after getting the scoring distribution? so why does it matter so much
•  » » » 14 months ago, # ^ |   +6 Why do you think the scoring distribution is posted hours before every contest?
 » 14 months ago, # |   +6 Good Luck Everyone
 » 14 months ago, # |   0 This contest seems to be difficult.Good luck to everyone!
 » 14 months ago, # |   0 I was not able to participate in round 716 but here you comes again. What a surprise.Thank you
 » 14 months ago, # |   +19 Ramanujan mode ON
 » 14 months ago, # |   +8 And here we have the signature XORRRRR problem for us XD
 » 14 months ago, # |   +25 this fuckin baby again????
 » 14 months ago, # |   0 Didn't know registration closes for the whole contest if you're not able to register before for the contest on codeforces :(
•  » » 14 months ago, # ^ |   0 Most of the times there is an extra registration window which opens 5-10 minutes after the contest starts and lasts around 15 minutes or so. So, the ones who missed it earlier can register then. But, not sure about this one.
 » 14 months ago, # |   0 When you begin with 500-th place and end up with 5000, because of 2-nd problem
•  » » 14 months ago, # ^ |   0 Same here, fourth test case was cursed :(
•  » » » 14 months ago, # ^ |   0 My solution failed on 4-th test case too
•  » » » » 14 months ago, # ^ |   0 Yeah, the second problem was a little difficult though.
 » 14 months ago, # |   +4 partitionForces
 » 14 months ago, # |   0 Wrong answer forces
 » 14 months ago, # |   0 I hate u
 » 14 months ago, # |   +66 Why is it so hard to make word adjacent bold... spent half of the contest searching for this word
•  » » 14 months ago, # ^ |   +9 Same here, misread Problem B until close to the end of the contest
•  » » 14 months ago, # ^ | ← Rev. 2 →   +8 I noticed this word in B 7 minutes before the end. Barely got my 300 points (minimum score for this task) xD
•  » » 14 months ago, # ^ |   +2 /Making tricky statement such a good thing/
•  » » 14 months ago, # ^ |   +12 I didn't even notice that untill I just read your comment. Couldn't solve B due to that throught the whole round xd.
•  » » 14 months ago, # ^ |   +13 Fuck, I realized this only after reading your comment.
•  » » 14 months ago, # ^ |   +13 Wow same, didn't notice it till now XD
•  » » 14 months ago, # ^ | ← Rev. 2 →   0 Noticed half hour later but fst :(
 » 14 months ago, # |   0 PRETEST 3 !!!!
•  » » 14 months ago, # ^ |   +1 PRETEST 4 !!!!
•  » » 14 months ago, # ^ |   0 PRETEST 9
•  » » 14 months ago, # ^ |   +4 PRETEST 69
•  » » 14 months ago, # ^ |   +20 Main Test 16
 » 14 months ago, # |   +6 How to solve C ?
•  » » 14 months ago, # ^ | ← Rev. 2 →   0 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?
•  » » » 14 months ago, # ^ |   +6 permitted
•  » » 14 months ago, # ^ | ← Rev. 24 →   0 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
•  » » » 14 months ago, # ^ | ← Rev. 2 →   +3 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."
•  » » » » 14 months ago, # ^ | ← Rev. 3 →   0 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.
•  » » » » » 14 months ago, # ^ |   +3 ow I have got it. Thanks a lot
•  » » » 14 months ago, # ^ |   0 could you please explain it with some examples, didn't get it.
 » 14 months ago, # |   0 The contest was really brilliant in my opinion. Kudos to the author! Even after having not performed that well, you still made my day! :)
 » 14 months ago, # |   -15 What's the point in problem E if it's OEIS-able?http://oeis.org/A087644
•  » » 14 months ago, # ^ |   +49 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.
•  » » » 14 months ago, # ^ |   0 hey mohammedehab2002, although I didn't farewell today please do give some thoughts on preparing such rounds once in 2 months atleast with some more coordinators to lessen your share of work too. The round I think was great.
•  » » 14 months ago, # ^ |   +1 Even after finding the OEIS sequence , I don't think the problem is solved.
•  » » » 14 months ago, # ^ |   +16 Well,you can just use the $O(nk)$ DP and optimize it with Lagrange Interpolation(not sure whether it is called this in English).
•  » » » » 14 months ago, # ^ |   0 Can you please elaborate on how to optimize it with Lagrange interpolation?
 » 14 months ago, # |   +9 Most people did the same mistake in B.Checking if xor of all elements is zero or not.nice trap
 » 14 months ago, # |   +3 i would say question B is a good problem...
•  » » 14 months ago, # ^ |   0 how do u solve B?
•  » » » 14 months ago, # ^ |   0 i failed to solve it, so i think it is a good problem. The word adjacent is thought to be very important, and i didn't notice it for 2 hours. After studying __fishingprince__'s submission, my understanding comes as follow:if xor(all)==0 puts("YES") else if there exists 1<=i
 » 14 months ago, # |   +20 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 ;(
•  » » 14 months ago, # ^ |   +5 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.
•  » » » 14 months ago, # ^ |   +1 Thanks for the words. Will see how it goes.
•  » » » » 14 months ago, # ^ | ← Rev. 4 →   +3 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)
•  » » 14 months ago, # ^ |   +4 u got this i believe :)
•  » » 14 months ago, # ^ |   +9 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.
•  » » » 14 months ago, # ^ |   +8 Will do this and see how it goes. :)
•  » » 14 months ago, # ^ |   +3 i lost expert and am currently stabilised on pupil :(
•  » » 14 months ago, # ^ |   +3 so familiar...
•  » » 14 months ago, # ^ |   +3 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.
•  » » 14 months ago, # ^ |   0 I agree with you mate. But I am having a hard time giving it up.
•  » » 14 months ago, # ^ |   0 Chin up king, dont lose hope. You just have to push yourself and solve harder problems so that you learn something new.
 » 14 months ago, # |   +16 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.
•  » » 14 months ago, # ^ |   +8 Me same broo)
 » 14 months ago, # |   0 How to solve B? with some proof
•  » » 14 months ago, # ^ |   +1 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.
•  » » » 14 months ago, # ^ |   0 Wow, seriously.. for me this is like how someone should have thought.
•  » » 14 months ago, # ^ |   +8 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.
•  » » » 14 months ago, # ^ |   0 Exemplary bruteforce....
 » 14 months ago, # |   +7 me when i thought you could remove any 2 elements for b and not just any two adjecent ones....
•  » » 14 months ago, # ^ |   +3 Me just realized that...
 » 14 months ago, # |   +28 mohammedehab2002 be like
 » 14 months ago, # |   +9 In Problem D, I believe I'm not the only one who think of subrange as subsequence wrongly...
•  » » 14 months ago, # ^ |   +1 :)
 » 14 months ago, # |   0 How to solve B?
 » 14 months ago, # |   0 Is there any penalty if you get WA on pretest 1?
•  » » 14 months ago, # ^ | ← Rev. 2 →   +9 nopePretest 1 is special. It has no penalty if you fail on it.Mainly because it usually means you've submitted the wrong file
 » 14 months ago, # | ← Rev. 3 →   +22 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.
•  » » 14 months ago, # ^ | ← Rev. 2 →   +6 I also notice increase in difficultyThough I've attributed it to the number of cheaters that somewhat raises the bar. But I like your explanation more
•  » » » 14 months ago, # ^ |   0 Possibly a bit of both
•  » » 14 months ago, # ^ |   +3 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.
•  » » 14 months ago, # ^ | ← Rev. 2 →   0 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
•  » » » 14 months ago, # ^ |   +1 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.
•  » » » » 14 months ago, # ^ |   0 He is exactly talking about people like specialists and experts.
•  » » » » » 14 months ago, # ^ |   +13 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.
 » 14 months ago, # |   +62 This is the first time I've seen that pretests were weak enough that a pretest was added during the contest.
 » 14 months ago, # |   +28
•  » » 14 months ago, # ^ |   -6 Um_nik ORZ!!!!!!
 » 14 months ago, # |   +4 A said choose different elements, means different value or different index?
•  » » 14 months ago, # ^ |   0 different index
•  » » » 14 months ago, # ^ |   0 unclear description :(
 » 14 months ago, # |   +7 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
 » 14 months ago, # |   0 Слабые системные тесты!!!
 » 14 months ago, # |   +1 Problem A statement says that two chosen element must be differentWhich 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
•  » » 14 months ago, # ^ |   0 Two elements are different if they are at different indices. That's what I thought.
•  » » » 14 months ago, # ^ |   0 That's not what the statement said though
•  » » » » 14 months ago, # ^ |   0 Well Yeah.
 » 14 months ago, # | ← Rev. 2 →   -36
•  » » 14 months ago, # ^ |   +25 doesn't look like the same problem at all
•  » » 14 months ago, # ^ |   0 I knew this problem. It's a classic DP problem. But how to use this in Problem C?
•  » » 14 months ago, # ^ |   0 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 ...
 » 14 months ago, # |   +2 Weak system tests!!!
•  » » 14 months ago, # ^ | ← Rev. 2 →   0 My friend's solve is not true. A. Sorry for my English
 » 14 months ago, # |   +6 I want to know why for the third problem, if we pick the minimum element, it will be giving wrong answer?
•  » » 14 months ago, # ^ | ← Rev. 2 →   +4 2 3 3 4 4Even if you remove 2, you can still partition it into 3 + 4 = 3 + 4
•  » » 14 months ago, # ^ |   0 Consider this case:72 2 2 2 2 3 5you have 2 + 2 + 2 + 3 == 5 + 2 + 2If you removed the first element, you will have 2 + 2 + 2 + 2 == 3 + 5If you removed the second element also, you will have 2 + 2 + 3 == 5 + 2
•  » » 14 months ago, # ^ |   +3 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
•  » » 14 months ago, # ^ |   0 6 2 2 2 2 3 3 
 » 14 months ago, # | ← Rev. 3 →   -8 Sigh. Failed problem B in the main test #16.Anyhow, for problem C, can someone provide a test case where the following fails : Check if we can construct sum/2 using some of the elements. If not, answer is 0. Check if sum is odd. If so, answer is 0. Check if there's an odd element. If so, it can be removed to make the sum odd. Answer is 1. Remove the smallest even element. In which case answer is 1. I understanding that this is failing in the last step (#4) but can't think of a test case.
•  » » 14 months ago, # ^ | ← Rev. 2 →   0 I think this case may work : 7-- 16 22 16 18 24 4 32
•  » » » 14 months ago, # ^ |   0 Yup that kills it
•  » » 14 months ago, # ^ | ← Rev. 3 →   0 same for B test 16: I think I found a counterexample to my code: 1 4 3 3 3 0 should be true, but my code outputs false :((((
•  » » » 14 months ago, # ^ |   0 Darn, that's likely it!
•  » » » 14 months ago, # ^ |   0 Can you please explain why the answer should have been true for this case?
•  » » » » 14 months ago, # ^ |   +1 These partitions are all equal: [3], [3], [3,0] (They all XOR to 3)
•  » » » » » 14 months ago, # ^ |   0 Ah! got it thanks
•  » » » » » 14 months ago, # ^ |   0 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.
•  » » » » » » 14 months ago, # ^ | ← Rev. 3 →   0 hm... does that really work? I'd expect it to fail for the testcase 1 3 0 0 0 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
•  » » » » » » » 14 months ago, # ^ |   0 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.
•  » » 14 months ago, # ^ | ← Rev. 2 →   0 4,10,12,12,14 remove smallest element 4 is not enough
•  » » 14 months ago, # ^ |   0 2 4 6 10
•  » » » 14 months ago, # ^ |   0 no number needs to be removed, 22/2 = 11 is not reachable
•  » » 14 months ago, # ^ | ← Rev. 3 →   0 76 6 4 4 4 4 4 this one fails if we remove the smallest
•  » » » 14 months ago, # ^ |   0 In this case, the sum is odd, so no number needs to be removed
•  » » » » 14 months ago, # ^ |   0 Oops my bad here 7 is the length of the array
•  » » » » » 14 months ago, # ^ |   0 I see now — that's a good example
•  » » 14 months ago, # ^ | ← Rev. 2 →   0 The solution is like an extension from step 3. After checking condition 1 and 2, we know at least a number has to be removed. If odd element exists -> remove it and doneNow, create a new array which all new elements are doubled from the original array. (new_array[i] = 2 * array[i] for 1 <= i <=n) For this new_array, there is no odd element but index of the element to remove is the same. (For example, arr = [4,5,6] and new_arr = [8,10,12])So from this extension, we know we are not just looking for an odd element. We are looking for a element with smallest i such that (1<
 » 14 months ago, # |   -8 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
•  » » 14 months ago, # ^ |   0 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.
 » 14 months ago, # |   -8 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!
•  » » 14 months ago, # ^ |   +1 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 3 and 7 are 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
•  » » » 14 months ago, # ^ |   0 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
•  » » » » 14 months ago, # ^ |   +1 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.
•  » » » » » 14 months ago, # ^ |   0 Thanks! Got it finally :)
•  » » 14 months ago, # ^ |   0 Check this for an intuitive approach
 » 14 months ago, # |   0 In the last round A had weak pretests, now in this round B & C have weak pretests :)
•  » » 14 months ago, # ^ |   0 Yes. Weak SYSTEM tests for A.
 » 14 months ago, # |   -15 Failed System Test 16 in B. So, here it comes: Spoiler"The Pretests should have been StRoNgEr..."
•  » » 14 months ago, # ^ |   +15 Weaker pretests mean some opportunities for hacks.And without hacks Codeforces rounds woudn't be so interesting.
 » 14 months ago, # |   -10 mohammedehab2002 In the first problem it says choose 2 different elements doesn't that mean it has to be 2 distinct elements(both of them are not equal) (I considered that only and solved it :/) PROBLEM WAS UNCLEAR WHICH IS QUITE UNFAIR
 » 14 months ago, # |   +7 questions are short and clear and also begiener friendly....i really enjoy the contest
 » 14 months ago, # |   0 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
 » 14 months ago, # |   -17 I failed task C because I printed 0-indexed solutionThere was no hint at all, that it was supposed to be 1-indexed.....
•  » » 14 months ago, # ^ |   0 The second line contains n integers a1, a2, …, anI don't see a0 here
•  » » 14 months ago, # ^ | ← Rev. 2 →   0 you should have atleast checked sample test case
•  » » 14 months ago, # ^ |   +10 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"
 » 14 months ago, # |   0 Weak system test for c. My random solution is passing.
 » 14 months ago, # |   0 Can we hack solutions now?
•  » » 14 months ago, # ^ |   0 Hacking is available during the contest in Div 1,2
 » 14 months ago, # | ← Rev. 2 →   -9 113719312 passed system test But my submission will give wrong answer on the test- INPUT 1 3 1 1 0 1 OUTPUT 1 0 1 (which is wrong) O O 2 (correct ouput) 
•  » » 14 months ago, # ^ |   0 Where is the value of k
 » 14 months ago, # |   +15 How to solve D if we partition into subsequences rather than contiguous subarrays?
•  » » 14 months ago, # ^ |   -10 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).
•  » » » 14 months ago, # ^ |   +10 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.
 » 14 months ago, # |   0 Stormy Dashboard!!!A lot of "WA" in problem "B" and "C" during system test. I could not dare to score during contest time. I am awaiting for the next round.I hope, at least I will be able to score in the next round,,, Insha-Allah.
•  » » 14 months ago, # ^ |   0 you will definitely be going to score well in the next contest :)
 » 14 months ago, # |   +1 Almost 50% submission for problem "B" and "C" got rejected...It's really astonishing!!!
 » 14 months ago, # |   0 Sorry for being annoying; problem C was on GeeksForGeeks. Here is my submission, with a little difference: 113799277.
 » 14 months ago, # |   +27
 » 14 months ago, # |   0 Really nice question set with good difficulty balance and fast editorial, that two in a row. Waiting for your next one buddy.
 » 14 months ago, # |   -9 Problem C was much easier than problem B
 » 14 months ago, # |   +25 To not keep you waiting, the ratings updated preliminarily. In a few hours, I will remove cheaters and update the ratings again!
 » 14 months ago, # |   0 Can someone hack this submission? I'm doing knapsack dp n times in worst case it should TLE I guess
 » 14 months ago, # |   0 Life Lesson From Problem B:Babies make your life harder lol.
•  » » 14 months ago, # ^ |   0 True as fuck xD
 » 14 months ago, # |   0 Can someone provide test cases for B. Still failing for pretest 4
•  » » 14 months ago, # ^ |   0 try this array [2,2,2]
•  » » » 14 months ago, # ^ |   0 No problem with this. Verdict YES
•  » » » » 14 months ago, # ^ |   0 Can you tell what is your logic?
•  » » » » » 14 months ago, # ^ |   0 Only considering subsets of either 2 or 3. If xor of array is 0 then Yes. Else we can check for xor prefix and suffix for the array. If present then YES else No.
•  » » » » » » 14 months ago, # ^ |   0 how are you checking for subset of size 3?
•  » » » » 14 months ago, # ^ |   0 try this array [3 2 1 3]
•  » » » » » 14 months ago, # ^ |   0 YES
•  » » » » » » 14 months ago, # ^ |   0 Could you tell your logic?
 » 14 months ago, # |   +1 Everybody missing "adjacent" in B. Me missing "at least" in B.
•  » » 14 months ago, # ^ |   0 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.
 » 14 months ago, # | ← Rev. 2 →   0 can someone explain what is wrong with my submission for problem B? I am getting wrong answer on pretest 4 113812521 edit: found the bug
 » 14 months ago, # |   0 Can we do D without binary lifting?
 » 14 months ago, # |   +3 Good problems, good round. Hopefully such rounds will be more.
 » 14 months ago, # |   +22 Note: the person in the meme is my friend Ahmadsm2005 in the ioi qualifications contest XDMeme by: Nakeeb
•  » » 14 months ago, # ^ |   +5 That fridge was full of yogurt drinks. It literally never ended xD
•  » » » 14 months ago, # ^ |   +7 yes you're a yogurt drink addict
•  » » 14 months ago, # ^ |   0 ehab ❤ XOR — Still a better love story than Twilight
•  » » 14 months ago, # ^ |   +11 as the setter of this meme give me contribution.
 » 14 months ago, # |   0 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
•  » » 14 months ago, # ^ |   0 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".
•  » » » 14 months ago, # ^ |   0 Thank you so much! :)
 » 14 months ago, # |   0 this timing of contest is amazing , just right time to start and finished before dinner really enjoying this :}
 » 14 months ago, # |   +3
 » 14 months ago, # |   0 Please update problem ratings.
•  » » 14 months ago, # ^ |   0 I'm quite new in codeforces. Good to know I'm not the only one facing this issue. They haven't updated the ratings yet
 » 14 months ago, # |   0 Could anyone explain, why dividing elements by 2 until we get an odd number works?
 » 14 months ago, # | ← Rev. 2 →   0 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
 » 14 months ago, # | ← Rev. 2 →   0 deleted
 » 14 months ago, # |   0 MikeMirzayanov The system message says my solution coincides with 4 more members even when I don't know them, my submission is 113778444 and I took a part of code from GeeksForGeeks which is completely valid according to the codeforces rules. Please have a look into this. I don't know how my code matches with so many people.
 » 14 months ago, # |   0 I have received a message regarding leakage of code but I want to assure that its not true. For my solution 113742914 for the problem 1516C I have taken the code of "equal sum partition" published on "geeks for geeks" website, I have also attached the link (https://www.geeksforgeeks.org/partition-problem-dp-18/) you could verify yourself. This code has been published a long time ago, I have taken this code snippet and rest of the code is all mine. So please see to it and increase my rating again.Also I want to assure that no code has been leaked by me till now. I have been on codeforces for a long time now and know about what to do and what to not while giving a contest. And I do my code on Vscode and then after checking it on Vscode I submit that code directly to codeforces so there is no chance of leakage from my end that I can assure. So please give me my rating back, after so much hardwork I reached "Pupil" and I don't want to reduce my rating for no reason
 » 14 months ago, # |   0 MikeMirzayanov I have received a message regarding Copying & Coincidence of code but I want to tell you that its not true. In my solution 113770742 for the problem 1516C I have taken the equal partition of array code from Geeks For Geeks I am also mentioning the link below you could examine yourself and verify the same(https://www.geeksforgeeks.org/partition-problem-dp-18/) This code has been published a long time ago, I have taken this code snippet and rest of the code is all mine. This is a false positive So please see to it and increase my rating again. and remove my warning
 » 14 months ago, # | ← Rev. 3 →   +3 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
 » 14 months ago, # | ← Rev. 3 →   0 System I have received a message regarding coincidence of my solution 113768019 for the problem 1516C. For this I took the code of "equal sum partition" published on "geeks for geeks" website, the link is here (https://www.geeksforgeeks.org/partition-problem-dp-18/) . This code has been published a long time ago, and I have used this code snippet in a function but the logic and other code part is all mine. Kindly see to the matter.
 » 14 months ago, # | ← Rev. 2 →   0 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 matterI can also point out the users privately if you want
 » 14 months ago, # |   0 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 .
 » 14 months ago, # |   0 My solution was taken from GeeksforGeeks avialabe article. I believe that is ot a violation of the rules.
 » 14 months ago, # |   0 MikeMirzayanov I recieved a a message regarding coincidence of my solution 113766317 for the problem 1516C. For the problem i took the code from "Partition problem" form GeeksforGeeks. The link is https://www.geeksforgeeks.org/partition-problem-dp-18/ . I believe using a source published before the contest is not a violation of codeforces policies. I have never leaked any code at all .
 » 14 months ago, # |   0 Hello MikeMirzayanov I just saw few cases got added to my solution (like the test 42nd) and to others it wasn't, the test case added exceeded the time limit on my solution and then I tried uploading someone else's solution after the contest which is different from me it still showed time limit exceeded but in the contest's leaderboard it showed accepted but mine got failed, can anyone tell why this happened. My submission is here 113778444 and the solution I checked to see is here 113763434