IgorI's blog

By IgorI, history, 4 years 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, kalki411, RetiredPlayer, 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

| Write comment?
»
4 years 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?

  • »
    »
    4 years 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.

  • »
    »
    4 years 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.

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

    Procrastination

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

Good Luck Participants! — a participant

»
4 years 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?

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

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

    • »
      »
      »
      4 years 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

      • »
        »
        »
        »
        4 years 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 :-).

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

    it's a trap!

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

this set is nice :3

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

we should be thankful to HIS_GRACE for testing this round

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

hope it be a good contest and yall good ratings

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

Problems are very interesting! Good Luck!

»
4 years 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.

»
4 years 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.

  • »
    »
    4 years 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 :).

    • »
      »
      »
      4 years 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.

      • »
        »
        »
        »
        4 years 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.

        • »
          »
          »
          »
          »
          4 years 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!

        • »
          »
          »
          »
          »
          4 years 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/

  • »
    »
    4 years 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.

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

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

      • »
        »
        »
        »
        4 years 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.

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

          It's actually Expert in Codeforces

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

          viwreck U know the feeling right,I just wanted to let itiswhatitizChiyu_0_O 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)/

»
4 years 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?!

  • »
    »
    4 years 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.

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

Hoping for shorter problem descriptions just like the announcement.

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

As a tester, I request some contribution.

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

    What was that, and who are you? :D

    • »
      »
      »
      4 years 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?

»
4 years 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?

  • »
    »
    4 years 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...

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

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

      • »
        »
        »
        »
        4 years 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!

»
4 years 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.

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

Wish you all luck ^^

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

Great round id

»
4 years 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

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

anyone waiting for round #700?

»
4 years 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.

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

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

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

Hopefully this round lives up to its ID.

»
4 years ago, # |
  Vote: I like it -6 Vote: I do not like it

Good luck to everyone!!

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

IgorI orz

»
4 years 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?

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

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

    • »
      »
      »
      4 years 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...

      • »
        »
        »
        »
        4 years 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.

        • »
          »
          »
          »
          »
          4 years 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...

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

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

»
4 years 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

  • »
    »
    4 years 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.

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

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

  • »
    »
    4 years 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.

»
4 years 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).

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

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

»
4 years 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

»
4 years 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!

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

»
4 years 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.

  • »
    »
    4 years 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

    • »
      »
      »
      4 years 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.

»
4 years 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 :)

»
4 years 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:/

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

Who all fall for the trap in problem B?

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

    Me. I literally skipped it.

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

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

      • »
        »
        »
        »
        4 years 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.

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

Nice round! Thank you, IgorI!

»
4 years 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

  • »
    »
    4 years 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

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

      lcm of 2 primes is basically multiplication

      • »
        »
        »
        »
        4 years 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

        • »
          »
          »
          »
          »
          4 years 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$$$

  • »
    »
    4 years 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.

  • »
    »
    4 years 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

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

Is C a graph problem or DSU?

  • »
    »
    4 years 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.

    • »
      »
      »
      4 years 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)$$$

      • »
        »
        »
        »
        4 years 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 .

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

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

»
4 years 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.

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

How to solve D?

  • »
    »
    4 years 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).

»
4 years 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.

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

Can I know the approach for div A?

  • »
    »
    4 years 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

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

can anyone explain how to solve question 3?

  • »
    »
    4 years 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).

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

How to solve C ?

  • »
    »
    4 years 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.

»
4 years 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...?

»
4 years 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?

»
4 years 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

  • »
    »
    4 years 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.

    • »
      »
      »
      4 years 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 :/

    • »
      »
      »
      4 years 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)

    • »
      »
      »
      4 years 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)$$$

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

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

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

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

»
4 years 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.

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

    Fun fact:This was div2 only round:)

»
4 years 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.

  • »
    »
    4 years 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 !!

  • »
    »
    4 years 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

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

      10^5 will also work

    • »
      »
      »
      4 years 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?

      • »
        »
        »
        »
        4 years 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.

  • »
    »
    4 years 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.

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

    Problem B was more logic than maths.

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

      How do you separate logic from math?

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

Thanks for the contest!

»
4 years 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.

  • »
    »
    4 years 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.

  • »
    »
    4 years 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.

    • »
      »
      »
      4 years 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.

      • »
        »
        »
        »
        4 years 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.

»
4 years 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
  • »
    »
    4 years 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.

»
4 years 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.

»
4 years 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.me/contest/1474/submission/104805897

  • »
    »
    4 years 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.

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

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

      • »
        »
        »
        »
        4 years 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 :)

    • »
      »
      »
      4 years 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.me/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).

      • »
        »
        »
        »
        4 years 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.

»
4 years 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.

»
4 years 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 ?

»
4 years ago, # |
  Vote: I like it -38 Vote: I do not like it

Probably the simplest solution of C 104805814

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

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

»
4 years 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 ....

  • »
    »
    4 years 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.

»
4 years 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.

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

I think D was leaked today.

»
4 years 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.me/contest/1474/submission/104812694

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

Any Help will be appreciated.. I am clueless

  • »
    »
    4 years 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.

  • »
    »
    4 years 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.

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

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

»
4 years 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 :) :) :)

»
4 years ago, # |
  Vote: I like it -27 Vote: I do not like it

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

»
4 years 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?

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

    Same situation... Realized only when 20 minutes left

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

    Edit: wrong solution.

    • »
      »
      »
      4 years 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?

    • »
      »
      »
      4 years 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.

      • »
        »
        »
        »
        4 years 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.

        • »
          »
          »
          »
          »
          4 years 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

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

      I uphacked your solution ^^

»
4 years 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!

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

.

  • »
    »
    4 years 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

»
4 years 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?-

»
4 years 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?!

»
4 years 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)

»
4 years 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.

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

Looking at the empty upcoming contest section , feels sad .

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

    There is one upcoming AtCoder Beginner Contest this weekend :)

    • »
      »
      »
      4 years 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 :')

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

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

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

Why there is no upcomming contest ??

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

Give me a round, or give me death!

»
4 years 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

  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    • »
      »
      »
      4 years 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.