vovuh's blog

By vovuh, history, 2 weeks ago, In English,

<almost-copy-pasted-part>

Hello! Codeforces Round #642 (Div. 3) will start at May/14/2020 17:35 (Moscow time). You will be offered 6 or 7 problems (or 8) with expected difficulties to compose an interesting competition for participants with ratings up to 1600. However, all of you who wish to take part and have rating 1600 or higher, can register for the round unofficially.

The round will be hosted by rules of educational rounds (extended ACM-ICPC). Thus, during the round, solutions will be judged on preliminary tests, and after the round it will be a 12-hour phase of open hacks. I tried to make strong tests — just like you will be upset if many solutions fail after the contest is over.

You will be given 6 or 7 (or 8) problems and 2 hours to solve them.

Note that the penalty for the wrong submission in this round (and the following Div. 3 rounds) is 10 minutes.

Remember that only the trusted participants of the third division will be included in the official standings table. As it is written by link, this is a compulsory measure for combating unsporting behavior. To qualify as a trusted participants of the third division, you must:

  • take part in at least two rated rounds (and solve at least one problem in each of them),
  • do not have a point of 1900 or higher in the rating.

Regardless of whether you are a trusted participant of the third division or not, if your rating is less than 1600, then the round will be rated for you.

Thanks to MikeMirzayanov for the platform, help with ideas for problems and for coordination of my work. Thanks to my good friends Daria ZeroAmbition Stepanova, Mikhail pikmike Piklyaev, Maksim Ne0n25 Mescheryakov and Ivan BledDest Androsov for help in round preparation and testing the round. Also thanks to Artem Rox Plotkin and Dmitrii _overrated_ Umnov for the discussion of ideas and testing the round!

Good luck!

</almost-copy-pasted-part>

UPD: Thanks to ma_da_fa_ka, Jaydeep999997, abhishek_saini, infinitepro and socho for testing the round!

UPD2: Editorial is published!

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

»
2 weeks ago, # |
Rev. 2   Vote: I like it -76 Vote: I do not like it

......

»
2 weeks ago, # |
  Vote: I like it -24 Vote: I do not like it

vovuh sent this announcement when the contest is going to begin in exactly 30 hours:)

»
2 weeks ago, # |
  Vote: I like it -35 Vote: I do not like it
