NALP's blog

Codeforces Round #101 (Div. 2)
By NALP, 13 years ago, translation, In English

Dear friends!

The next competition - Codeforces Round 101 for participants Div2 will take place through a pair of hours, but the others can traditionally participate out of competition. It has been prepared by a small command of authors: me (NALP), Polina Bondarenko (Polichka) and Gerald Agapov (Gerald). There were Artem Rahov (RAD), Maria Belova (Delinur) and Michael Mirzayanov (MikeMirzayanov) with us as always.

It is a little bit about authors: all of us study at the Saratov State University at faculty of Computer Sciences and Information technology on 4th course. Now in free time from competitions and problems we pass the exams :) I’m a 1/3 part from command Saratov SU#2, and Gerald with Polina - 2/3 from Saratov SU#1. We would like our rounds became kind tradition on Codeforces and you have seen us among authors soon again.

We hope that this problems will be pleasant to all participants and everyone will take the deserved high place in the total table. Today you will help Santa Claus, Elf, Vasya and the other characters. All the similarities to real people are casual :)

The points on problems are distributed today in this way: 500-1000-2000-2000-2500

UPD: You can read the tutorial here.

UPD: Thanks all for participation! The round has turn out difficult enough and only one person among all participants (including Div. 1) has solved all offered problems - akim239. Our congratulations for him!!

UPD: our congratulations for Top-10 participants in competition:
3. frp
6. hex539
7. not
10. ggbuaa
  • Vote: I like it
  • +147
  • Vote: I do not like it

Comments Comments (41)
| Write comment?
»
13 years ago, # |
  Vote: I like it 0 Vote: I do not like it
Good luck and have fun!)
→ Reply
»
13 years ago, # |
  Vote: I like it +6 Vote: I do not like it
Three witches watch three Swatch watches. Which witch watch which Swatch watch!
→ Reply
»
13 years ago, # |
  Vote: I like it +3 Vote: I do not like it
How to solve problem C?
→ Reply
  • »
    »
    13 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    I used greedy algorighm, but I don't know if it is correct ot not. (Passed pretests).

    Sort people by ai. // fail() means that there is no solution
    We will have array res, where we will keep name of person, his height.
    Then check: if (a1 > 0) fail();
    h1 = 500000;
    for i = 2..n {
    if (ai ≥ i) fail(); 
    if (ai =  = ai - 1) {
    put this person after previous (remember that it may be not last place!), hi = hi - 1
    } else {
    put this person at the (ai + 1)th place, hi = 500000 - ai
    }
    }
    → Reply
    • »
      »
      »
      13 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it
      I have the same idea but can't prove it in the contest, now it seems correct.

      But there is an issue, will 500000 be too small? I guess 5000000 would be safe.
      → Reply
      • »
        »
        »
        »
        13 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it
        We have only 3000 names, so minimal value is 500000 - 3000 = 497000.
        If I am not mistaken, 5000 will be enough.
        → Reply
»
13 years ago, # |
  Vote: I like it +10 Vote: I do not like it
Please make the statements more clear.. It take a lot of time to understand what is asked in the problem...
→ Reply
  • »
    »
    13 years ago, # ^ |
      Vote: I like it +8 Vote: I do not like it
    yes...statements were a bit confusing...i found difficulty specially in D.
    → Reply
»
13 years ago, # |
  Vote: I like it +10 Vote: I do not like it
It's a very good contest with very good questions.
Thank you
→ Reply
»
13 years ago, # |
  Vote: I like it +3 Vote: I do not like it
what hit me?
→ Reply
»
13 years ago, # |
  Vote: I like it +3 Vote: I do not like it
An interesting discovery: B is such a kind of problem, even you know lots of submissions probably would be failed in the system test, it's hard to come up with a vital test case in a short time.  That's very frustrating. 
→ Reply
  • »
    »
    13 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    Yeah. Many people failed the system test.
    And if you want to hack them, you need to understand their codes totally.
    → Reply
