mohammedehab2002's blog

Codeforces Round #717 (Div.2)
By mohammedehab2002, 4 years ago, In English

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
  3. Mehrdad_Sohrabi
  4. zscoder
  5. SSRS_

Div.2:-

  1. ShuijunDainifei
  2. Dolodu123
  3. alya_wow
  4. PolarFlea
  5. Kazaoka_Mari

Good luck & Have fun :D

  • Vote: I like it
  • +637
  • Vote: I do not like it

Comments Comments (223)
| Write comment?
»
4 years ago, # |
  Vote: I like it +182 Vote: I do not like it

Codeforces : So how much contribution do you want?

mohammedehab2002 : YES

→ Reply
»
4 years ago, # |
  Vote: I like it +106 Vote: I do not like it

As a tester, I can confirm that the problems are brilliant. Also, the statements are very short and clear :)

→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it +46 Vote: I do not like it

    Number theory again?)

    → Reply
    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it -49 Vote: I do not like it

      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 !

      → Reply
      • »
        »
        »
        »
        4 years ago, # ^ |
        ← Rev. 3   Vote: I like it +127 Vote: I do not like it

        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.

        → Reply
        • »
          »
          »
          »
          »
          4 years ago, # ^ |
          ← Rev. 2   Vote: I like it +22 Vote: I do not like it

          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.

          → Reply
          • »
            »
            »
            »
            »
            »
            4 years ago, # ^ |
              Vote: I like it +9 Vote: I do not like it

            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

            → Reply
            • »
              »
              »
              »
              »
              »
              »
              4 years ago, # ^ |
                Vote: I like it +12 Vote: I do not like it

              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.

              → Reply
        • »
          »
          »
          »
          »
          4 years ago, # ^ |
            Vote: I like it +19 Vote: I do not like it

          I ve regret for what ive said,cannot agree with you more!

          → Reply
        • »
          »
          »
          »
          »
          4 years ago, # ^ |
            Vote: I like it -29 Vote: I do not like it

          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

          → Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Weak SYSTEM tests in problem A!!!

    → Reply
»
4 years ago, # |
  Vote: I like it +1 Vote: I do not like it

Two consecutive mohammedehab2002 rounds. Hope I'll perform well.

→ Reply
»
4 years ago, # |
← Rev. 2   Vote: I like it +48 Vote: I do not like it

More Baby Ehab on way!!!

→ Reply
»
4 years ago, # |
  Vote: I like it +121 Vote: I do not like it

I'm having 1504A - Déjà Vu

→ Reply
»
4 years ago, # |
← Rev. 2   Vote: I like it +53 Vote: I do not like it

As a tester, I can confrim that problems are interesting and tests are strong. Also, the statements are short and clear. :)

→ Reply
  • »
    »
    4 years ago, # ^ |
    ← Rev. 2   Vote: I like it -74 Vote: I do not like it

    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.

    → Reply
    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it +49 Vote: I do not like it

      CP can be better described as a discrete math puzzle solving contest than a programming contest.......

      → Reply
      • »
        »
        »
        »
        4 years ago, # ^ |
          Vote: I like it -64 Vote: I do not like it

        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.

        → Reply
        • »
          »
          »
          »
          »
          4 years ago, # ^ |
            Vote: I like it +22 Vote: I do not like it

          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

          → Reply
      • »
        »
        »
        »
        4 years ago, # ^ |
          Vote: I like it +24 Vote: I do not like it

        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

        → Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Weak SYSTEM tests in A!!!

    → Reply
  • »
    »
    4 years ago, # ^ |
    ← Rev. 2   Vote: I like it +3 Vote: I do not like it

    How do you call not putting x x x 0

    in pretests

    "strong pretests"

    → Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

xorz again

→ Reply
»
4 years ago, # |
  Vote: I like it +22 Vote: I do not like it

I guess the XOR will be in this contest instead. I have hopes.

→ Reply
»
4 years ago, # |
  Vote: I like it +20 Vote: I do not like it

→ Reply
»
4 years ago, # |
← Rev. 6   Vote: I like it +60 Vote: I do not like it

![ ](Hi)

→ Reply
»
4 years ago, # |
  Vote: I like it -41 Vote: I do not like it

Great, now I have to skip one more round : )