The key of good contests
»
2 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Still getting used to contests, can someone explain/link me to how the points and penalty system works?

  • »
    »
    2 weeks ago, # ^ |
    Rev. 4   Vote: I like it +15 Vote: I do not like it
    • every wrong submission:penalty(the time you use to solve ecah questions added together)+10.
    • the more penalty you get the worse rank you get.
    • the people solve more problems is always before the people solve less questions.
    • example:
    • User Penalty Solved Rank
    • A 100 3 4
    • B 50 3 3
    • C 200 4 1
    • D 500 4 2
    • 4<3,so C and D 's rank is before A and B 's.
    • 200<500,so C 's rank is before D 's.
    • 50<100,so B 's rank is before A 's.
    • This is ICPC mode,so no points but only penalty and the number of solved problems.
    • »
      »
      »
      2 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Got it, thank you so much. So just to clarify:

      • Solving a problem at the beginning of the contest, and at the end of the contest counts for the same (i.e. you don't get fewer points for late AC)
      • Person with more solved, more penalty has better rank than less solved, less penalty

      Are these two correct?

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

        nope..time always matters..even if you solved late your time will count..and your rank will be less than the one who solved earlier the same problem. and person with more solve has highest rank..that is right.

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

        You are ranked by number of solved problems. If these are same then by penalty. Penalty is sum of minutes of solved problems +10 for every wrong submission of a finally solved problem.

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

        The participants are ranked by the number of problems they solved. However, if two participants solved the same number of problems, they are ranked by penalty (whoever has a lower penalty will be given a better rank).

        For each solved problem, the penalty is the time taken (in minutes) from the start of the contest to solve the problem, plus 10 times the number of incorrect submissions (some types of incorrect submission do not count).

        The total penalty is the penalties for each problem that you solved (Accepted) added up.

        Note: If you tried to solve a problem but none of your submissions were accepted, then the incorrect submissions for this problem will not count in the penalty.

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

          Thank you so much, appreciated.

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

            Also, let's say there are two problems A and B, and you can solve A in 1 min and B in 50 min. If you solve at first A, then B your penalty is 51. But if you solve B, then A, your penalty is twice as big = 101. which is not very logical.

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

              Absolutely agreed ! I believe Google and Topcoder marking schemes are more logical..

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

              Yeah your logic is correct to some extent but there is a motive behind keeping such penalties.Suppose the system is changed as per your thinking then people who are ranked higher and are supposed to do 3-4 problems to stop getting negative delta, will start solving the C/D problem first and if they are not able to get logic for the problem in less time, they might not submit anything and escape the negative delta.(no submission in a contest counts to non-participation).

              This type of penalty system almost ensures that contestants don't do that!(but still many contestants do C/D first.)

    • »
      »
      »
      2 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      every wrong submission => penalty . this applies to the first submission too ??

      • »
        »
        »
        »
        2 weeks ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        yes.but submissions wrong on examples -0 penalty.

»
2 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Good luck to all the participants. It's a really good opportunity to become an expert.

  • »
    »
    2 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Honestly! It had good questions. Also! Problem F. Was one of the problems I saw somewhere else but never solved it!

    Today! will solve that problem :party-parrot:

»
2 weeks ago, # |
  Vote: I like it +29 Vote: I do not like it

Thank you CodeForces for increasing the contest frequency!!

»
2 weeks ago, # |
  Vote: I like it +80 Vote: I do not like it

»
2 weeks ago, # |
Rev. 7   Vote: I like it -28 Vote: I do not like it

This will be the only meme I've posted so far.

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

    And this meme too.

    • »
      »
      »
      2 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      IMO there shall be change in rules for DIV3/4 regarding contest Authors, as we low rated guys have ideas for new questions too.

»
2 weeks ago, # |
  Vote: I like it -23 Vote: I do not like it

I hope that this contest can have a wider range of questions. In the last round (Rd 641), I personally think that the problems are too math-based. I believe that a good contest should test contestants in different regions of programming, such as dp, constructive algorithms and etc. Hope this contest can be educational for div 3 programmers and being competitive at the same time!

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

    That sounds good but lots of contests before have already had what you need. I think we should have more mathletic problems because we are having too few. (sorry for my poor English)

»
2 weeks ago, # |
  Vote: I like it +37 Vote: I do not like it

I run out of memes

»
2 weeks ago, # |
  Vote: I like it -16 Vote: I do not like it

lets hope that the questions don't emphasize on number theory in general a lot...

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

    TBH number theory is fun.

    • »
      »
      »
      2 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      you r so wrong,it gets friggin irritating when 2 out of first 3 problems are simply based on annoying numeros....

    • »
      »
      »
      2 weeks ago, # ^ |
        Vote: I like it -11 Vote: I do not like it

      No all participants are computer science students. I study aerospace engineering. So I prefer simple math algorithms like euclids GCD, DFS. But not some special, not well known property of prime numbers or modular division. There should be seperate mathforces round.

»
2 weeks ago, # |
Rev. 3   Vote: I like it +6 Vote: I do not like it

Thanks! for round. Hope it will help.

»
2 weeks ago, # |
  Vote: I like it +5 Vote: I do not like it

One Question .... what are things we should do in college to get a good placement.... Some people tell me that do CP...because at the time of Interview it helps lot....But i have one doubt..We also have to do projects ? or to do only CP..and improve it....And if we have to do projects what are the right time in a 4 year B.Tech course...to do projects.... Please answer this Question it helps me a lot..to prepare my strategy for further Two year... i'm in 2nd year now..... Thanks in advance//

  • »
    »
    2 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Don't do CP just for the sake of interviews, for that you've got leetcode. Do CP as a hobby. Work on projects whenever you feel like it.

  • »
    »
    2 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    depends in which college u r...

    • »
      »
      »
      2 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      i'm in 3 tier college

      • »
        »
        »
        »
        2 weeks ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        then most probably u r going to have to take up projects on languages like python which is deemed to take over in few years..this will enhance your programming and give u an upper hand amongst your peers...i dnt mean to mock anyone..but in tier 3 colleges u will have to really work to qualify as a potential candidate for the companies that will be hiring from tier 3 college.. i hope u dont take it otherwise.. :) wish u success

        • »
          »
          »
          »
          »
          2 weeks ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          so wrapping up this conversation...I have to do coding regularly..to crack interviews..and do also projects monthly..or at a regular interval ..right?

          • »
            »
            »
            »
            »
            »
            2 weeks ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            Yeah.. And u can also consider completing courses on coursera on topics such as data science /analysis....and all u have is time in this quarantine...

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

    You need two or three good projects on your resume so that interviewer have something to discuss with you in the interview.
    It also varies from company to company. Some companies judge you on the basis of your approach for solving cp problems and some will judge you on the basis of your work and understanding of the projects in your resume.
    But in the end to reach face to face interview rounds you have to clear initial coding rounds first. So cp is important for that part. If you can solve div2 ABC level question than clearing those initial coding round will be easy for you.

