vovuh's blog

By vovuh, history, 5 years 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 nooinenoojno Stepanova, Mikhail awoo Piklyaev, Maksim Neon 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

| Write comment?
»
5 years ago, # |
Rev. 2   Vote: I like it -26 Vote: I do not like it

[DELETED]

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

Finally a good freaking round

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

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

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

3 rounds in 2 days is very cool!

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

.

»
5 years ago, # |
Rev. 7   Vote: I like it -8 Vote: I do not like it

.

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

Div3 gives confidence

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

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

        thanks for your suggestion.i'll try my best.

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

          if you need help i will help you :)

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

          Keep practising & forget about the rating changes.

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

            a really good advice for a noon like me. appreciate.

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

Is it rated?

  • »
    »
    5 years 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 years ago, # ^ |
        Vote: I like it +1 Vote: I do not like it

      That's good.

      I'll take off in this contest.

»
5 years 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 years ago, # ^ |
      Vote: I like it +9 Vote: I do not like it

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

  • »
    »
    5 years 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 years 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 years ago, # ^ |
      Vote: I like it +14 Vote: I do not like it

    But I don't have enough money to donate.Actually I am hungry, for I don't have money to eat rice.

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

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

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

Smiley face

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

Schrodinger's Problem Number

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

OMG first time I solve D <3

»
5 years ago, # |
  Vote: I like it +21 Vote: I do not like it
»
5 years 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 years ago, # ^ |
      Vote: I like it +9 Vote: I do not like it

    Fix B.Find A and C greedily.

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

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

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

        You can simply try all possible solutions in time. code

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

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

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

              How does the hack work?

              • »
                »
                »
                »
                »
                »
                »
                »
                5 years 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 years 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 years 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 years ago, # ^ |
                    Vote: I like it +1 Vote: I do not like it

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

                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  5 years ago, # ^ |
                    Vote: I like it +9 Vote: I do not like it
                  113
                  385 770 10010
                  
                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  5 years 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 years 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 years 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 years 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 years ago, # ^ |
                    Vote: I like it 0 Vote: I do not like it

                  How to decide that epsilon value?

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

                  10.5k is enough. not 20k.

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

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

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

          it's just like erastothenes sieve without prime number

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

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

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

          i think this is (n^2)/2

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

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

  • »
    »
    5 years 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 years ago, # |
  Vote: I like it -12 Vote: I do not like it

speedforces

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

I want an editorial ASAP :(

»
5 years 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.net/contest/1311/submission/71794691

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

    I'm also want to know it :(

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

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

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

        His code: (https://codeforces.net/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 years 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 years 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 years 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 years ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

Is this comment (https://codeforces.net/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 years 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 years 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 years ago, # |
  Vote: I like it +2 Vote: I do not like it

i think d will be hacked most...

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

    Seek some damn therapy instead of asking random internet strangers.

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

    Yes there are. it's called editorial

  • »
    »
    5 years 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 years ago, # |
  Vote: I like it +5 Vote: I do not like it

What is the hack of D?

»
5 years 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 years 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 years ago, # |
  Vote: I like it +1 Vote: I do not like it

hey ? No hacking phase?

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

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

»
5 years 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 years 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 years 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 years 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 years ago, # |
  Vote: I like it 0 Vote: I do not like it
»
5 years ago, # |
  Vote: I like it +10 Vote: I do not like it

How to solve E guys ?

  • »
    »
    5 years 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 years 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 years 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 years 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 years ago, # |
  Vote: I like it +12 Vote: I do not like it

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

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

    It works from the submission page. It can be opened by clicking on '#' in solution preview

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

    Me , What does it mean ??

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

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

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

    how to prove it ?

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

      I dont good at proving complexity, I dont mean anything, sorry

»
5 years 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.net/contest/1311/submission/71798202). Is it what the contest want?

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

Why is 71783447 accepted, not hacked?

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

    Probably because they changed the accepted condition

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

    Wow, this is new to me too

»
5 years 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 years ago, # |
  Vote: I like it +3 Vote: I do not like it

Codeforces Hack Round #624 (Div. 3)

»
5 years 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 years 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 years 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 years 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 years 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 years 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 years 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 years 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 years ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    cyan revolution is only a matter of time..

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

SPEEDFORCES!!!

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

what is approach for E and F?

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

    Can u explain D

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

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

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

Help me with how you approach Problem D

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

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

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

    Why say that?

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

Is this a hackforces ?

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

Where is the educational round?

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

Good luck everyone!