»
13 years ago, # |
  Vote: I like it +2 Vote: I do not like it
Thanks for the quick editorials :D
→ Reply
»
13 years ago, # |
  Vote: I like it +10 Vote: I do not like it
Great contest! Thanks Codeforces! A veryyyy small problem caused me 2 WA! The size of an array!! By the way problems were great! Specially E. I love graph problems!
→ Reply
»
13 years ago, # |
  Vote: I like it +3 Vote: I do not like it
For Problem E ... I separated all the santa edges and elf edges and then used disjoint set to make the tree.i chose one edge from santas side and one edge from the elfs side and kept on iterating and toggling.. if the edges count of santa and elf is same and the total is n-1. Then there is a possible solution.  but I got WA on case 30.. 


Can anyone tell me why my code fails?
→ Reply
»
13 years ago, # |
  Vote: I like it 0 Vote: I do not like it
can someone explain solution for problem C ? i couldn't understand the solution from tutorial... failure condition is straightforward, but how to adjust the heights ?
→ Reply
  • »
    »
    13 years ago, # ^ |
    ← Rev. 3   Vote: I like it 0 Vote: I do not like it

    After sorting:
    First, let h1 = n (or what number you like as long as it is not less than n).
    At step i, assign n - ai to hi and decrease hj by 1 if hj ≤ hi (obviously, these changes do not affect previous order). Therefore, after step i, we can maintain a list of numbers from n - i + 1 to n.

    → Reply
    • »
      »
      »
      13 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it
      hi,
      can you tell why your solution works ? idea behind it.
      → Reply
      • »
        »
        »
        »
        13 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it
        We process from the head of the queue to the tail.
        Now, instead of choosing values, let's think about choosing ranks for these elements (from 1 to n, 1 is the biggest). Then, we can easily choose value for an element if we know its rank.

        First, there's only 1 element, of course its rank is 1.
        With element i, we know it must be smaller than ai elements, so its rank is ai+1. Inserting this element into the list we created so far will increase the ranks of elements whose current ranks are greater than ai.
        For ex: let the a[] after sorting is {0,1,1,2,2,3}
        Array rank[] after each step (bold numbers are whose ranks are increased after each step)

        Step 0: 1
        Step 1: 1,2
        Step 2: 1,3,2
        Step 3: 1,4,2,3
        Step 4: 1,5,2,4,3
        Step 5: 1,6,2,5,3,4
        → Reply
»
13 years ago, # |
  Vote: I like it +11 Vote: I do not like it
I resubmitted my C and Passed!
count differences between these two codes!
http://www.codeforces.com/contest/141/submission/1024571
http://www.codeforces.com/contest/141/submission/1022993