»
2 weeks ago, # |
Rev. 2   Vote: I like it -11 Vote: I do not like it

Hopefully this will not happen to me again :(

»
2 weeks ago, # |
  Vote: I like it +33 Vote: I do not like it

»
2 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Let's hope to rank up after latest Div2 round

»
2 weeks ago, # |
  Vote: I like it -44 Vote: I do not like it

is it rated for unrated participants?

»
2 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

I have a general doubt:

If there is an update in the problem statements and I am giving the contest in m1.codeforces.com, will I get the notification?

»
2 weeks ago, # |
  Vote: I like it +15 Vote: I do not like it

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

Wow! Next four days three CF contests and many more to come. Thanks CF.

»
2 weeks ago, # |
  Vote: I like it +12 Vote: I do not like it

Rounds in this time of selfisolation like a water in desert...

»
2 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Best Wishes

Spoiler
»
2 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Struggling a lot to become a specialist. I crossed 1380+ three times. but couldn't reach 1400. I hope this time, I will make it to the 1400 club.

»
2 weeks ago, # |
  Vote: I like it +3 Vote: I do not like it

Long queues Mike, w@#k happened again ?

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

Deleted

»
2 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Why aren't contest hosted on weekends more often? I mean, some of us have no opportunity to compete from Monday to Friday, 'cause you know, we work on those days.

  • »
    »
    2 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Agreed. At least one contest on weekend would work.

»
2 weeks ago, # |
  Vote: I like it +3 Vote: I do not like it

Thank you Codeforces for increasing the contest frequency ^_^

»
2 weeks ago, # |
  Vote: I like it +24 Vote: I do not like it

A say home stay safe.

»
2 weeks ago, # |
Rev. 6   Vote: I like it -11 Vote: I do not like it

deleted

(I mean, why you guys downvote this? This is nothing so can't you just ignore it?

Anyway this was a crap meme and I decided to delete it...)

»
2 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

I hope that problems will be based on Data structures.

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

Codeforces is surely the best platform to practise CP

»
2 weeks ago, # |
Rev. 4   Vote: I like it -32 Vote: I do not like it

.

»
2 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

The explanation is good and Thanks the Codeforces Team for this nice platform and for increasing the contest frequency and it is really good for beginners ...Thanks to all.

»
2 weeks ago, # |
  Vote: I like it -7 Vote: I do not like it

Vovuh and Mike's Div3 never lets me down. Also I am lucky to never cross 1600 and participate in all their rounds.

»
2 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

In my personal profile my rating has changed. But when I am checking my rating in organization section, my rating is as it was in previous contest. Why?

»
2 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Can anyone explain the rating system or the link of previous discussion about rating system(latest) ?

  • »
    »
    2 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    You are ranked by number of solved problems. If these are same then by penalty. Penalty is sum of minutes of solved problems +10 for every wrong submission of a finally solved problem. Copied from : spookywooky

    • »
      »
      »
      2 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Thanks for your comment.But I have asked about rating after a contest not about ranking...

»
2 weeks ago, # |
  Vote: I like it -9 Vote: I do not like it

CoNgRaTs! YoU HaVe ReAd AlL ThE MeMes

»
2 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

1st contest! Time to leave 1500 rating gang. Probably the highest I will ever get.

»
2 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

How much is the importance of knowing algorithm for Div3 and which ones I should know?

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

    dp, greedy, dfs and bfs, simple math and implementation, and binary search. Also, you should solve problems fast.

»
2 weeks ago, # |
  Vote: I like it -63 Vote: I do not like it

»
2 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

A efficient way to spend quarantine time for programmer.

Hope for the best for today's contest.

»
2 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it
»
2 weeks ago, # |
  Vote: I like it +4 Vote: I do not like it

although I am in div2,usually I cann't fully solve div3. So why cann't I be rated in div3? Maybe we can drop 2 easy problems and append 2 harder problem to make div3 also rated for div2.

»
2 weeks ago, # |
  Vote: I like it -24 Vote: I do not like it
The comment removed because of Codeforces rules violation
  • »
    »
    2 weeks ago, # ^ |
      Vote: I like it +14 Vote: I do not like it

    If you have questions like this, ask the jury.

    It's forbidden to talk about these during the contest.

»
2 weeks ago, # |
  Vote: I like it +9 Vote: I do not like it

Beautiful problems and straightforward statements... thank you! Also, first time being able to solve E :)

  • »
    »
    2 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Can you give hint on $$$E$$$, I am out of ideas!

    • »
      »
      »
      2 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Hint:we will use dynamic problem to solve this problem.

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

      Let's denote the input array by s[1...n].

      Let:

      dp[i][0 / 1] — be the minimum number of operations you need to perform in order to make the array s[1...i] k-periodic, considering that you let the i-th bit as it is (dp[i][0]) or that you've changed it (dp[i][1])

      cnt[i] — be the number of 1's in the array s[1...i]

      Let's talk about the case when s[i] = 0...

      If you don't change this bit, it won't affect the periodicity of the array s[1...i], so you can take the answer from the previous subproblem:

      dp[i][0] = min(dp[i - 1][0], dp[i - 1][1])
      

      If you change this bit, then you may have to make additional opperations to assure the k-periodicity property of your s[1...i] array.

      The first option is to turn off all the 1's from 0 to i - 1:

      dp[i][1] = 1 + cnt[i - 1] // 1 + because you change the i-th bit, as well
      

      The second option is to turn off all the 1's from i - k + 1 to i - 1 and continue building your answer based on the subproblem i - k, considering that s[i - k] = 1.

      In case s[i - k] = 1, then:

      dp[i][1] =  1 + dp[i - k][0] + cnt[i - 1] - cnt[i - k]
      

      In case s[i - k] = 0, you have to change that bit, as well:

      dp[i][1] =  1 + dp[i - k][1] + cnt[i - 1] - cnt[i - k]
      

      In the end, dp[i][1] is the minium beween cnt[i - 1] + 1 and one of the two last cases.

      Now, consider a similar strategy when s[i] = 1...

      In the end, the answer will be:

      min(dp[n][0], dp[n][1])
      
    • »
      »
      »
      2 weeks ago, # ^ |
      Rev. 3   Vote: I like it +1 Vote: I do not like it

      I apoligize for the poor editing skills, I am not used to how editing comments works on this platform.

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

        Highly appreciate your comment, thanks a lot!

