vovuh's blog

By vovuh, history, 6 weeks ago, translation, In English,

<almost-copy-pasted-part>

Hello! Codeforces Round #624 (Div. 3) will start at Feb/24/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.

Good luck!

</almost-copy-pasted-part>

Thanks to Artem Rox Plotkin and Dmitrii _overrated_ Umnov for help with testing the round!

UPD: It turned out that in the problem C, such a test exists that the answer overflows 32-bit integer type (int). Since such a test was not in the test set, many participants made such a mistake. We decided to forbid such tests, additionally guaranteeing that the answer fits in int.

UPD2: Editorial is published!

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

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

[DELETED]

»
6 weeks ago, # |
  Vote: I like it -18 Vote: I do not like it

finally... I am excited

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

Finally a good freaking round

»
6 weeks ago, # |
  Vote: I like it -12 Vote: I do not like it

newbies will rock it

»
6 weeks ago, # |
  Vote: I like it -13 Vote: I do not like it

Can anyone help me how to hack a solution ? With detail's . Thanks in advance.

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

    On the dashboard, click the padlock icon for locking a problem (Note, that you can not send your solution for a problem after locking it). Then go to room results, where you can see roommates codes for the problems you've already locked (you can see a certain solution by double clicking on it in the room results table). After you've opened someone's solution, you can consider it and then hack it. When hacking a code, you're entering some testcase on which that code is most likely going to fail (it may be wrong answer, or running out of time/memory limit). When you want to enter a large testcase, you can send test generator instead of typing it. Test generator must be your program which produces a file with a testcase in it. After hacking a code, you can see hacking results. There are two possible outcomes: "Successful hack" — it means the code failed, and you're rewarded with 100 points for that. Otherwise, it's "Unsuccessful hack" (the code did not fail) and you get minus 50 points for that.

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

    In div.3/educational contests, you can not hack any solutions during the coding phase. In the hacking phase which follows the coding phase and lasts for 12 hours, you can hack any solution. Just double-click somebody to view his/her submissions and then click "hack it!" button.

    there will be no points for successful hacking attempts and no penalties for unsuccessful ones in div3/educational rounds.

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

      So in div3/edu contest. If I failed to hack someone's code, I wont get minus 50 points right ?

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

3 rounds in 2 days is very cool!

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

vovuh writes them better : ), thanks

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

Hope to solve 4 or more question in this contest

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

< almost-copy-pasted-part >

: )

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

Div3 gives confidence

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

    Yeah have the confidence that i will never be a specialist ever :'(

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

      Never say never

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

      you have just read algorithms and solve lots of high rate problems from it and you will become specialist at least :)

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

///786///

Div 3 is good for newbie like me :D

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

Is it rated?

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

    It's rated for Newbies, Pupils and Specialists. It is also rated for Experts who have taken part in at least two rated rounds (and solve at least one problem in each of them).

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

I don't like only Div.3 contest. Actually most people is more than 1600.

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

    But in last div-3 contest there was 9000+ participants!

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

    But they can take part out of the competition. It won't decrease the happiness of doing a contest. So Div.3 is very nice since it's easier and more people can have fun!

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

If you want more contests so please donate the codeforces 1000$ or more

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

If i register the contest but will not submit in the contest, will my rating change?

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

Exiting to join the contest <3 Hope that I can solve A-B-C and dont get any stupid mistakes <3

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

Let's Hope Everyone gets a positive change in their ratings :)

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

Smiley face

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