can u rejudge it please ?!
→ Reply
  • »
    »
    13 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    http://www.codeforces.com/contest/141/submission/1024639  
    → Reply
  • »
    »
    13 years ago, # ^ |
      Vote: I like it -10 Vote: I do not like it
    devils13. I've submitted your TLE code, and it actually passes.
    Codeforces was so slow today and I think your code deserves to be rejudged.
    → Reply
    • »
      »
      »
      13 years ago, # ^ |
      ← Rev. 2   Vote: I like it +13 Vote: I do not like it

      I think the reason is judging a lot of submissions at the same time in system testing might cause a little difference in execution time (1920ms is pretty close to time limit).

      → Reply
      • »
        »
        »
        »
        13 years ago, # ^ |
        ← Rev. 2   Vote: I like it 0 Vote: I do not like it

        the order of my code is n^2logn which is should pass when n = 3,000. u r right it is very close to 2 secs, but my code passes in less than 2 secs.

        → Reply
  • »
    »
    13 years ago, # ^ |
      Vote: I like it +15 Vote: I do not like it

    Process time is not a constant on any operation system, but it could vary a little. Typically 3-10% is acceptable accuracy. In particular on this all author solutions are 2-3 times faster than a time limit. Actually each contest we have some solutions which work around a time limit. Some of them pass system tests, some of them not. But anyway, writing such solution is a risk, because you can't get will it pass tests or not.

    We do not rejudge such solutions, it would be unfair to other participants. We apologize for the inconvenience.

    → Reply
    • »
      »
      »
      13 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it
      ok thanks so much!, but I hope to c codeforces avoid such problems in the future :)
      → Reply
      • »
        »
        »
        »
        13 years ago, # ^ |
          Vote: I like it +6 Vote: I do not like it
        Codeforces has not problem. It is NOT a problem. All solutions tested in real operating system, on real CPU. The world is not ideal. And if you try to run the same solution on the same data 100 times, the running time will be different - "Typically 3-10% is acceptable accuracy"
        → Reply
        • »
          »
          »
          »
          »
          13 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it
          no it is a problem, if the servers strong enough it will pass cause my code in the worst case makes 31,294,092 operations. topcoder servers finish them in less than 1 sec. my laptop finish them in less than 1 secs!
          → Reply
          • »
            »
            »
            »
            »
            »
            13 years ago, # ^ |
            ← Rev. 2   Vote: I like it +3 Vote: I do not like it

            can you please tell us how you get such number of operations? what if we replace set with sort? the number of operations will be the same? I think you just have not strong enough test data. Codeforces servers are very fast as i know. 

            upd: with sort your program works only 340 ms, but it is still O(n^2 * log(n)). The constant factor is very important. BTW dont't you forget about N^2/2 calls of "operator new" when you use set? There is more optimal - O(n^2) solution, so there is no any problem.

            → Reply
            • »
              »
              »
              »
              »
              »
              »
              13 years ago, # ^ |
              ← Rev. 2   Vote: I like it -6 Vote: I do not like it

              as I know that the set implementation in the c++ is a red-black tree, which takes log(n) in the insertion. so my code is O(N^2Log(N)) and N = 30000, So N^2Log(N) = 3000^2Log(3000) = 31,294,091.292476962. 

              I know that it is an approximate number and not a 100% accurate. 
              → Reply
              • »
                »
                »
                »
                »
                »
                »
                »
                13 years ago, # ^ |
                  Vote: I like it +1 Vote: I do not like it
                see at your modified solution. both variants works O(n^2 * log(n)) but second is 6 times faster.
                → Reply
              • »
                »
                »
                »
                »
                »
                »
                »
                13 years ago, # ^ |
                  Vote: I like it +3 Vote: I do not like it
                don't you know what O(log(n)) means? it can be 2 * log(n) can be 100000000000 * log(n). set insertion is very slow: 1 call of "operator new"(you can google how it's slow) and then (for n = 3000) not only 12 arithmetic operations, but recursive calls, complicated tree rotations and so on... can be 100 * 12 operations, i dont know for sure
                → Reply
                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  13 years ago, # ^ |
                    Vote: I like it 0 Vote: I do not like it
                  hmmmm, got it, thx so much :) i'll never use it again :D:D
                  → Reply
                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  13 years ago, # ^ |
                    Vote: I like it 0 Vote: I do not like it
                  sometimes set must be used, but you should understand: it is slower then just sorting.
                  → Reply
                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  13 years ago, # ^ |
                    Vote: I like it 0 Vote: I do not like it
                  yes, um kidding :D
                  → Reply
            • »
              »
              »
              »
              »
              »
              »
              13 years ago, # ^ |
              ← Rev. 2   Vote: I like it 0 Vote: I do not like it

              There's an even more optimal O(N) solution too.

              → Reply
      • »
        »
        »
        »
        13 years ago, # ^ |
          Vote: I like it +24 Vote: I do not like it
        It's better to compete in winter cause CPUs work faster in winter than in summer. :D
        → Reply
  • »
    »
    13 years ago, # ^ |
      Vote: I like it +1 Vote: I do not like it
    Similar issue happened to me once in TopCoder, my Passed System Test solution during the contest is getting TLE in the practice room. :)
    → Reply