»
2 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

What could be the test case 2 of problem-E?

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

    For sure it is a test case that takes into consideration the fact that sometimes you can stop at some character 1 in position i and just ignore the rest of the string. I took this case into consideration to pass the test case 2. But of course to do this you will have to "pay" a price which is the amount of character 1 after the position i.

»
2 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

How to solve E ?

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

    You can solve for each index mod k separately. Now replace '0' by -1 and '1' by +1. Find segment with max sum, can be done with Kadane algo.

    • »
      »
      »
      2 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      @Len how did it strike you that we need to take maximum subarray sum? I almost spent an hour thinking about it. Could not write dp solution because I am not good at dp :(

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

      could you tell what do you mean by 'solve for each index mod k separately'

      Edit- got it.

»
2 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Is it going to be hackforces?

»
2 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Is there easier way to solve D beside divide and conquer?

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

How to solve F, thanks.

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

    Notice that sum(n) <= 100, sum(m) <= 100 constraint. There will be at least one cell that is not changed. So if you fix that cell, you can determine what value (i, j) needs to be. The rest is n * m dp.

»
2 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

I just refreshed my page 30 seconds after contest and the editorial is published. Damn!!

»
2 weeks ago, # |
  Vote: I like it +1 Vote: I do not like it

Can D be solved using heap? I kept getting TLE on test case 2. Using a priority_queue<pair<int,int>> where the first element is the size of the segment and the second one the starting point (times -1 because of the order needed)

  • »
    »
    2 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Exactly I did this. Luckily it passed for me, have a look at my submission: link

    • »
      »
      »
      2 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Thanks! Glad to know that. If you want to debug my code ^.^: link

      • »
        »
        »
        »
        2 weeks ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        May be u r visiting the same segment more than once or the same array index more than once.

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

        Hey, you are popping the current pair from your Heap, after adding the two new segments(pairs) created! So, basically, your code won’t do, what you are intending to do. Just put the “Heap.pop()” line, above the two “Push” lines and a limit condition for adding the two new pairs, and your code will work perfectly! It is giving TLE, because the pop and push of pairs, isn’t in correct order, and hence, you are visiting the same segment(s) more than once, which won’t empty the queue, in any case, and then the loop will run infinitely! Also, you have to put up a condition to add the new pairs(segment(s)), that will be created, after replacing a “0” element with “i”. Else, your code will add two new pairs every time, and hence, your queue, will keep getting longer and longer!

  • »
    »
    2 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I have solved using a heap. You can see my code.

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

    You should pop before you push. Because pushing an element may change top of priority_queue which will result in poping unwanted elements.

    Secondly on each iteration you are pushing two elements and poping 1 element. So size is increasing. As a result your queue is not going to be empty in near future. You should apply some condition for push so that size doesn't get too large.

»
2 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

What's the score distribution? Are all problems worth the same in div 3? Thanks!

»
2 weeks ago, # |
  Vote: I like it +3 Vote: I do not like it

What was the test case 2 in E ?

  • »
    »
    2 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    check the default case like string with 1's count = 0 or 1

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

    Test 2 contains all binary strings of length from $$$1$$$ to $$$10$$$ with all possible values $$$k$$$.

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

Was there a simpler approach to solve D which doesn't use priority-queues/multi-sets ?

  • »
    »
    2 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I think Priority Queue is more simpler approach compare to any other approach.

»
2 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

i solved prob E and did not solve prob D (sad story .. :'( )

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

Nice round! Well written statements and interesting problems.

»
2 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Can anyone please tell how to hack other solutions?  It is giving error: either testcase or filename must be specified. what to do??

»
2 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Hey guys, I'm new to this platform and this was my first contest. What does the "open hacking phase" mean and when do I find out if my rating increased?

  • »
    »
    2 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    you can through through faq and help section and also google to find out just like i did

  • »
    »
    2 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Now you can see other peoples' solution. If you see an accepted solution will not work for a specific input then give that input and hack that solution.

    After hacking phase there will be system test. After that rating will change. You may need to wait about 14-15 hours for your rating change.

»
2 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

I attended the contest but it shows that I didn't attend. Please help me @admin

»
2 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

please help me in finding what is mistake in my code for problem E (https://codeforces.com/contest/1353/submission/80159424)

»
2 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

can someone pls provide a testcase where this solution for E fails

»
2 weeks ago, # |
  Vote: I like it +1 Vote: I do not like it

Is this fair? @vovuh @MikeMirzayanov

Kindly ban this user who is using multiple handles and hacking one account using the other account-

mamun360 and 550mamun

https://codeforces.com/contest/1353/submission/80148191

https://codeforces.com/contest/1353/submission/80124724

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

    Happens all the time ..also there are no extra points for hacks so chill

  • »
    »
    2 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Also his rating is trash anyways so who cares?

»
2 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Hi guys can I ask about problem C?... I have problem working with big numbers in C++. I'm sure I have declared m, n, and sum to be long long or int64_t but eventually it cannot calculate the correct number to add to sum, and at the end the answer is wrong.

  • »
    »
    2 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Code?

    • »
      »
      »
      2 weeks ago, # ^ |
      Rev. 4   Vote: I like it 0 Vote: I do not like it
      #include <iostream>
      #include <string>
      
      using namespace std;
      
      int main() {
          int t;
          int64_t sum, temp, n, m;
          cin >> t;
          for (int i=0; i<t; i++) {
              sum = 0;
              cin >> n;
              m = n/2 + 1;
              for (int j=1; j<=n-m; j++) {
                  temp = (int64_t) (j*j*2*4);
                  sum += temp;
              }
              cout << sum << endl;
          }
          return 0;
      }
      

      Previously I simply add the new value to sum but as I see it didn't work out I used a temporary variable to hold the value and unfortunately it is still not working

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

        I think that this value j*j*2*4 may overflow before the casting. Try to do ((int64_t)j)*j*2*4

        • »
          »
          »
          »
          »
          2 weeks ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          lol no shit how could it be like this it worked man. i don't know yet why and how but thank you for this i'll try to understand

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

            When C++ is evaluating an arithmetic expression it holds temporary values on variables of the biggest type involved in the expression. In this case the biggest type is int.

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

        Notice how you cast into an int64_t AFTER you do the operation. However, since all j, 2, and 4 are integer values, the value inside the parentheses will overflow.

        Try temp = (int64_t)((int64_t)j*(int64_t)j*(int64_t)2*(int64_t)4); and it should work (this is very explicit, the following also works (int64_t)j*j*2*4).

      • »
        »
        »
        »
        2 weeks ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Thank you guys this is phenomenal this will help me overcome a shit load of other prroblems. I've always been shaking my head when I see a casting problem, and having to deal with big numbers in C++. I will forever remember this.

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

    The biggest value that can be generated by some input is 125000000000000000 ( actually this value is a little bigger than the biggest value that can be generated by some input ) which fits into a long long int variable.

    • »
      »
      »
      2 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      I'm fully aware of this but for some reason the result for the last pretest input is 6229295798864 and not 41664916690999888

»
2 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

How to solve problem E. Thanks in advance

»
2 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Can anyone help me understand why this code is throwing runtime error. https://codeforces.com/contest/1353/submission/80152681

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

Hello, good time MikeMirzayanov in this submission look like guy who hacked it create 2nd account for it and submit an code that have a bug for hack it with him/his 1st account submission: https://codeforces.com/contest/1353/submission/80164801 bug is this part: if(n==165) { cout<<n<<"\n";

  • »
    »
    2 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Not only this, 80147785, 80151297, this two solutions are similar except the variable name, and the solution of Problem A of the authors of above mentioned solution was also similar and got hacked by same person.

  • »
    »
    2 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    It's cheating!

»
2 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Has anyone solved D using recursion? I tried but got WA. Any help would be appreciated, because that's the first thought that came to my mind after spending sometime on the problem.

  • »
    »
    2 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Yes, I used a recursive approach to solve the problem. However, instead of using the built in computer stack, I used a priority queue.

    See my AC submission for more details.80164051

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

My solution for problem F is essentially O(N^2 * M^2), and unsurprisingly it is slow (but it runs within the time limit luckily). Is this the intended time complexity, or is there a solution which runs in O(N*M*(N+M))?

Here is my code, 80169304.

  • »
    »
    2 weeks ago, # ^ |
    Rev. 4   Vote: I like it +13 Vote: I do not like it

    Lol. At least it got an AC.
    80141105 was the only soln is python which got accepted in the contest.
    Only one soln in python is accepted so far 80171692 credits pajenegod.

    TL;DR; Vovuh Just don't enforce long ints in div3 just for the sake of it.

    Yet another rant about python.
    • »
      »
      »
      2 weeks ago, # ^ |
        Vote: I like it +3 Vote: I do not like it

      Don't you think that I set such constraints for safety? I don't know if there are some $$$n^2\sqrt{a}$$$ solutions which can get accepted, but even with $$$a_{i, j} \le 10^9$$$ the answer doesn't fit int32. So I could make $$$a_{i, j}$$$ up to $$$10^7$$$ or maybe even less, and what then? Maybe with this constraints there are $$$n^2 a$$$ solutions which can be good optimized? Do you know? I don't. But they can be.

      It is not a surprising fact that the last problem of Div3 is something like Div2C-Div2D. And anybody knows that Python's speed sucks. And anybody knows that C++ is the fastest language and some problems are just not for Python. I know that this is Div3 but if the participant can solve the last problem then he need to understand that the solution written on Python or PHP or Ruby or other slow languages could not be accepted.

      • »
        »
        »
        »
        2 weeks ago, # ^ |
        Rev. 4   Vote: I like it +18 Vote: I do not like it

        Here is how it works with PyPy. 32 bit PyPy (which is what codeforces uses) is able to work efficiently with small integers (corresponding to C long) and with floats (corresponding to C double). So normally when I need performance for say a n = 1e6, A[i] <= 1e9 problem, I can just use floats (which have integral precision <= 2^52 approx 4.5e15). So in the case of today's F, had max been 1e13 instead of 1e15, I would have had a much easier time.

        In general I get that there are problems where it makes sense to involve large integers. However this problem is one where I don't really see the point of making A[i] <= 1e15. Just the usual 1e9 would have worked just as well.

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

          Well, I already said that we don't know if there are some non-intended solutions which can get accepted if $$$a_{i, j}$$$ could be up to $$$10^9$$$. Moreover, I didn't know anything about PyPy background so I couldn't imagine that something like $$$10^{13}$$$ will be better than $$$10^{15}$$$ in this problem. I said that I set such constraints to make the answer fits in int64 datatype (even more, make the answer significantly less than $$$10^{18}$$$ because a lot of users uses $$$10^{18}$$$ as 64-bit infinity) and cut off all possible bad solutions.

          Also, my point about using faster languages for hard problems, remains. I checked a bit of your submissions and see that some of them are tightly fits the time limit so I think you knew that PyPy can be very slow in some cases. I agree that I could make the constraints better but, from my point of view, I didn't see significant reasons to do that.

          This is also my bad that I didn't write the Python solution and I'm sorry that I didn't do that and didn't check how it fits. Anyway, I cannot do anything with it right now.

          • »
            »
            »
            »
            »
            »
            2 weeks ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            I cannot do anything with it right now.

            We know just wanted to point it out for future div3s.

            I checked a bit of your submissions and see that some of them are tightly fits the time limit

            Those are someone else's submission. He asked him why he got TLE on that and how to improve it. Pypy3's IO is slow same soln written in Pypy2 will run fast. His in contest soln takes Time Limit/2 except for this F.

            On a side note, he knows Python is slow but he also knows a lot of cancers in python.

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

              As you can see, my previous reply was to pajenegod so I talked about his submissions.

              The last thing I want to say in that discussion is: I hope nobody forgets that the competitive programming is about efficienty. And slow languages are completely don't about it. Don't you think that we need to learn newcomers that cp problems need to be solved efficiently? If we don't do that there, then after reaching div2 they'll stuck on anything because any algorithm or data structure in such languages is about 10 times slower than in Java or C++. I think it's better for them to understand that slow languages are not good for solving hard problems as soon as possible. Moreover, 5 out of 6 problems were python-friendly, so I don't know what else to ssy. My point of view is just different.

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

                Just to clear confusion here. You misunderstood my last comment.
                I was talking about pajenegod's submissions which you said were slow. Pajenegod's in contest submissions takes less than TL/2.
                Someone wrote that slower code and asked pajenegod in AC discord server for help. He submitted that code.

                Anyways let's stop this debate here. It can go long. Its completely upon you how many problems you want beginners to solve. I completely agree that one should choose the best tools. We just wanted to point it out because next time we may have a similar problem with easier problems. These days you try a lot to make easier problems slow languages friendly (Thanks :) ). If one looks at recent div3's he can clearly see are a trend that constraints of easier problems are set in such a way that slow input-output languages don't get TLE.

»
2 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

I am trying to learn C++ as I usually use Java. I had a question regarding DP problems in C++. Often, a vector cannot be used in recursion, so is an array preferred? I was thinking one way to still use a vector is to give an initialize max size so we can treat the vector as an array and access indices but is initializing a vector with a specific size really slow (I used a vector with 10E6 size and TLEd)?

Furthermore, if I do use an array, how can I initialize all elements to a value as fill_n(begin(dp), size, INF) gave a run-time error.

Thanks!

  • »
    »
    2 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Why a vector "cannot be used in recursion"? Or asked other way: What can you do with an array what you cannot with an vector?

  • »
    »
    2 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Try passing reference to vectors rather than their values. If I am not wrong arrays are passed by reference. There is a quite time overhead in passing by values(as it makes a copy and passes)

»
2 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Can someone please provide the solution of Q4 i.e D: Constructing the array in python or probably pypy3?

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

    Using Heap...Maintain max-heap for the length of segments simultaneously with min-heap with a lower index of the segment. Code

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

      it was very helpful thanks

    • »
      »
      »
      2 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      hey i have not submitted the code yet but can this solution be acceptable ,i have done this after seeing the editorial but i am not sure it will be accepted or give TLE I will also submit the code once system testing is done code is here

      • »
        »
        »
        »
        2 weeks ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Even after System Testing, My code is ACCEPTED. That means NO TLE.

  • »
    »
    2 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    check abundis submission...it is very lucid..

    • »
      »
      »
      2 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      sorry but i don't think he gave this contest

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

        he did...but if you are not able to view his..check mine(after system testing)...it is pretty much based upon his implementation

»
2 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Hey, I'm new here. It was my first contest. I solved A, B and C. Curious to know when will my ratings be updated. It's still not showing anything on my "Contests" page.

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

    Be patient, it takes some time.

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

    Div.3 contests have an open hacking phase (12 hours) followed by a system testing for all submissions. The ratings will be updated once the system testing is over. It may take some time, however, even after system testing is finished. Welcome to CF!

»
2 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

MikeMirzayanov ,Sir I am really sorry for the miskate which I did in last round Div3( round#642). I already logged in my old account and I submitted 4 problems then suddenly I realized that this is not my current and permanent account then I resubmitted all the 4 previous problem + one more problem E in my current account not in old ones. Sir please look at this situation. Both are my own account and It didn't happen intentionally. please don't skip my solution all solutions are my own. I promise that it will not happen again in future.

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

MikeMirzayanov My submissions were skipped for this round. First I thought it is just a mere coincidence that my solution matched with someone's but then I googled and found out that one should not write code in ideone for contests. I have been using ideone since I signed up on codeforces but have encountered this issue for the first time. :(

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

Why did my rating fall ? It was supposed to be increasing by +16 according to cf rating predictor ? Can anyone tell me the reason ? Thanks in advance .MikeMirzayanov

»
2 weeks ago, # |
Rev. 6   Vote: I like it +101 Vote: I do not like it

Vovuh MikeMirzayanov
I made 25 MLE hacks using pajenegod's test case which TLEed my soln 80141105 . I see ratings got updated but I can't find that test case in system tests (same soln passes 80201283).

Since ratings are updated and only 3 test cases were added in system tests.
Question 1. Is there a system testing phase in Div3? Or if nobody hacked you mean your soln is an AC.
Question 2. If there is one then why was this hack ignored?

26 solutions were hacked using this test case among 127 successful hacks in the round (more than 20%). Shouldn't this be a sufficient reason to blindly add this hack in system tests?

Brief description about the hack
»
2 weeks ago, # |
  Vote: I like it -9 Vote: I do not like it

there are two users @yomna62 and @yes_gg i don't even know them they copied my code from ideone during the ongoing contest yesterday Actually i had updated my chrome and due to that ideone.com had become public again instead of private. These users even copied my template as it is. I would request the codeforces community to please look into the matter as these cheaters don't deserve to be taking a part in such contests. When i saw their previous submissions after the system mail came to me then i realised that most of their verdicts are skipped and that means they copy codes very often Their account must be banned with immediate effect as they create a sense of hatred within the coders community. i am sure that community will understand my problem and i am ready to provide any further evidence to prove that the code they used was unique for me.They copied my code and i can show through my previous submissions on different platforms that the template is mine only

»
2 weeks ago, # |
  Vote: I like it -9 Vote: I do not like it

I have two ID .. one is TestCase22 and other one is AzmayenSabil. I submitted solutions both from these two ID. Today morning I got a warning saying that I have performed plagiarism. But those two ID belong to me.

What should I do now. Or should I disable one of my irregular ID ?

»
2 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

i had solved 3 problem a,b,c and it got accepted in first attempt still my rating decreased by 48 ,can someone explain how we are rated in these contest

  • »
    »
    2 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    The time you took to solve the questions matters too. There were participants who solved three questions but are ahead of you because they solved them early. In the end, you need to look at your rank and previous rating. For rating 1363 you need to be at least around 5k.

»
2 weeks ago, # |
  Vote: I like it -9 Vote: I do not like it

I got an email about the violation . actually both the accounts are mine I submitted the same code from my two different accounts is it illegal?? I DONT KNOW if its illegal I am sorry .

»
2 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Does anyone know why this unusual time?

»
2 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Problem E has a greedy tag. Can anyone explain the greedy approach to E?

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

This contest is bullshit(mozakhrafff )=))))