→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it +38 Vote: I do not like it

    Why would you skip it? It's unrated for you:)

    → Reply
»
4 years ago, # |
  Vote: I like it +5 Vote: I do not like it

hope problem b is easier !

→ Reply
»
4 years ago, # |
  Vote: I like it +13 Vote: I do not like it

Now the missing XOR problem will come in this round.

→ Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

This time How many problems did antontrygubO_o rejected without reading them ? :D

→ Reply
»
4 years ago, # |
  Vote: I like it +41 Vote: I do not like it

again google forces?

→ Reply
»
4 years ago, # |
  Vote: I like it +6 Vote: I do not like it

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.

→ Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Good luck to all！

→ Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Hoping for less google problems :)

→ Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Note : An hour early of the usual timing.

→ Reply
»
4 years ago, # |
  Vote: I like it +50 Vote: I do not like it

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

→ Reply
»
4 years ago, # |
  Vote: I like it +9 Vote: I do not like it

As a tester, I can confrim that problems are interesting and tests are strong. Also, the statements are short and clear. :)

→ Reply
»
4 years ago, # |
  Vote: I like it +2 Vote: I do not like it

bitwise and number theory again XD

→ Reply
»
4 years ago, # |
  Vote: I like it +3 Vote: I do not like it

please put strong test cases in pretest and special cases problem a hacked from me last round :(

→ Reply
»
4 years ago, # |
  Vote: I like it -18 Vote: I do not like it

XOR again?

→ Reply
»
4 years ago, # |
← Rev. 8   Vote: I like it +2 Vote: I do not like it

→ Reply
»
4 years ago, # |
← Rev. 2   Vote: I like it +284 Vote: I do not like it

Someone: Ehab round is tomorrow or yesterday?

Me: Yes

→ Reply
»
4 years ago, # |
  Vote: I like it -22 Vote: I do not like it

Can you move the start of the round to 17: 35?

→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it +167 Vote: I do not like it

    No problem, anything else you need?

    → Reply
    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it -42 Vote: I do not like it

      I have a pair for random processes ends at 16: 55, I would really like to have time for the round to start :)

      → Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Why the round isn't started yet?

→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    Because it is tomorrow, not today.

    → Reply
    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it +55 Vote: I do not like it

      Thanx bro. I was waiting till now. So stupid I'm.

      → Reply
      • »
        »
        »
        »
        4 years ago, # ^ |
          Vote: I like it +2 Vote: I do not like it

        We all do silly mistakes in life. All the best for the contest.

        → Reply
»
4 years ago, # |
  Vote: I like it +14 Vote: I do not like it

@mohammedehab2002 I enjoyed your yesterday's contest, Problems were good and were not having the story drama and all

→ Reply
»
4 years ago, # |
← Rev. 2   Vote: I like it +1 Vote: I do not like it

Hoping to see concise statements again and Ehab's X-OR won't be missed this time ig

→ Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

I really enjoy mathy rounds, so while I can not surely assume it will be, it is still a nice round to look forward

→ Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

orz

→ Reply
»
4 years ago, # |
  Vote: I like it +15 Vote: I do not like it

And actually why did the last problemset did not involve your favourite XOR ?

→ Reply
»
4 years ago, # |
  Vote: I like it +3 Vote: I do not like it

