Please subscribe to the official Codeforces channel in Telegram via the link https://t.me/codeforces_official. ×

IgorI's blog

By IgorI, history, 8 months ago, translation, In English

Hi, Codeforces!

I'm glad to invite you to take part in Codeforces Round #696, which will take place on Jan/19/2021 17:35 (Moscow time). Round will be rated for participants with rating less than $$$2100$$$. Participants from the first division can take part out of competition.

There will be $$$6$$$ problems for $$$2$$$ hours. All problems are authored by me. Thanks to adedalic for excellent round coordination and to MikeMirzayanov for Codeforces and Polygon.

Also thanks to testers errorgorn, awoo, rkm62, khiro, AmShZ, IaMaNanBord, Osama_Alkhodairy, Prakash11, Gauravvv, HIS_GRACE, Dragnoid99 for testing the round and giving valuable feedback for problems.

Scoring is $$$500-1000-1500-2000-2250-3000$$$.

Good luck!

UPD: Editorial

UPD: Congratulations to the winners!

Of both divisions:

  1. neal

  2. antontrygubO_o

  3. HIR180

  4. fuppy

  5. Thienu

Of the second division:

  1. EzioAuditoreDaFirenze

  2. Ishtar

  3. God_Of_Blunder

  4. Shivam_18

  5. AlphaAurigae

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

»
8 months ago, # |
  Vote: I like it +103 Vote: I do not like it

I have a naive question: Why setters take too much time on selecting the scoring distribution?

  • »
    »
    8 months ago, # ^ |
      Vote: I like it +53 Vote: I do not like it

    It needs to be balanced, one should not feel like he wasted time solving C and D if E wasn't that hard but worth much more points, converse is also true. I hope you get what I am trying to say.

    • »
      »
      »
      8 months ago, # ^ |
        Vote: I like it -45 Vote: I do not like it

      I think, if greens are selected for testing Question A & B Scoring will be more accurate :)

  • »
    »
    8 months ago, # ^ |
    Rev. 2   Vote: I like it +2 Vote: I do not like it

    Not revealing score distribution too early doesn't mean it takes so much time for setters. It might change someone's strategy at the beginning of the contest.

  • »
    »
    8 months ago, # ^ |
      Vote: I like it +224 Vote: I do not like it

    Procrastination

»
8 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Good Luck Participants! — a participant

»
8 months ago, # |
  Vote: I like it +27 Vote: I do not like it

When you see some common testers and started thinking how can this be a coincidence?

  • »
    »
    8 months ago, # ^ |
      Vote: I like it +22 Vote: I do not like it

    As a tester I feel bad that you didn't tag me :-(

    • »
      »
      »
      8 months ago, # ^ |
        Vote: I like it +2 Vote: I do not like it

      As a future participant I feel bad that you didn't help me being one of the tester :P

      • »
        »
        »
        »
        8 months ago, # ^ |
          Vote: I like it +14 Vote: I do not like it

        1) I try my best to help problem setters.

        2) I try my best to help you and other participants.

        It is guaranteed that the above two statements are equivalent.

        Still you can verify that through some algorithm ( if there exist any :-).

  • »
    »
    8 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    it's a trap!

»
8 months ago, # |
  Vote: I like it +125 Vote: I do not like it

this set is nice :3

»
8 months ago, # |
  Vote: I like it +22 Vote: I do not like it

we should be thankful to HIS_GRACE for testing this round

»
8 months ago, # |
Rev. 4   Vote: I like it -87 Vote: I do not like it

hope it be a good contest and yall good ratings

»
8 months ago, # |
  Vote: I like it +45 Vote: I do not like it

Problems are very interesting! Good Luck!

»
8 months ago, # |
Rev. 2   Vote: I like it -82 Vote: I do not like it

.

»
8 months ago, # |
  Vote: I like it -10 Vote: I do not like it

I wish the Problems have some bold words. Guess that serves me right for trying too hard to speedsolve.

»
8 months ago, # |
  Vote: I like it +7 Vote: I do not like it