Sorry I am a newbie,I wanted to ask what does it mean "The penalty is 10 minutes".Is it literal that 10 minutes will be deducted from our time,if we have a wrong submission or is it something else?

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

    if you submit a wrong solution and then submit the right solution afterwards, the accepted time of submission will be +10 minutes of that. more wrong answers mean more +10 minutes..

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

      Ok Thanks for clearing that. Just a question suppose I submit a wrong solution and then submit a right solution at just the end of a contest what will the accepted time of submission will be, is it going to be more than 2 hours in this case?

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

    Short answer:

    No it doesn't, it just is basically something that makes your score for that problem worse.

    Long answer:

    Basically in Div3 (and Educational Rounds or any other rounds that follow ACM-ICPC format), your score is calculated a bit differently from normal CF rounds. Participants are first ranked by the number of problems they solved. After that ties are broken by a so called "penalty".

    This penalty has two parts to it:

    • The sum of times of your submissions.
    • The wrong answer penalty times the number of wrong answers on problems that you solved afterwards. (that is if you get a wrong answer on a problem and don't get accepted till the end you wont be penalized for those wrong submissions)

    A person with a lower penalty is ranked higher.

    Consider for example the following contest with 3 participants — A, B and C and a wrong submission penalty of 10 minutes:

    • A solves 2 problems, the first at 5 minutes and the second at 30 minutes, with no wrong submissions on either.

    • B solves 2 problems, the first at 5 minutes and the second at 25 minutes, but makes a wrong submission on the second problem before submitting the correct solution.

    • C solves 3 problems, the first at 10 minutes, the second at 40 minutes and the third at 1 hour 20 minutes.

    So A has solved 2 and has a time penalty of 5 + 30 = 35 minutes,

    B has solved 2 and has a time penalty of 5 + 25 + 10 = 40 minutes, and

    C has solved 3 and has a time penalty of 10 + 40 + 80 = 130 minutes.

    As we sort them first by number of problems solved then by penalty, so the final standings will be:

    • C (3, 130)
    • A (2, 35)
    • B (2, 40)
»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

It would be great if more div 3 contest held because new competitive programmers can better start. Div 2 contests are quite tough for beginners. Thanks for this contest.

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

Schrodinger's Problem Number

»
5 weeks ago, # |
  Vote: I like it -30 Vote: I do not like it

F***K MY LUCK!!! on problem c, my code has diffrent output on CF system than my own!!! And of course it's wrong on CF

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

OMG first time I solve D <3

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

How to Solve D? I tried thinking of it in multiple ways, but all my approaches seem to fail.

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

    Fix B.Find A and C greedily.

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

      Does there exist a proof that this approach will always work?

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

        You can simply try all possible solutions in time. code

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

          That's So Cool! I never thought that brute force would pass.

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

            Well, it was hacked. So don't be too sure yet.

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

              How does the hack work?

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

                I'm guessing that it's because you're only going upto $$$10^4$$$ instead of $$$2*10^4$$$

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

                  Ah, I see, the input is limited to 1e4, but not the solution space. Sic shit.

                  So, 10000 100000000 1000000000000 could be a valid answer for some input.

                  Edit: It turns out that a,b,c should be all below 2*1e4, because if not there is a better solution. So, this code uses same algo but works better.

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

                  What should be the output for : 1 481 777 10000?

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

                  How did you decide the size of solution space ? Why 2e4 ?

                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  5 weeks ago, # ^ |
                    Vote: I like it +9 Vote: I do not like it
                  113
                  385 770 10010
                  
                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  5 weeks ago, # ^ |
                    Vote: I like it 0 Vote: I do not like it

                  One possible sol is allways 10000 10000 10000 for any input where max(a,b,c)==10000.

                  The max diff is 9999*2. So the max value for b and c cannot be more than 20000, whatever a is.

                  Not sure if this counts as a prof ;)

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

                  Why only 2e4 ? How did you come up with that upper bound?

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

                  We only have to show that a goes to A, b goes to B and c goes to C (you can prove this by considering all cases in the number line). Then you can show that B must be less than c+a. This can be proven by contradiction. So actually you only need to test it for 1<=B<=c+a

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

                You need to check values up to 10k + epsilon for test such as

                73 73 10000

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

                  How to decide that epsilon value?

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

                  20k should be more then enough (since if go up to 20k we can achieve all values in [0, 10k] with a smaller cost)

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

                  10.5k is enough. not 20k.

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

                  10^4 + 32 is enough. And no less because of:

                  1
                  176 3344 10000
                  
                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  5 weeks ago, # ^ |
                    Vote: I like it 0 Vote: I do not like it

                  I_love_chickpea can you please explain, how did you concluded +32 would be enough?

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

                  We can slightly modify the model solution to pick out of answers with minimum distance the one with minimal value C.

                  Now for a fixed triple $$$A_0, B_0, C_0$$$ such that $$$B_0$$$ is divisible by $$$A_0$$$, $$$C_0$$$ is divisible by $$$B_0$$$ and $$$C_0 > 10^4$$$ if there is a testcase for which this triple will be the only valid answer, then one of them will be testcase $$$min(A_0, 10^4), min(B_0, 10^4), min(C_0, 10^4)$$$. We can just run the modified solution on this test, if it says the minimum value of $$$C$$$ is $$$C_0$$$ it means that there is a test, which requires checking values of $$$C$$$ up to $$$C_0$$$.

                  Now just run it for larger and larger values of $$$C$$$.

                  Code

                  I ran it for $$$C <= 20000$$$ and found nothing larger than $$$10^4 + 32$$$.

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

          Your solution for D has been hacked but it's still showing in standings

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

      I fixed A and then find B as A*j and then find C as A*j*f.

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

    you find all pair of a and b from 0 to 10^4(maybe more for safety) for every pair of a and b you find suitable third number nearest to original c. it probably cost you about n*log(n) for every test case.

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

      So it will be O(10^8)*100 = O(10^10) operations right ? How did it pass the time limit?

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

        No of course. let's call first number is a,second is b. we want a is a divisor of b. so we just start from a then go to 2a,3a,4a.to find every pair of a and b.it's only cost you about nlog(n)

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

          it's just like erastothenes sieve without prime number

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

          No, I am not sure about this. This is n^2.

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

            errrrr it's running in n+n/2+n/3+n/4+...+1 which is prove less than nlog(n)

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

            I'm not sure if i'll get hack xD but i believe in my solution

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

              I got your solution, you are right. I just upsolved it now. Sad :(

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

          i think this is (n^2)/2

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

      How can this algorithm cost n*log(n)?

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

    Make all the possible combinations (A, B, C) with for-loops and compare them with the given (a, b, c)s.

    The key is that neither of these three should exceed 10^4. (If they did, they would in itself be not the efficient solution) I have found just a bit fewer than 5X10^5 cases which satisfies (A, B, C). Thus, given that the test cases are 100, 5X10^7 seems like a good deal.

    Brute force, if applied properly, can be a very powerful tool.

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

      Since it is a hack
      Corrected:- just a small change that neither of three exceed 2*10^4 instead of 10^4 only

»
5 weeks ago, # |
  Vote: I like it -12 Vote: I do not like it

speedforces

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

I want an editorial ASAP :(

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

why is my code not correct in test2 about problem b?

https://codeforces.com/contest/1311/submission/71794691

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

How does one solve F with a complexity lesser that O(n^2) ? We at least need to consider all the pair of points for the minimum distance between them.

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

    I'm also want to know it :(

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

    The non-integer part is really helpful here — distance between points i and j will be either 0 (if they overlap), or starting distance (if they diverge). You can easily see, that for i < j if vj < vi then distance is 0. So, for each i we can find sum of xj such that vj >= vi (I scaled speeds to fit in a segment tree) in logarithmic time, then we can calculate everything in O(n log n).

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

    Hint:

    Here's how you would find the sum of the differences between all pairs.

    Sort the array. Set sum = 0. Note that for every number, it will be subtracted from the sum a (number of numbers greater that it) of times, and added to the sum a (number of numbers lower than it) of times, so you can solve the problem in O(NlogN).

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

      Can you please elaborate? I don't understand your solution fully.

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

        His code: (https://codeforces.com/contest/1311/submission/71790025)

        He didn't describe his actual solution yet, just an $$$O(N)$$$ way to calculate (xj-xi) for ALL pairs i<j. But then he goes through again in one pass, and removes those (xj-xi) which didn't satisfy (vj>vi).

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

          Still slower than most solutions

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

            2-D Segment tree approach can be very fast in this problem

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

          I think I get the solution now after 2 hours of thinking. Maybe this example can help someone else. Say $$$x=[100,50,75,25]$$$, and the corresponding sorted $$$v=[1,2,3,4]$$$. First we sort $$$x=[25,50,75,100]$$$. Then look at the ways 75 gets added initially according to @golions comment:

          $$$+75, +75, -75$$$

          (from 75-50, 75-25, and 100-75)

          Now let's iterate through $x$ in sorted $$$v$$$ order: when we get to the third element 75, we see that we should only have a single

          $$$+75$$$

          term due to the

          $$$75>50$$$

          . Coincidentally this equals the net sum of the three terms above. The reason is that if $75$ has the same rank in both the sorted $$$x$$$ and the sorted $$$v$$$ versions, then there is a symmetry in how $$$[25,50,75,100]$$$ mutates into $$$[100,50,75,25]$$$: we can let other elements "jump over" 75 to anywhere on the other side, and the symmetry is that the number of jumps going right over 75 equals the number of jumps going left: 100 jumped left, but then 25 jumped right. So the rank of 75 is equal in both cases, and we don't need to correct the $$$+75,+75,-75$$$ in our final answer.

          Another case is $$$25$$$, which is rank 1 with respect to $$$x$$$, but rank 4 with respect to $$$v$$$: Initially we had

          $$$ -25, -25, -25 $$$

          due to 50-25, 75-25, and 100-25. But because the rank changed from 1 (w.r.t $$$x$$$) to 4 (w.r.t $$$v$$$), we must have had 3 jumping overs to the left: and every such jumping over means we shouldn't have included a $$$-25$$$, so we correct with $$$+25$$$ 3 times, and end up with $$$0\cdot 25$$$ in the final answer.

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

        Say you have the numbers 1,2,3,4.

        The sum of differences is 2-1 + 3-1 + 4-1 + 3-2 + 4-2 + 4-3. Note that it's also equal to 1*(-3+0) + 2*(-2+1) + 3*(-1+2) + 4*(0+3). First number in parenthesis (that you subtract by) is the number of numbers that is greater than that number, and the second number in parenthesis (that you add) is the number of numbers that is less than that number.

        This is not the solution to the entire problem, just part of it.

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

    I think NlogN can be achieved with PBDS or compression with segment or fenwick tree, just use contribution technique.

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

Is this comment (https://codeforces.com/blog/entry/11310?#comment-162921) the right strategy for F?

I reduced the problem as follows: first sort by x[i]. Then for every i, sum (x[i]-x[j]) over j<i such that v[j]<=v[i]. Brute force would be $$$O(N^2)$$$.

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

    If for every i, you consider all j<i, won't you do 1+2+3....(n-1) = n(n-1)/2 number of operations which is O(n^2) ?

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

      Yes via brute force, but if you do the sqrt decomposition, you could sort by x[i], then put all pairs into a $$$\sqrt{N}\times \sqrt{N}$$$ grid, and sort each row by v[j]. Then given $$$i$$$, you can compute the number of $$$j$$$ which have both $$$x_j<x_i$$$ and $$$v_j<=v_i$$$, in $$$\sqrt{N} \log N + \sqrt{N}$$$ time. However given the constraints this approach might be around $$$10^7$$$ or $$$10^8$$$ operations. There is a better way given in other comments, so my question is moot.

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

i think d will be hacked most...

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

Perhaps it is psycholigal problem...but again I did not solve B :/

At least somebody tell me what is wrong with this code

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

I am in a great trouble..I don't know when will be the end of newbie era from my life..Really I am depressed..So,what can I do???

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

I'm getting Unexpected verdict while trying to hack a solution for problem C.

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

hey im new in everything, is there a post afterwards with the solutions? if not how to solve problem c? i got runtime error all the time.

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

    Yes there are. it's called editorial

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

    I also got a runtime error once. Mine was because the array size I declared was 10e5 (not sufficient). I changed the array size to 2*10e5 + 5 (according to the constraints), and it got accepted.

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

What is the hack of D?

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

Noooo vovuhhh nooooo

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

in D I used 4*10000 that gives TLE but 2*10000 was ok. is there any other approach for solving D.

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

Very strong tests in problem D!

Your WA
Answer is
To hack, use this test
»
5 weeks ago, # |
  Vote: I like it +1 Vote: I do not like it

hey ? No hacking phase?

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

    According to codeforces... Hacks will be open in ~10 minutes.

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

My solution for E : First arrange nodes so as to achieve max depth sum (mis concluded this part for like 20 mins), ie, a linear chain.Now consider the node at the bottom and move it up greedily as much as possible so that the change in answer is less than equal to current answer — required depth sum.(Initial answer is sum of depths of all nodes in the linear chain).If we cannot move a node anymore upward and we do not have the required answer, then it is not possible to form such a tree, otherwise it is.

Could anyone confirm this?

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

    I made the opposite: first construct a balanced binary tree (parent of x is x/2), then on each iteration take two deepest leafs v1 and v2, and attach v2 to v1. On the last iteration, maybe, you should attach v2 not to v1, but to some its parent.

    Each vertex is moved at most once, so it is N^2. Looks like it is possible to do it in NlogN, but we don't have to do it.

    It passed stress test for n, d <= 50, I think it is correct.

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

      Actually thanks for the idea of stress testing, i forgot the input is only n and d so it can be confirmed for all values of d in range vmin to vmax that answer is found by the code or not.

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

Where is hacking phase? Just hacked someone's code and it crashed...

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

How to solve E guys ?

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

    I don't have proof(maybe someone can hack it), and use a random method(pretty fast).

    first prep lower_bound&upper_bound of n. it's easy to note $$$ub[n] = n*(n-1)/2$$$. while $$$lb[n]$$$ can be find recursively, each time you divide $$$n$$$ almost half. i.e. $$$lb[n] = n-1 + lb[x]+lb[n-1-x]$$$, where $$$x=n/2$$$.

    then try divide&conquer, for random $$$x$$$ and valid $$$n_x$$$, and so other son should valid. Since in intuition there should be many valid partition.

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

      Sorry, I am just begin to learn Graph (5 dáys). Can you go in more detail. Thanks <3

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

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

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

why it-my[tst].begin(); isn't giving the expected value that was so weird wasted 1 hour trying to figure it out

here's my submission

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

Is anyone facing issue of illegal contest id while hacking??

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

    if you use vector instead of set it is O(n)

  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
            for(int i=0;i<n;){
                
                int j=i;
                while(pos.find(j)!=pos.end())j++;
                sort(a.begin()+i,a.begin()+j+1);
                i=j+1;
                
            }
    

    Are you sure it is O(n log n) ?

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

      B is easily O(n) using dp[i] sum from 1 to i-1 ( sum of how many each element occurs in range 1 to i-1) Also B can be done using segment tree in nlogn Solution above isnt nlogn, it is something like n*logn*logn

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

    how to prove it ?

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

    This isnt nlogn, it is nlog^2n

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

      For every segment of length L, sorting will take LlogL, sum of all L is at max N. How is it nlog2n ?

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

        But you sort it in cycle, shouldn't the complexity be n*(LlogL) which can be n*log^2n

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

vovuh Some people are hacked but their submission still apear in scoreboard (such as https://codeforces.com/contest/1311/submission/71798202). Is it what the contest want?

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

    I think that is because of at some moment hacks were disallowed but uphacking was allowed. So, it seems like you hacked this solution during the uphacking phase and it is considered as correct (but uphacked) solution.

    And I don't know what I have to do with it.

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

Why was case of overflow not considered. :rage: . So what if many people fail.Will u add test cases manually everywhere where people fail. Totally unfair.

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

Why is 71783447 accepted, not hacked?

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

    Probably because they changed the accepted condition

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

      I made a mistake, they changed condition on C. But the mistake seems fair, why did they do it?

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

    Wow, this is new to me too

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

Can anyone hack my B and D? I have written bad codes and think they can be hacked

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

Codeforces Hack Round #624 (Div. 3)

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

Problem D should have such test case instead of getting hacked for almost the whole contest

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

    Most people considered A,B,C <=1e4 including me which lead to hacking :(

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

      the fix is super easy it is really stupid test case

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

This contest is too unfair. You fixed the test case for C while you didn't do anything for problem D. It was a fair mistake done by contestants in problem C. Why did you do this unfair thing?

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

    Face reality, the whole universe is not a fair thing. It is a competition.

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

vovuh Why did you change C? If the change in C was fair then you should change D too. Or undo the changes.

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

Very bad round. One of the most unfairest rounds in Codeforces. Half of the people got hacked in D and you didn't do anything there. But you changed the condition of C.

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

Very good round but unfortunately too weak test cases. I fell from 500 to 2500 after hack. It is unfair that you ignored hacks on C but not for D.

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

The test data of question C in this competition does not exceed the 32-bit integer range, so do you calculate the rating this time?

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

Why are you ignoring us vovuh? What if high rated guys protested? Would you be so silent like you are now?

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

    please stfu, like you didnt even participate in the contest, what is your problem?

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

    cyan revolution is only a matter of time..

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

SPEEDFORCES!!!

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

In fact, both C and D has poor test case and that's not problem. but why you change only C?

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

    We changed only C because we had a bug in author's solution. I didn't have overflow tests (both mistakes in C and D are mine and I'm very sorry about that) and only one of three solutions considered overflow with #define int long long. So we considered to change the constraints in such a way that this issue will not affect participants because I had a problem in my solution.

    The problem D issue is that it has very bad tests and I wonder how I don't have at least one test case (of hundreds test cases) with $$$C > 10^4$$$. It was really surprising for me and I don't even know how to generate such tests in advice (the only way I understand is to write such a wrong solution and stress it).

    Anyway, this is just an excuse and I blame myself for these mistakes. Sorry everyone who was affected by my poor brain work.

    UPD: And for all who think that I'm silent and don't want to accept my mistakes or describe you the situation. I'm so silent because now I just trying to do all I can: write the editorial as soon as possible and I trying to do that right now.

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

      You can easily modify the model solution to minimize first: number of moves, then minimize C. Now iterate through all valid triples $$$A, B, C$$$ such that C lies in range $$$(10^4, 10^4 + 20]$$$, run modified solution for triplet $$$\min(A, 10^4), \min(B, 10^4), \min(C, 10^4)$$$ and if it says, that optimal solution has $$$C > 10^4$$$ we just found a countertest.

      In the same manner you can defeat a solution, that assumes too tight upper bound on $$$B$$$ like 71800958

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

        Okay, I see. Thank you for explanation! But I didn't even think that the issue "$$$C > 10^4$$$ in the answer" will affect and break such amount of solutions.

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

          So just to confirm, submissions that display as Accepted, but are actually hacked, that depend on $$$A,B,C<=10^4$$$ will be judged as WA/Hacked?

          For me the difference is between +149 and -5, so I'm a bit on edge :D

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

            As you saw, the actual bound on $$$C$$$ is a bit larger than $$$10^4$$$, so I think that all solutions that only consider $$$C \le 10^4$$$ will be rejected.

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

what is approach for E and F?

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

    Can u explain D

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

      iterate over value of c(1 to 3*1e4) and for every c make a tuple {a,b,c} which holds property (c%b==0 && b%a==0) where a and b which are factors of c. So, now one of this tuple is answer.

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

      just fix A and B then check that C which lie very close to c and satisfy the condition that $$$A$$$ divides $$$B$$$ and $$$B$$$ divides $$$C$$$ . Now for fixing A and B you can iterate A from 1 to say 10000 and B as a multiple of A from 1 to say 11000 simply like in seive algorithm .

      NOW after fixing A,B and nearby C you have to calculate that this A,B and C deviates how much from original a,b and c . Iterate in the above described value and calculate the minimum value. Simply Cool Algorithm.

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

What is the largest possible answer in problem D? The largest I found is:

Input:
6500 8000 10000
Output:
3500
5000 10000 10000
»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

How long does it take to update my rating after contest??

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

Nice contest !! Problem statements were clear and easy.

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

Help me with how you approach Problem D

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

    Just do three loops for three variables, and check for minimum answer Something like this: for(int i=1;i<=10300;i++) for(int j=i;j<=10300;j+=i) for(int k=j;k<=10300;k+=j) if(abs(a-i)+abs(b-j)+abs(c-k)<ans) ans=abs(a-i)+abs(b-j)+abs(c-k),a1=i,a2=j,a3=k;

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

      This will give TLE I think, can you help me with optimized solution.

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

      ok I got it, It is some what like nested loops in Sieve for finding primes. Thanks for the help.

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

So I'm pretty sure this is cheating, right? Submission

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

    Why say that?

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

      Seems like they're purposely making the code obfuscated.

      You can check in the Official rules that that is prohibited.

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

        Wow, that's not cool at all.I didn't see the code thoroughly.

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

          Yup, also they're in 2nd place!

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

    You are right. The function name 'zao123jia' is the pinyin of Chinese word '造假', which means 'cheat' or 'fake' in English.

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

      LMAO. I mean, if you're gonna fake something, at least don't leave the word FAKE in it xDDDD

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

    This is obvious a rules violation, it is stated explicitly that you cannot obfuscate your code.

    Calling vovuh

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

Is this a hackforces ?

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

I wanna hack someone's code but it told me "Illegal contest ID", and so I could not hack anyone's code.Could someone help me?

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

    Try opening the submission page by clicking the "#" button. Then try to hack from there. It worked for me.

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

I'm a rookie. I took part in the game last night, but why didn't my rating change?

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

Why hasn't the rating changed even after the end of hacking phase ?

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

Hi! I don't see any rating changes for me. Can I understand why? I seem to be fitting all the criteria mentioned above

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

I'm a new user. I want to participate in contest. How I can? anybody help plz

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

    Press the contest bottom and find the conteset which you want to take part in. Then press the red bottom Register to finish your registration.

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

This was my first ever try to competitive coding.Had a nice experience.It was an eyeopener for me.But,Im really motivated to kickstart this journey!! Wish me luck guys!!!

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

Where is the educational round?

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

I mistakenly thought that in problem F the sum of minimum distances over all pairs of points means that I should determine a moment when each point move to a certain coordinate so that the sum of distances is minimum during all times...

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

Good luck everyone!

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

thanks for this round