no xor last time :(...

→ Reply
»
4 years ago, # |
  Vote: I like it +56 Vote: I do not like it

as a tester i tested negative for covid 19 thanks to god!

→ Reply
»
4 years ago, # |
← Rev. 3   Vote: I like it +22 Vote: I do not like it

.

→ Reply
»
4 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

I believe it is a wonderful problemset :D

→ Reply
»
4 years ago, # |
← Rev. 2   Vote: I like it +14 Vote: I do not like it

mohammedehab2002 Scoring Distribution?

→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it -31 Vote: I do not like it

    Will the amount of question you solve change after getting the scoring distribution? so why does it matter so much

    → Reply
    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it +6 Vote: I do not like it

      Why do you think the scoring distribution is posted hours before every contest?

      → Reply
»
4 years ago, # |
  Vote: I like it +6 Vote: I do not like it

Good Luck Everyone

→ Reply
»
4 years ago, # |
  Vote: I like it +19 Vote: I do not like it

Ramanujan mode ON

→ Reply
»
4 years ago, # |
  Vote: I like it +8 Vote: I do not like it

And here we have the signature XORRRRR problem for us XD

→ Reply
»
4 years ago, # |
  Vote: I like it +25 Vote: I do not like it

this fuckin baby again????

→ Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Didn't know registration closes for the whole contest if you're not able to register before for the contest on codeforces :(

→ Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

When you begin with 500-th place and end up with 5000, because of 2-nd problem

→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Same here, fourth test case was cursed :(

    → Reply
    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      My solution failed on 4-th test case too

      → Reply
»
4 years ago, # |
  Vote: I like it +4 Vote: I do not like it

partitionForces

→ Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

I hate u

→ Reply
»
4 years ago, # |
  Vote: I like it +66 Vote: I do not like it

Why is it so hard to make word adjacent bold... spent half of the contest searching for this word

→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it +9 Vote: I do not like it

    Same here, misread Problem B until close to the end of the contest

    → Reply
  • »
    »
    4 years ago, # ^ |
    ← Rev. 2   Vote: I like it +8 Vote: I do not like it

    I noticed this word in B 7 minutes before the end. Barely got my 300 points (minimum score for this task) xD

    → Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it +2 Vote: I do not like it

    /Making tricky statement such a good thing/

    → Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it +12 Vote: I do not like it

    I didn't even notice that untill I just read your comment. Couldn't solve B due to that throught the whole round xd.

    → Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it +13 Vote: I do not like it

    Fuck, I realized this only after reading your comment.

    → Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it +13 Vote: I do not like it

    Wow same, didn't notice it till now XD

    → Reply
  • »
    »
    4 years ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    Noticed half hour later but fst :(

    → Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

PRETEST 3 !!!!

→ Reply
»
4 years ago, # |
  Vote: I like it +6 Vote: I do not like it

How to solve C ?

→ Reply
  • »
    »
    4 years ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    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?

    → Reply
  • »
    »
    4 years ago, # ^ |
    ← Rev. 24   Vote: I like it 0 Vote: I do not like it

    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

    → Reply
    • »
      »
      »
      4 years ago, # ^ |
      ← Rev. 2   Vote: I like it +3 Vote: I do not like it

      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."

      → Reply
      • »
        »
        »
        »
        4 years ago, # ^ |
        ← Rev. 3   Vote: I like it 0 Vote: I do not like it

        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.

        → Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

The contest was really brilliant in my opinion. Kudos to the author! Even after having not performed that well, you still made my day! :)

→ Reply
»
4 years ago, # |
  Vote: I like it -15 Vote: I do not like it

What's the point in problem E if it's OEIS-able?

http://oeis.org/A087644

→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it +49 Vote: I do not like it

    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.

    → Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    Even after finding the OEIS sequence , I don't think the problem is solved.

    → Reply
    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it +16 Vote: I do not like it

      Well,you can just use the $$$O(nk)$$$ DP and optimize it with Lagrange Interpolation(not sure whether it is called this in English).

      → Reply
      • »
        »
        »
        »
        4 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Can you please elaborate on how to optimize it with Lagrange interpolation?

        → Reply
»
4 years ago, # |
  Vote: I like it +9 Vote: I do not like it

Most people did the same mistake in B.

Checking if xor of all elements is zero or not.

nice trap

→ Reply
»
4 years ago, # |
  Vote: I like it +3 Vote: I do not like it

i would say question B is a good problem...

→ Reply
»
4 years ago, # |
  Vote: I like it +20 Vote: I do not like it

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 ;(

→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

    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.

    → Reply
    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it +1 Vote: I do not like it

      Thanks for the words. Will see how it goes.

      → Reply
      • »
        »
        »
        »
        4 years ago, # ^ |
        ← Rev. 4   Vote: I like it +3 Vote: I do not like it

        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)

        → Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it +4 Vote: I do not like it

    u got this i believe :)

    → Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it +9 Vote: I do not like it

    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.

    → Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    i lost expert and am currently stabilised on pupil :(

    → Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    so familiar...

    → Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    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.

    → Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I agree with you mate. But I am having a hard time giving it up.

    → Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Chin up king, dont lose hope. You just have to push yourself and solve harder problems so that you learn something new.

    → Reply
»
4 years ago, # |
  Vote: I like it +16 Vote: I do not like it

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.

→ Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

How to solve B? with some proof

→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    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.

    → Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it +8 Vote: I do not like it

    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.

    → Reply
»
4 years ago, # |
  Vote: I like it +7 Vote: I do not like it

me when i thought you could remove any 2 elements for b and not just any two adjecent ones....

→ Reply
»
4 years ago, # |
  Vote: I like it +28 Vote: I do not like it

mohammedehab2002 be like

→ Reply
»
4 years ago, # |
  Vote: I like it +9 Vote: I do not like it

In Problem D, I believe I'm not the only one who think of subrange as subsequence wrongly...

→ Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

How to solve B?

→ Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Is there any penalty if you get WA on pretest 1?

→ Reply
  • »
    »
    4 years ago, # ^ |
    ← Rev. 2   Vote: I like it +9 Vote: I do not like it

    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

    → Reply
»
4 years ago, # |
← Rev. 3   Vote: I like it +22 Vote: I do not like it

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.

→ Reply
  • »
    »
    4 years ago, # ^ |
    ← Rev. 2   Vote: I like it +6 Vote: I do not like it

    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

    → Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    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.

    → Reply
  • »
    »
    4 years ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    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

    → Reply
    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it +1 Vote: I do not like it

      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.

      → Reply
      • »
        »
        »
        »
        4 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        He is exactly talking about people like specialists and experts.

        → Reply
        • »
          »
          »
          »
          »
          4 years ago, # ^ |
            Vote: I like it +13 Vote: I do not like it

          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.

          → Reply
»
4 years ago, # |
  Vote: I like it +62 Vote: I do not like it

This is the first time I've seen that pretests were weak enough that a pretest was added during the contest.

→ Reply
»
4 years ago, # |
  Vote: I like it +28 Vote: I do not like it

Screencast with commentary

→ Reply
»
4 years ago, # |
  Vote: I like it +4 Vote: I do not like it

A said choose different elements, means different value or different index?

→ Reply
»
4 years ago, # |
  Vote: I like it +7 Vote: I do not like it

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

→ Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Слабые системные тесты!!!

→ Reply
»
4 years ago, # |
  Vote: I like it +1 Vote: I do not like it

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

→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Two elements are different if they are at different indices. That's what I thought.

    → Reply
»
4 years ago, # |
← Rev. 2   Vote: I like it -36 Vote: I do not like it

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

→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it +25 Vote: I do not like it

    doesn't look like the same problem at all

    → Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I knew this problem. It's a classic DP problem. But how to use this in Problem C?

    → Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

    → Reply
»
4 years ago, # |
  Vote: I like it +2 Vote: I do not like it

Weak system tests!!!

→ Reply
»
4 years ago, # |
  Vote: I like it +6 Vote: I do not like it

I want to know why for the third problem, if we pick the minimum element, it will be giving wrong answer?

→ Reply
  • »
    »
    4 years ago, # ^ |
    ← Rev. 2   Vote: I like it +4 Vote: I do not like it

    2 3 3 4 4
    Even if you remove 2, you can still partition it into 3 + 4 = 3 + 4

    → Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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

    → Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    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

    → Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it 
    6
2 2 2 2 3 3
    → Reply
»
4 years ago, # |
← Rev. 3   Vote: I like it -8 Vote: I do not like it

Sigh. Failed problem B in the main test #16.

Anyhow, for problem C, can someone provide a test case where the following fails :

  1. Check if we can construct sum/2 using some of the elements. If not, answer is 0.
  2. Check if sum is odd. If so, answer is 0.
  3. Check if there's an odd element. If so, it can be removed to make the sum odd. Answer is 1.
  4. 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.

→ Reply
  • »
    »
    4 years ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    I think this case may work : 7-- 16 22 16 18 24 4 32

    → Reply
  • »
    »
    4 years ago, # ^ |
    ← Rev. 3   Vote: I like it 0 Vote: I do not like it

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

    → Reply
    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Darn, that's likely it!

      → Reply
    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Can you please explain why the answer should have been true for this case?

      → Reply
      • »
        »
        »
        »
        4 years ago, # ^ |
          Vote: I like it +1 Vote: I do not like it

        These partitions are all equal: [3], [3], [3,0] (They all XOR to 3)

        → Reply
        • »
          »
          »
          »
          »
          4 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          Ah! got it thanks

          → Reply
        • »
          »
          »
          »
          »
          4 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          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.

          → Reply
          • »
            »
            »
            »
            »
            »
            4 years ago, # ^ |
            ← Rev. 3   Vote: I like it 0 Vote: I do not like it

            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

            → Reply
            • »
              »
              »
              »
              »
              »
              »
              4 years ago, # ^ |
                Vote: I like it 0 Vote: I do not like it

              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.

              → Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    2 4 6 10

    → Reply
  • »
    »
    4 years ago, # ^ |
    ← Rev. 3   Vote: I like it 0 Vote: I do not like it

    7

    6 6 4 4 4 4 4 this one fails if we remove the smallest

    → Reply
    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      In this case, the sum is odd, so no number needs to be removed

      → Reply
»
4 years ago, # |
  Vote: I like it -8 Vote: I do not like it

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

→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

    → Reply
»
4 years ago, # |
  Vote: I like it -8 Vote: I do not like it

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!

→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    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

    → Reply
    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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

      → Reply
      • »
        »
        »
        »
        4 years ago, # ^ |
          Vote: I like it +1 Vote: I do not like it

        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.

        → Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Check this for an intuitive approach

    → Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

In the last round A had weak pretests, now in this round B & C have weak pretests :)

→ Reply
»
4 years ago, # |
  Vote: I like it -15 Vote: I do not like it

Failed System Test 16 in B. So, here it comes:

Spoiler
→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it +15 Vote: I do not like it

    Weaker pretests mean some opportunities for hacks.

    And without hacks Codeforces rounds woudn't be so interesting.

    → Reply
»
4 years ago, # |
  Vote: I like it +7 Vote: I do not like it

questions are short and clear and also begiener friendly....i really enjoy the contest

→ Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
4 years ago, # |
  Vote: I like it -17 Vote: I do not like it

I failed task C because I printed 0-indexed solution

There was no hint at all, that it was supposed to be 1-indexed.....

→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    The second line contains n integers a1, a2, …, an

    I don't see a0 here

    → Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it +10 Vote: I do not like it

    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"

    → Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Weak system test for c. My random solution is passing.

→ Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Can we hack solutions now?

→ Reply
»
4 years ago, # |
  Vote: I like it +15 Vote: I do not like it

How to solve D if we partition into subsequences rather than contiguous subarrays?

→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it -10 Vote: I do not like it

    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).

    → Reply
    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it +10 Vote: I do not like it

      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.

      → Reply
»
4 years ago, # |
  Vote: I like it +1 Vote: I do not like it

Almost 50% submission for problem "B" and "C" got rejected...It's really astonishing!!!

→ Reply
»
4 years ago, # |
  Vote: I like it +27 Vote: I do not like it

→ Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Really nice question set with good difficulty balance and fast editorial, that two in a row. Waiting for your next one buddy.

→ Reply
»
4 years ago, # |
  Vote: I like it +25 Vote: I do not like it

To not keep you waiting, the ratings updated preliminarily. In a few hours, I will remove cheaters and update the ratings again!

→ Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Can someone hack this submission? I'm doing knapsack dp n times in worst case it should TLE I guess

→ Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Can someone provide test cases for B. Still failing for pretest 4

→ Reply
»
4 years ago, # |
  Vote: I like it +1 Vote: I do not like it

Everybody missing "adjacent" in B. Me missing "at least" in B.

→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

    → Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Can we do D without binary lifting?

→ Reply
»
4 years ago, # |
  Vote: I like it +3 Vote: I do not like it

Good problems, good round. Hopefully such rounds will be more.

→ Reply
»
4 years ago, # |
  Vote: I like it +22 Vote: I do not like it

unknown

Note: the person in the meme is my friend Ahmadsm2005 in the ioi qualifications contest XD

Meme by: Nakeeb

→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

    That fridge was full of yogurt drinks. It literally never ended xD

    → Reply
    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it +7 Vote: I do not like it

      yes you're a yogurt drink addict

      → Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it +11 Vote: I do not like it

    as the setter of this meme give me contribution.

    → Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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".

    → Reply
»
4 years ago, # |
  Vote: I like it +3 Vote: I do not like it

→ Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Please update problem ratings.

→ Reply
»
4 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
4 years ago, # |
← Rev. 3   Vote: I like it +3 Vote: I do not like it

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

→ Reply
»
4 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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 .

→ Reply