Hoping that my performance will be at least same as my previous performance in your contest.

  • »
    »
    8 months ago, # ^ |
      Vote: I like it -88 Vote: I do not like it

    Bro you are trying since 6 years on codeforces why you still a Specialist. Is there any mistake you are making, please give some experience advice also mistake you have made i'm a beginner here want to learn from you :).

    • »
      »
      »
      8 months ago, # ^ |
        Vote: I like it +61 Vote: I do not like it

      At least he is enjoying what he is doing without worrying much about ratings.

      • »
        »
        »
        »
        8 months ago, # ^ |
          Vote: I like it -120 Vote: I do not like it

        But bro In india geting high rating means high placement, The company would not ask you enjoying or not :( It's reality brother. So I only ask for suggestion that the mistake we could not repeat.

        • »
          »
          »
          »
          »
          8 months ago, # ^ |
            Vote: I like it +45 Vote: I do not like it

          That is so not true! I think it is this misconception that is leading to the alarming rise in cheating cases. Companies do not ask for a high rating on competitive programming platforms when they hire. They don't even care for it, in most cases.

          Recruiters only expect candidates to have a good knowledge of Data Structures and Algorithms, and programming problems on platforms like Codeforces and Codechef sometimes require the use of those topics. As a result, being good at DSA is wrongly correlated with having a high rating on these platforms, and a lot of people end up focussing on rating rather than improving their knowledge and problem-solving skills!

        • »
          »
          »
          »
          »
          8 months ago, # ^ |
          Rev. 2   Vote: I like it +19 Vote: I do not like it

          Competitive programming is a sport and it is never meant to be considered as a parameter for getting placements. Read this article for more clarification. https://www.freecodecamp.org/news/mythbusting-competitive-programming/

  • »
    »
    8 months ago, # ^ |
      Vote: I like it -22 Vote: I do not like it

    Sorry drifter_kabir Mridul323, If you taken it in negative i'm worried as i wasted my 2 years in college and started cp too late would i get job or not :( does not have any right direction how to improve in that less time.

    • »
      »
      »
      8 months ago, # ^ |
        Vote: I like it +11 Vote: I do not like it

      cruX_072 It is never late to do anything,but bro I let u know 5 star or candidate master will give negative image on your resume if u have not that true level ,So instead of focussing on rating focus on making ur data structure and algorithm stronger and also create a good dev project side by side.Also most of the guys which are here for more than year or two is doing cp for dopamine rush which they got when they have good contests or even seeing an accepted solution. AND AND NO ONE CARE FOR YOUR RATING NOT EVEN UR BEST BUDDIES OF COLLEGE.

      • »
        »
        »
        »
        8 months ago, # ^ |
          Vote: I like it +31 Vote: I do not like it

        Please don't compare 5 stars on codechef with candidate master on codeforces.

        • »
          »
          »
          »
          »
          8 months ago, # ^ |
            Vote: I like it +7 Vote: I do not like it

          It's actually Expert in Codeforces

        • »
          »
          »
          »
          »
          8 months ago, # ^ |
            Vote: I like it +2 Vote: I do not like it

          viwreck U know the feeling right,I just wanted to let cruX_072 know that rating or star shouldnt be your priority ,It will not matter if u are really good in dsa...And I know candidate master should never be compared to codechef any star ,cause I have even seen many people with 6 and 7 star by doing only long challenge(U can see India's no 1 on codechef right now for reference)/

»
8 months ago, # |
  Vote: I like it +3 Vote: I do not like it

I was wondering how they choose the testers , is it a complicated proccess?!

  • »
    »
    8 months ago, # ^ |
      Vote: I like it +33 Vote: I do not like it

    You just need to connect with author or coordinator to test the round.

»
8 months ago, # |
  Vote: I like it -28 Vote: I do not like it

IGORL ORZ

»
8 months ago, # |
  Vote: I like it +18 Vote: I do not like it

Hoping for shorter problem descriptions just like the announcement.

»
8 months ago, # |
Rev. 6   Vote: I like it -48 Vote: I do not like it

As a tester, I request some contribution.

  • »
    »
    8 months ago, # ^ |
      Vote: I like it +2 Vote: I do not like it

    What was that, and who are you? :D

    • »
      »
      »
      8 months ago, # ^ |
        Vote: I like it +30 Vote: I do not like it

      To all you downvoting — do you realize that this was in response to the first revision of the comment?

»
8 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Can't wait.Excited to face some challenging problems

»
8 months ago, # |
  Vote: I like it +30 Vote: I do not like it

It's just me or someone also felt that Codeforces rounds per month, are less nowadays?

  • »
    »
    8 months ago, # ^ |
      Vote: I like it +13 Vote: I do not like it

    I also thinks so. Might be Mike and his team are planning to do something against cheaters, because from past 3-4 months everyone knows what is happening...

    • »
      »
      »
      8 months ago, # ^ |
        Vote: I like it +6 Vote: I do not like it

      Or maybe, because there are lesser contest proposals these days.

      • »
        »
        »
        »
        8 months ago, # ^ |
          Vote: I like it +55 Vote: I do not like it

        I think the proposal queue is quite long and there are still many writers waiting. From my personal experience, I finally get KAN's review exactly 4 months after I propose my friends' and my contest. Moreover, our contest doesn't even have a coordinator to assign to. Coordinators are so busy and committed to their work. We should thank them for their devotion.

        Anyway, in the period of less contests, don't forget there are considerable amount of nice problem in GYM and previous contests. Go and solve them!

»
8 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Good luck to all of you!

»
8 months ago, # |
  Vote: I like it +94 Vote: I do not like it

As a tester, I can confirm that the problems are awesome and you guys will enjoy the contest.

»
8 months ago, # |
  Vote: I like it +14 Vote: I do not like it

Wish you all luck ^^

»
8 months ago, # |
  Vote: I like it +25 Vote: I do not like it

Great round id

»
8 months ago, # |
  Vote: I like it +21 Vote: I do not like it

Since this is a palindromic round ( 696 ). Hoping to see one question on Palindrome :D

»
8 months ago, # |
  Vote: I like it -10 Vote: I do not like it

anyone waiting for round #700?

»
8 months ago, # |
Rev. 2   Vote: I like it -56 Vote: I do not like it

Chahu me ye chahu dil se me ye chahu k is contest k baad pupil me bun jau.

»
8 months ago, # |
  Vote: I like it +2 Vote: I do not like it

I will try to solve solve A,B,C. Good Luck Every One, Keep Practicing and keep shining.

»
8 months ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

Thank you lgorl for this contest! Good luck to everyone!

»
8 months ago, # |
  Vote: I like it +18 Vote: I do not like it

Hopefully this round lives up to its ID.

»
8 months ago, # |
  Vote: I like it -6 Vote: I do not like it

Good luck to everyone!!

»
8 months ago, # |
  Vote: I like it +7 Vote: I do not like it

IgorI orz

»
8 months ago, # |
  Vote: I like it 0 Vote: I do not like it

All the Best !!

»
8 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Out of the given 5 or 6, solving how many statements within the 2 hours of the contest would be considered 'reasonable' for a relative novice?

  • »
    »
    8 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    2 on average.

    • »
      »
      »
      8 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Lol. Expected a lot of downvotes because of 'Ratism'. Anyway, still a long way to go for me.

      • »
        »
        »
        »
        8 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Good luck. Even solving one problem is enough for a beginner.

  • »
    »
    8 months ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    I couldn't solve one for this round :(. It's damn tough.

    • »
      »
      »
      8 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      I still don't get what was to be done in the second one... Sending the first two primes after 1, each at least d apart from one another, did not always seem to produce the minimum number and checking for every number was a bit too resource intensive.

      Am curious about the solution...

      • »
        »
        »
        »
        8 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        The number has atlest 4 divisors if it's a multiple of 2 primes. The least first prime is $$$a >= 1 + d$$$, and second $$$b >= a + d$$$. As soon as any number is a multiple of some primes, if we choose only two primes, which are the smallest possible, the result a * b will be the smallest.

        • »
          »
          »
          »
          »
          8 months ago, # ^ |
          Rev. 2   Vote: I like it 0 Vote: I do not like it

          Yeah, I did just that but weirdly, it was showing 'wrong answer for test case 2'.

          Eg. outputs of my program:

          234 -> 114481, 10000 -> 200250077, 1 -> 6, 2 -> 15,

          Don't know what went wrong...

          • »
            »
            »
            »
            »
            »
            8 months ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            Your ansewer for 3 is 28 somewhy. But 2 and 1 is 28 divisors. So, I would assume function findPrime() is not correct

            • »
              »
              »
              »
              »
              »
              »
              8 months ago, # ^ |
              Rev. 2   Vote: I like it 0 Vote: I do not like it

              Yes, I did make a mistake. The issue is with this:

              `if(var == 2)`
              `{return 2;}
              

              Without even checking for the special condition (min. difference of d), I am always returning 2 as one normally would if only whether a number is prime or not was to be checked.

              A really embarrassing mistake made in the heat of the competition.

              Thanks for looking into my code.

»
8 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Please make short statements for hard problems so we can switch another problem easily if we can't solve

  • »
    »
    8 months ago, # ^ |
      Vote: I like it +8 Vote: I do not like it

    Short statements are good but I think in contests like ICPC one can struggle if he doesn't have the habit of reading long statements and find the real problem out of it.

»
8 months ago, # |
  Vote: I like it +22 Vote: I do not like it

Am I the only one who don't see English Statements?

  • »
    »
    8 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    sometimes when you open this site , the Russian version is displayed, select the English option in right top corner.

»
8 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by IgorI (previous revision, new revision, compare).

»
8 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Hope to give my best :}

»
8 months ago, # |
  Vote: I like it +11 Vote: I do not like it

I'm just new here..... wish me luck..

»
8 months ago, # |
  Vote: I like it +7 Vote: I do not like it

Hello today i do late comment ..you guys miss me? So i want to say that its been a great journey at codeforces with you all.Such a nice community of coders and mathematicians. Good luck to all div2 participants along with me..lets binge solve tonight wohooo XD

»
8 months ago, # |
  Vote: I like it +8 Vote: I do not like it

Hope this round to be a DIV 2 and not DIV 1.5. All the best everyone!

»
8 months ago, # |
Rev. 2   Vote: I like it +123 Vote: I do not like it

»
8 months ago, # |
  Vote: I like it 0 Vote: I do not like it

I am not able to register this contest. It says it is closed. I did't saw register button at the beginning and directly started solving first question. Plz help me out.

  • »
    »
    8 months ago, # ^ |
      Vote: I like it +6 Vote: I do not like it

    You must register at least 5 minutes before the start of the round

    • »
      »
      »
      8 months ago, # ^ |
        Vote: I like it +3 Vote: I do not like it

      Not actually must , for example I missed to register beforehand today . There's something called extra registration which starts ten minutes into the contest , and probably lasts for half an hour .Use that to register if you forget to register beforehand . The only bad little disadvantage is that you cannot submit any solution in the first ten minutes.

»
8 months ago, # |
  Vote: I like it +28 Vote: I do not like it

Problem E's name describe exactly my thought on pretest 2 of E :)

»
8 months ago, # |
Rev. 2   Vote: I like it +2 Vote: I do not like it

I ruined it. Great Round very good C after a long time ig:/

»
8 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Who all fall for the trap in problem B?

  • »
    »
    8 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Me. I literally skipped it.

    • »
      »
      »
      8 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Good question, looked like a tough one but....

      • »
        »
        »
        »
        8 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        It's funny one part of my brain says do it but the other half is nah, I'mma skip to C.

      • »
        »
        »
        »
        8 months ago, # ^ |
          Vote: I like it +1 Vote: I do not like it

        CodeForces is expert in publishing problems that seem impossible but actually can be solved with a simple trick.

»
8 months ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

Nice round! Thank you, IgorI!

»
8 months ago, # |
  Vote: I like it 0 Vote: I do not like it

some body please tell me about B

I was try to find two prime number where first one is greater then or equal to 1+d and second one is a prime number which is greater then first one and difference between two prime number is greater than or equal d

but my this process get wrong answer verdict

please some one tell me about the approach of B

  • »
    »
    8 months ago, # ^ |
    Rev. 3   Vote: I like it 0 Vote: I do not like it

    the answer is LCM of 2-th and 3-th primary numbers, and diff between each prime numbers should be >= than d

    • »
      »
      »
      8 months ago, # ^ |
        Vote: I like it +10 Vote: I do not like it

      lcm of 2 primes is basically multiplication

      • »
        »
        »
        »
        8 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        thanks, I observed this connection but couldn't prove it during the contest

        • »
          »
          »
          »
          »
          8 months ago, # ^ |
          Rev. 3   Vote: I like it +2 Vote: I do not like it

          lcm of two numbers $$$a$$$ and $$$b = (a*b)/gcd(a,b)$$$

          so lcm of two primes $$$p1$$$ and $$$p2$$$

          $$$= (p1 * p2) / gcd(p1, p2)$$$

          obviously the $$$gcd$$$ of two distinct primes is $$$1$$$ since they are relatively prime to each other

          $$$lcm = (p1 * p2) / 1$$$

          $$$= p1 * p2$$$

          • »
            »
            »
            »
            »
            »
            8 months ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            It can also be proven directly. A positive integer is a common multiple of primes $$$p$$$ and $$$q$$$ iff it has both of them as prime factors of which $$$pq$$$ is the least.

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

    find next prime number for 1+d and then next prime number for (previous prime number)+d.

    • »
      »
      »
      8 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      How can we ensure that it will not cause tle or will exist in range of sieve array ? I know it intuitively but any formal or informal proof ?

  • »
    »
    8 months ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

    i guess your approach is correct ..you are missing somewhere else i think

    • »
      »
      »
      8 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      i was find all prime between 1 to 1000000 with sieve method and then start to find my primes

      is there is the problem my code had faced??

      or i should find all prime between 1 to 1000000000 ?

      • »
        »
        »
        »
        8 months ago, # ^ |
        Rev. 2   Vote: I like it 0 Vote: I do not like it

        no you didnt find upto that big number..the 1000000 is ok..

        • »
          »
          »
          »
          »
          8 months ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          i was print multiplication of those two primes

          • »
            »
            »
            »
            »
            »
            8 months ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            you dont need to look all the primes so no need for sieve. Just take 1+d, if its prime then ok, if not find next prime from it. then again add 'd' to that number and if that is prime then ok, else find next prime. multiply these two thats the answer.

          • »
            »
            »
            »
            »
            »
            8 months ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            You're accessing indexes out of the array bounds for your bool array, set it to n + 1 instead of n.

        • »
          »
          »
          »
          »
          8 months ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          actually for this, 22000 was enough considering the constraints.

  • »
    »
    8 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I think that your approach is correct but the calculation of primes takes too much time. For example, your code takes sqrt(100 million) * (100 million / 2) loops just to set multiples of 2 to false. Try the same thing, but with primes up to 50000.

»
8 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Is C a graph problem or DSU?

  • »
    »
    8 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I did brute force , because when we fix the first two numbers , the whole process becomes fixed . I don't know if it will pass system test.

    • »
      »
      »
      8 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      I thought my solution failed on some edge case where picking wrong maximum for x.

    • »
      »
      »
      8 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      For what i undestand your solution works in $$$O(n^3)$$$, if you notice that in the first two numbers, one of them should be the maximum value of the array, so the complexity become $$$O(n^2)$$$

      • »
        »
        »
        »
        8 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Yup , I considered that . But i also used set in c++ to find the biggest number and the other number faster . So mine is $$$O(n^2logn)$$$ . Since 2*n was around 2000 i thought it might work .

      • »
        »
        »
        »
        8 months ago, # ^ |
        Rev. 3   Vote: I like it 0 Vote: I do not like it

        hmmm

    • »
      »
      »
      8 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Attempt at a proof. Assume i,j,k to be indices.

      1) We have to select the maximum number in the array first to create an x [ obvious ] If you don't you cannot exhaust the array as all the maximums you chose must be strictly less than the previous maximums as arr[i]+ arr[j](new max) = arr[k] ( current max), hence arr[j] < arr[k] is an invariant.

      2) Let's assume that you have multiple combinations of i and j for getting a sum arr[k], let's call them i1,j1 and i2,j2 pairs. If i1 > i2 then j2> i1 hence you cannot select this later per invariant mentioned above. Therefore you can have one possible arrangement of the solution.

  • »
    »
    8 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    greedy+brutoforce (+ multiset)

    x is always greater than the maximum remaining number; which is a value y; also; x must be equal to y+z; for some z in the remaining values; otherwise; you cannot remove y.

»
8 months ago, # |
  Vote: I like it +4 Vote: I do not like it

contest not gut!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!

»
8 months ago, # |
Rev. 2   Vote: I like it +1 Vote: I do not like it

Very unbalanced problemset, sucks to say it, but it's what it is.

»
8 months ago, # |
  Vote: I like it +16 Vote: I do not like it

How to solve D?

  • »
    »
    8 months ago, # ^ |
      Vote: I like it +15 Vote: I do not like it

    Let dp1[i] means if you only consider the piles in [1,i] and make every piles in [1,i-1] empty, the number of stones in i. Specially, dp1[i] = -1 if you can't make every piles in [1,i-1] empty.

    Similarly, let dp2[i] means if you only consider the piles in [i,n] and make every piles in [i+1,n] empty......

    So, not considering the swap opertion, we can see that if for some i, dp1[i]=dp2[i+1]&&dp1[i]!=-1, the answer is YES.

    For swap operation, just iterate for the position you swap and get the new dp value near the swapped positions, which is O(1).

»
8 months ago, # |
  Vote: I like it +3 Vote: I do not like it

Interesting problems! Could D be solved using Segment Trees? I tried but got WA on pretest 2.

»
8 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Can I know the approach for div A?

  • »
    »
    8 months ago, # ^ |
    Rev. 3   Vote: I like it 0 Vote: I do not like it

    first char have to be max = 1 store prev char and you have three cases for the rest:

    prev = 2 -- b[i] == '0' ? '1' : '0'

    prev = 1 -- b[i] == '0' ? '0' : '1'

    prev = 0 -- '1'

    then update prev.

  • »
    »
    8 months ago, # ^ |
      Vote: I like it +6 Vote: I do not like it

    If you do not have two consecutive digits equal, you get the maximum length number. Going from left to right the first integer, you try to have in d the largest possible number, different from the previous one

»
8 months ago, # |
  Vote: I like it 0 Vote: I do not like it

can anyone explain how to solve question 3?

  • »
    »
    8 months ago, # ^ |
    Rev. 5   Vote: I like it +2 Vote: I do not like it

    Here comes the key observation. let max(array) = M.

    1. M should consist in the first pair. if we don't choose the biggest element, (next 'x') <= M, since all elements are positive, we can't eliminate M since M+1 > x

    2. If the first pair is chosen, choosing the rest automatically completes. Let's choose the first pair arbitrary. Eliminate the pair from the array. Then the next 'x' is M. by 1., we should choose the biggest element from the remaining array. But this time we know the sum of the pairs. Now, the pair automatically completes since we know one element and the sum of two elements.

    After choosing the first pair by brute force, we can complete all the steps in N log N using multiset. The number of possible 'first pair' is N-1. So we can complete the algorithm in O(N^2 log N).

»
8 months ago, # |
  Vote: I like it +4 Vote: I do not like it

How to solve C ?

  • »
    »
    8 months ago, # ^ |
      Vote: I like it +2 Vote: I do not like it

    Hint: For a particular x you must select two integers where one of them is the max of remaining elements.

  • »
    »
    8 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    X should be >= max(all(ai)), now if you dont choose max(all(ai)) in the first step itself, then you could never choose it because we are choosing elements in a decreasing fashion to satisfy the criteria of selecting maximum everytime. So if you fix any 1 number in the start except the maximum then the whole process is fixed and all you have to do is check if differences of consecutive elements exist and at the end all of them add upto n as there are n maximums to be chosen.

»
8 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Apparently multiple people solved C the same way i did, can anyone explain how i got TLE? my code's complexity should be fine...?

»
8 months ago, # |
  Vote: I like it +1 Vote: I do not like it

Stuck on figuring out C for more than 1.5 hrs. Approach anyone?

»
8 months ago, # |
  Vote: I like it 0 Vote: I do not like it

What is the intended complexity for C? I think N^2LogN should pass. Or maybe I am calculating it wrongly. Can somebody see? https://pastebin.com/5GypBk22

  • »
    »
    8 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    My solution’s complexity for C was O(N^2). I used a hashmap.

    • »
      »
      »
      8 months ago, # ^ |
      Rev. 3   Vote: I like it 0 Vote: I do not like it

      I used OrderedMap so I add the LogN factor. I will try with HashMap.

      EDIT: It passes with HashMap :/

    • »
      »
      »
      8 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Did you use DFS to find out when the no. of child reached N/2 , (basically implemented it brute forcely)

      • »
        »
        »
        »
        8 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Man why to do fucking complicated when normal hashmap O(N*2) solution can be done why to go for such complications dude !!

    • »
      »
      »
      8 months ago, # ^ |
        Vote: I like it +3 Vote: I do not like it

      hashmap in worst case if i am correct is $$$O(n)$$$ , so isn't that $$$O(n^3)$$$

  • »
    »
    8 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    My $$$O(n^2 log n)$$$ passed in like 400 ms

»
8 months ago, # |
  Vote: I like it 0 Vote: I do not like it

D is amazing, but C... kinda strange problem :/

»
8 months ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

For Div2 C, I implemented brute force graphs , but it gave me TLE , its complexity is probably O(T*(N^2)) or O(T*(N^3)) . I am not sure.

  • »
    »
    8 months ago, # ^ |
      Vote: I like it +19 Vote: I do not like it

    Fun fact:This was div2 only round:)

»
8 months ago, # |
  Vote: I like it 0 Vote: I do not like it

How to solve A?? i was trying using string as input but was getting error when i tried to convert the characters into integers for satisfying conditions.

»
8 months ago, # |
Rev. 2   Vote: I like it +4 Vote: I do not like it

After solving A and C in like 25 minutes , I gave 1.5 hours on B and still I have absolutey no idea how to do it, LOL dont have any maths background ,I am always unable to do these kinds of maths problem.

  • »
    »
    8 months ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    how to solve C can u please elaborate your approach thanks in advance !!

  • »
    »
    8 months ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    Just find the prime numbers upto 10^7 and select the prime numbers at minimum possible distance from d.

    First divisor = 1

    Second divisor = (nearest prime number to 1+d)

    Third divisor = (nearest prime number to Second divisor + d)

    Fourth Divisor = The number itself

    Answer = Second Divisor * Third Divisor

    • »
      »
      »
      8 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      10^5 will also work

    • »
      »
      »
      8 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      This makes sense. How do you know to set the upperbound to 10^7?

      • »
        »
        »
        »
        8 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        We need to find 2 primes from [10000 + 1, 2 * 10000 + 1] and [2 * 10000 + 1, 3 * 10000 + 1].

        There're multiple ways to check if there's at least 1 in each interval, easiest being searching list of primes on google.
        Alternatively, an exploratory run of sieve can be done to verify the hypothesis.

  • »
    »
    8 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    You have to just find the product of first two prime numbers such that the difference between (1,p1) and (p1,p2) is atleast d where p1<p2.

  • »
    »
    8 months ago, # ^ |
      Vote: I like it +8 Vote: I do not like it

    Problem B was more logic than maths.

    • »
      »
      »
      8 months ago, # ^ |
        Vote: I like it +1 Vote: I do not like it

      How do you separate logic from math?

  • »
    »
    8 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    B was quite easy it just had basic maths of Prime numbers,I wasn't able to solve C :(

»
8 months ago, # |
  Vote: I like it +8 Vote: I do not like it

Thanks for the contest!

»
8 months ago, # |
  Vote: I like it 0 Vote: I do not like it

How to solve B?

»
8 months ago, # |
  Vote: I like it 0 Vote: I do not like it

I found C TL to be pretty strict. I'm not sure what the intended is but $$$O(n^2 \log n)$$$ in C++ passed comfortably while the same code in Java TLEd.

  • »
    »
    8 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Same here. It doesn't even go past pretest 2 in Java using TreeMap.

  • »
    »
    8 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    You could avoid the logn factor by using a count array instead of a map(as A[i]<1e6) and after each iteration instead of resetting the entire array you could only reset the values which occurred during that iteration. This solution has a bit more implementation but you would have to worry less about about fst.

    • »
      »
      »
      8 months ago, # ^ |
        Vote: I like it +16 Vote: I do not like it

      I can see the $$$O(n^2)$$$ solution now. However simply because you can spend extra effort to find a faster solution in order to pass in a certain language doesn't justify the tight TL. Unless if the TL was intended to block log solutions (which it did a bad job of), I think it would've been better to make it looser.

      • »
        »
        »
        »
        8 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Yeah, maybe if n was 2000 it would have blocked even the C++ solutions with extra logn but I'm not sure.

    • »
      »
      »
      8 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      here is my solution that is nearly equiv to your proposition but it also causes a TLE in java! O(n^2)

»
8 months ago, # |
  Vote: I like it +6 Vote: I do not like it

Some test cases for D that I have caught and resolved

2
8
2 2 2 2 1 3 2 2
7
1 2 3 5 4 6 3
  • »
    »
    8 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    can you please tell how you resolved it, i'm trying and it's still giving WA on pretest 2.

»
8 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Cool contest. I particularly like C, although I wasn't able to solve it in-contest.

»
8 months ago, # |
  Vote: I like it 0 Vote: I do not like it

For me figuring out solution for A takes more time than solving B XD...

»
8 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Could someone pls tell why my solution TLEd for problem B? https://codeforces.com/contest/1474/submission/104805897

  • »
    »
    8 months ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    I didn't read the code carefully, See this comment for the correct answer.

    • »
      »
      »
      8 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Why did you use 2e5+5 as the largest possible prime?

      • »
        »
        »
        »
        8 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        The first divisor is around $$$d$$$ and the second divisor should be around $$$2d$$$. 2e5 is just the first number that came to my mind and it's big enough so I used it :)

    • »
      »
      »
      8 months ago, # ^ |
      Rev. 3   Vote: I like it +1 Vote: I do not like it

      I don't think that is the case. Your code fails because when 'd' is odd, you get and even 'j' and your step size in while loop is 2 so you'll never get out of the while loop. Hence the TLE.

      https://codeforces.com/contest/1474/submission/104841099

      This works. I just changed j+=2 with j+=1 and i+=2 with i+=1 (second change not needed AFAIK).

      • »
        »
        »
        »
        8 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        I apologize. I just quickly skimmed the code and found that he's checking the prime and got my conclusion.

»
8 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Couldn't solve D but loved the problem set and enjoyed a lot.

»
8 months ago, # |
Rev. 3   Vote: I like it 0 Vote: I do not like it

problem A Video Editorial Link : https://www.youtube.com/watch?v=2u6zr-tdEF4

»
8 months ago, # |
  Vote: I like it 0 Vote: I do not like it

In Problem B, if d =3 what will be the divisors of the answer ?

  • »
    »
    8 months ago, # ^ |
    Rev. 2   Vote: I like it -11 Vote: I do not like it

    1 , 5 , 11 , 55

    • »
      »
      »
      8 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Why can't it be 28 ? The divisors can be 1,4,7,28 and it's smaller than 55.

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

        all divisors, it's mean 1,2,4,7,14,28. And 2-1=1<3

      • »
        »
        »
        »
        8 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        You should notice that it contain all divisors,so 28 is 1 2 4 7 14 28,but 2-1 less than 3

      • »
        »
        »
        »
        8 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        No, Because as mentioned in the question, two out of any of its divisors should have at least d difference. Here in the case of 28, you can see, that the factors are 1, 2, 4, 7, 14, 28. Here the difference between 1 and 2 is not 3 same as for 2 and 4 have difference 2 instead of 3.

      • »
        »
        »
        »
        8 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        I don't know why on earth people have downvoted my message.

»
8 months ago, # |
  Vote: I like it -38 Vote: I do not like it

Probably the simplest solution of C 104805814

»
8 months ago, # |
Rev. 2   Vote: I like it +10 Vote: I do not like it

I solved problem E 1 minute after contest ended... :(

»
8 months ago, # |
  Vote: I like it +2 Vote: I do not like it

What is the greedy soln to D (if there is ..)? Solely greedy based and no dp ....

  • »
    »
    8 months ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    There is n't much dp other than prefix sum calculation.My solution:- if we have to remove all piles lets start from 1st one as it has only one neighbour.so a[0]<=a[1] similarily a[2]>=a[1]-a[0],a[3]>=(a[2]-(a[1]-a[0])) so on.so our problem reduces to finding an array with atmost one swap such that after swap for each position if position is even sum of even indexed number(after swap) >=sum of odd indexed number(after swap).and at final position odd_sum[n-1]=even_sum[n-1] to ensure there is no piles remain at last.Now it is an well known prefix sum implementation problem.If any doubt plz comment.

»
8 months ago, # |
Rev. 2   Vote: I like it +7 Vote: I do not like it

I am seeing codeforces's upcoming contests list empty for the first time.

»
8 months ago, # |
Rev. 3   Vote: I like it +28 Vote: I do not like it

I think D was leaked today.

»
8 months ago, # |
  Vote: I like it +5 Vote: I do not like it

Can Someone Pls Explain why my code gives a TLE with complexity O(n^2logn) and some codes with the same complexity pass easily

My Submission = https://codeforces.com/contest/1474/submission/104812694

Other Submission — https://codeforces.com/contest/1474/submission/104801893

Any Help will be appreciated.. I am clueless

  • »
    »
    8 months ago, # ^ |
    Rev. 2   Vote: I like it +1 Vote: I do not like it

    I believe it because erase(int) will erase all of that number in the set, so then you may erase the begin() of an empty set, which will cause TLE.

  • »
    »
    8 months ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

    You shouldn't do s.erase(a[i]). In this case all a[i] are getting removed while only one should get removed. Now if all elements are same, doing this makes the multiset empty and s.erase() will give TLE.

    • »
      »
      »
      8 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Thank you so much I was not aware of this STL functionality.

»
8 months ago, # |
  Vote: I like it +50 Vote: I do not like it

My 10 months-long fuckups-streak finally broke today. From writing buggy codes, to missing submiting the solutions to difficult problems by a few seconds, many times, and missed reaching the Master as consequences.

It all will end today, once the ratings get updated :D

Thanks for the contest, I'll finally become master today :) :) :)

  • »
    »
    8 months ago, # ^ |
      Vote: I like it -29 Vote: I do not like it

    Ham kya karein bhai! NO one cares

»
8 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Please Ban them!

Link1 Link 2 Link 3 Link 4

»
8 months ago, # |
  Vote: I like it 0 Vote: I do not like it

in problem B i try to first store all prime number till 2*pow(10,8); my test cases didn't passed but with 2*pow(10,6) it passed.

i think according to problem statement the upper limit should be 2*pow(10,8);

»
8 months ago, # |
  Vote: I like it -27 Vote: I do not like it

constructive-adhoc-forces... ... -50 rating ...

»
8 months ago, # |
  Vote: I like it +28 Vote: I do not like it

I misread D ( realized after an hour) and thought you can swap any pair(not necessarily neighboring).Does anyone know how to solve this version?

  • »
    »
    8 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Same situation... Realized only when 20 minutes left

  • »
    »
    8 months ago, # ^ |
    Rev. 5   Vote: I like it 0 Vote: I do not like it

    Edit: wrong solution.

    • »
      »
      »
      8 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      I solved D using those two condition but I don't know how to prove they are sufficient. Can you help me out?

    • »
      »
      »
      8 months ago, # ^ |
        Vote: I like it +48 Vote: I do not like it

      Hey, I was working on it and I think I found a counter-case.

      counter-case : n = 8, 3 4 6 4 4 6 4 3

      This array follows the two condition but it is not a good array. I think the tests were a little weak and I was able to pass through.

      • »
        »
        »
        »
        8 months ago, # ^ |
        Rev. 2   Vote: I like it 0 Vote: I do not like it

        Thanks. During contest I thought I can prove this by induction. Now I've found a mistake in the proof.

        • »
          »
          »
          »
          »
          8 months ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          Same here. I thought I had it in the contest. I actually came up with this solution because of the same misreading mistake XD

    • »
      »
      »
      8 months ago, # ^ |
        Vote: I like it +2 Vote: I do not like it

      I uphacked your solution ^^

»
8 months ago, # |
  Vote: I like it +9 Vote: I do not like it

Thanks for this contest. I'm very excited that I will reach Master tomorrow morning!

»
8 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Video solutions for problem A and B :

Problem A Video Solution

Problem B Video Solution

»
8 months ago, # |
  Vote: I like it 0 Vote: I do not like it

After a long day a nice C problem. Nice round. Enjoyed!

»
8 months ago, # |
Rev. 3   Vote: I like it 0 Vote: I do not like it

.

  • »
    »
    8 months ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    Before the start of cleaning, you can select two neighboring piles and swap them

»
8 months ago, # |
  Vote: I like it 0 Vote: I do not like it

I think the amount of code in question c is a bit large, maybe it is enough to output yes or no?-

»
8 months ago, # |
Rev. 3   Vote: I like it 0 Vote: I do not like it

My Submissions in the round have been skipped due to coincide with another solution . I don't know how it happened but I'm copying the body of the code as a template form online training I have taken recently and this is a link of a sample of a solution. https://github.com/MohamedAfifii/ProblemSolving--Arabic/blob/master/Solutions/Codeforces/100814I.cpp

I also copy some algorithms from this training and edit in them and I don't know if this person was talking the same training and is doing something similar but likely it is the case as both of us are Egyptians and the training is Egyptian one and maybe that's why the coincidence has occurred. I'm not cheating from anyone ,I swear it .That's all I want my rating back and your understanding is highly appreciated !

Link of Training : https://www.youtube.com/watch?v=N8l8-UeVpAM&list=PLYknlDiw2kSwdDhTSDoX7ZoVEle8nbZdk&fbclid=IwAR1CSH575RPWPYxnD8ftWD3ek7u3Bt3JQFSbVEBmVYOehtMLddL1OD0bRYg Link of Material : https://github.com/MohamedAfifii/ProblemSolving--Arabic

»
8 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Can some one tell me what is the difference between g++11 and g++17 that I got WA for my solution for C with g++17 and got accepted with the same code with g++11?!

»
8 months ago, # |
  Vote: I like it +10 Vote: I do not like it

Does someone happen to know when the next round is going to be? (guess now I'm into cf)

  • »
    »
    8 months ago, # ^ |
    Rev. 2   Vote: I like it +2 Vote: I do not like it

    I can't remember the last time I found the upcoming contest field empty!:(

  • »
    »
    8 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Not until it appears in the "upcoming contests" section.

»
8 months ago, # |
  Vote: I like it +12 Vote: I do not like it

I am wondering about the reason behind no new upcoming contest. Is it the case that there are no new problems proposals to pick up? Or, it is just a bit of breathing time for the admins since they have been working so hard continuously.

»
8 months ago, # |
  Vote: I like it +8 Vote: I do not like it

Looking at the empty upcoming contest section , feels sad .

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

    There is one upcoming AtCoder Beginner Contest this weekend :)

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

      Yeah I know there is atcoder round , codechef cookoff etc. But i don't know why codeforces rounds hits me differently :')

  • »
    »
    8 months ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    You don't have to be sad anymore! A div3 is scheduled

»
8 months ago, # |
  Vote: I like it +6 Vote: I do not like it

Why there is no upcomming contest ??

»
8 months ago, # |
  Vote: I like it +5 Vote: I do not like it

Give me a round, or give me death!

  • »
    »
    8 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    RIP .

    • »
      »
      »
      8 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      There are two upcoming contests as of now, but you may disregard all of them and leave codeforces for good if you like.

»
8 months ago, # |
  Vote: I like it 0 Vote: I do not like it

I can't even solve 1st problem in 2 hours :((

»
8 months ago, # |
  Vote: I like it 0 Vote: I do not like it

I dont understance why my solution. that uses just arrays and takes only O(n^2) cause a TLE !! Am i force to use c++ instead of Java ?

»
8 months ago, # |
  Vote: I like it 0 Vote: I do not like it

problems were good

»
7 months ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

B. Different Divisors for input d=381 four divisors should be (1, 1+d, 1+2d, (1+d)*(1+2d)) i.e (1, 382, 763, 291466). So answer should be 291466. but given answer is 294527. I think (1, 1+d, 1+2d, 1+3d) this should 4 divisors instead of (1, p, q, pq) or (1, p, p^2, p^3) please anyone explain this :( Correct me if I am wrong

  • »
    »
    7 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    • »
      »
      »
      7 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Well, you can't generalize the solution in this case. You are correct the answer in be of the form (1, p, q, pq) where a = pq. Moreover, according to question constraints, p-1>=d, q-p>=d, pq-p>=d. You can read the editorial for the rest of the solution. Your assumption of (1, 1+d, 1+2d, (1+d)*(1+2d)) is wrong because you can't say for sure that 1+d and 1+2d are prime numbers.