»
13 days ago, # |
  Vote: I like it 0 Vote: I do not like it
#include <bits/stdc++.h>
#define fastio        ios_base::sync_with_stdio(false); cin.tie(NULL);
#define ln            cout<<endl;
#define vi            vector<int>
#define vll           vector<long long>
#define sortl(vec)    sort(vec.begin(), vec.end());
#define sortr(vec)    sort(vec.rbegin(), vec.rend());
#define forn(i, x, n) for(int i = x; i < int(n); i++)
#define in(vec)       for(auto &it : vec) cin>>it;
#define loop(vec)     for(auto &it : vec)
#define	out(vec)      for(auto &it : vec) cout<<it<<" ";
#define ll            long long
#define mod           1000000007
#define debug(x)      cout << x << endl;
#define pb			  push_back
#define mp            make_pair
#define um			  unordered_map
#define pii			  pair<int, int>
#define pll           pair<ll, ll>
#define f             first
#define s             second
#define dp3d(n)       vector<vector<vector<ll>>>dp(n, vector<vector<ll>>(n, vector<ll>(n)));
using namespace std;

ll power(ll x, ll y, ll p) {
	ll res = 1;
	x = x % p;

	while (y > 0) {
		if (y & 1)
			res = (res * x) % p;

		y = y >> 1;
		x = (x * x) % p;
	}
	return res;
}

ll modulo(ll a, ll b) {
	ll c = a % b;
	return (c < 0) ? c + b : c;
}

struct cmp {

	bool operator()(const pair<ll, pll> &p1, const pair<ll, pll> &p2) const {


		if (p1.f == p2.f)
			return p1.s.f < p2.s.f;

		return p1.f > p2.f;

	}
};

int main() {

#ifndef ONLINE_JUDGE
	// for getting input from input.txt
	freopen("input1.txt", "r", stdin);
	// for writing output to output.txt
	freopen("output1.txt", "w", stdout);
#endif

	fastio
	ll t;
	cin >> t;
	while (t--) {
		ll n;
		cin >> n;
		vll ans(n + 1);
		priority_queue < pair<ll, pll>, vector<pair<ll, pll>>, cmp>pq;
		pair<ll, pll> m;
		pq.push(mp(n, mp(1, n)));
		forn(i, 1, n + 1) {
			m = pq.top();
			pq.pop();
			ll mid = (m.s.f + m.s.s) / 2;
			ans[mid] = i;
			if (mid - 1 >= m.s.f) {
				pq.push(mp(mid - m.s.f, mp(m.s.f, mid - 1)));
			}
			if (mid + 1 <= m.s.s) {
				pq.push(mp(m.s.s - mid, mp(mid + 1, m.s.s)));
			}
			//cout << pq.top().f << endl;
			//cout << pq.top().s.f << " " << pq.top().s.s << endl;

		}

		forn(i, 1, n + 1)
		cout << ans[i] << " ";
		ln

	}
	return 0;
}


Can anyone explain why in this code custom comparator is not working properly. I'm not able to debug it