NALP's blog

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

Hi to all!

A few hours later you're lucky to participate in Codeforces Round #149 for Div.2 participants, but traditionally the others can take part out of the competition. It has been prepared by me (NALP), Igor Kudryashov (Igor_Kudryashov), Pavel Holkin (HolkinPV) and Gerald Agapov (Gerald). Also we express thanks to Mary Belova (Delinur) and Mike Mirzayanov (MikeMirzayanov).

Traditionally I wish good luck, accepted solutions and successful hacking attempts for you!

The standart scoring system will be used: 500-1000-1500-2000-2500

UPD: The contest is over, thanks to all!

UPD: Congratulations to the winners:

  1. Unkown

  2. ballmaids00

  3. mihaipopa12

  4. Yukari

  5. chlxyd

UPD: the tutorial has been published.

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

Comments Comments (88)
| Write comment?
»
13 years ago, hide # |
 
Vote: I like it +11 Vote: I do not like it

good luck

→ Reply
»
13 years ago, hide # |
 
Vote: I like it +4 Vote: I do not like it

If someone wish for making successful hacks , He also wishes for another one to be hacked . So you can say : traditionally I wish someone hack you :|

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

    Why don't you simply take a positive look at successful hacking? It gives people chances to correct their mistakes :)

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

      also a successful hack increases the total score of the contest by 50 (+100 for the hacker and -50 for the one hacked)

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

        it's fail, if you locked the problem, and someone hacked you :|

        → Reply
      • »
        »
        »
        »
        13 years ago, hide # ^ |
         
        Vote: I like it -7 Vote: I do not like it

        And if someone who was hacked won't send the right solution, it will be +100.

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

        hacked participant loses all his points for the problem. So hack always decreases total score of the contest :D

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

          That's not always correct. If the participant is not hacked, he will fail system test --> his score = 0. If he is hacked, he has another chance to submit and be correct --> his score can be > 0

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

            Yes, you're right. The world "always" not compatible in our situation. Maybe "sometimes"?

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

        Hacked solution is wrong solution. So hacked person's score does not decrease ("hackable" solution should fail the system test) And if his solution had been hacked, if he/she had not lock the problem, he might recognize his solution will fail, so he might increase his score.

        → Reply
»
13 years ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

I believe what was meant was the Maximalist's points (maximum reachable score) and not sum of scores of individuals.

→ Reply
»
13 years ago, hide # |
 
Vote: I like it +9 Vote: I do not like it

In queue..

→ Reply
»
13 years ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

In problem C, the ri more than defining a row, it defines a column I think, please correct me if I am wrong.

→ Reply
»
13 years ago, hide # |
 
Vote: I like it +9 Vote: I do not like it

Seems like problems C, D & E (div.2) are much harder than other contests unlike A & B which are easier than other contests

→ Reply
»
13 years ago, hide # |
← Rev. 3  
Vote: I like it +11 Vote: I do not like it

Funny, the pretests for E are so weak, that I've wrote an TLE code intentionally, so I could hack some people on E :)

→ Reply
»
13 years ago, hide # |
 
Vote: I like it +14 Vote: I do not like it

I have always wondered, what happens on server side during the "Pending system testing" phase? Does anyone know the answer?

→ Reply
»
13 years ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

Maybe out of topic, but how can we undergo a BFS with time complexity O(n) in a tree?

→ Reply
»
13 years ago, hide # |
 
Vote: I like it +3 Vote: I do not like it

At the first sight I thought that D is Union-find Data Structure E is Segment Tree and jumped into coding. Soon I realized that I was coding the wrong solution.

Lesson learnt: Never code without proving correctness and reading the entire statement.

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

Each time we have 2 division contest simultaneously, we have less than 500 coders in 1 div. Now, we have a lot of new coders in first place each time we have only second division. Are they the same with a new user?

top 20 ---> 13 new users. Good Luck in 1 div!!!

→ Reply
»
13 years ago, hide # |
← Rev. 2  
Vote: I like it +33 Vote: I do not like it

Well, the part "It is guaranteed that the total length of all given segments doesn't exceed 10^5." in the problem C is SO TRICKY :D

→ Reply
»
13 years ago, hide # |
 
Vote: I like it +5 Vote: I do not like it

How solve problem E ?

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

BFS gets AC in problem C?

I got it!!! If you have a doubt with your algo but you don't have anything else, try your doubt. BFS is the first technique I learnt.

→ Reply
»
13 years ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

I have some problems with the C: I pass with sucess the samples given on the statement on local, but on ideone.com or when I submit here, I have runtime error for the same input. Can someone help me, please? http://mirror.codeforces.com/contest/242/submission/2537756

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

    When you define the structure i think you should define the members before initializing them.

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

      That is not true. The order inside structure does not matter. Constructor is always called after intialization of instance variable. There is something else wrong with it. (running fine on my local)

      → Reply
»
13 years ago, hide # |
 
Vote: I like it -9 Vote: I do not like it

My task B failed because i read 10^6 instead of 10^9 limit :@

→ Reply
»
13 years ago, hide # |
 
Vote: I like it -9 Vote: I do not like it

I used a stack for bfs, instead of a queue. It's a good lesson to learn : search for trivial mistakes line by line without any assumptions.

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

My submission at contest! 2539880

{ some code }
#define U 4             // I set it to 4 only for test my code
{ some code }

My submission after Contest! 2540107

{some code}
#define U 20            // input values can have up to 20 bits!
{some code}

I didn't solve it because of a 2 characters sooti [= bug] in my code. what can I name it?

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

My submission for E (i.e. 2537727) produces all zero in CF but it works fine on my machine (g++ on ubuntu with same parameters as CF) and also on ideone (here) can anyone tell me why this happens?

→ Reply
»
13 years ago, hide # |
 
Vote: I like it +5 Vote: I do not like it

Common Rank it.

→ Reply
»
13 years ago, hide # |
 
Vote: I like it +7 Vote: I do not like it

Is it going to be rated?!! about 3 hours after the contest, it hasn't been rated yet!!

→ Reply
»
13 years ago, hide # |
 
Vote: I like it -9 Vote: I do not like it

Rating update is slow :(

→ Reply
»
13 years ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

Is this contest will rated? I'm waiting... for 3:30 hours...

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

    Well, I'm aware that CodeForces team work hard to maintain the system and sometimes something wrong happens and we can't handle all of them instantly. But I think it would be better for us if we get an update explaining the reason (or not) and/or just a short note, "Due to some unavoidable circumstances, rating will be updated after X hours." It will save a lot of F5 pressing and a lot of contestants won't need to sleep on the keyboard (Later one is not assured, as a lot of programmers like to sleep on the keyboard/desk first and then roll to the bed :P)

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

      And in blog there was not written "Contest will be rated!" or something like this

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

    It is not gonna be rated for you, for sure :)

    → Reply
»
13 years ago, hide # |
 
Vote: I like it +11 Vote: I do not like it

When will the editorial be published? It would be very helpful.

→ Reply
»
13 years ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

Can someone explain why BIT doesn't pass on task E?

→ Reply
»
13 years ago, hide # |
 
Vote: I like it +4 Vote: I do not like it

Any idea how to solve problem D. Dispute ?

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

    There is always an answer, I'm not sure how to prove this. The solution is BFS. Put all vertex that have value == a to the queue. Then on each step we take vertex, increase it's value and values of it's neighbours and add to queue neighbours which values == a. Just look at my code.

    → Reply
    • »
      »
      »
      13 years ago, hide # ^ |
      ← Rev. 3  
      Vote: I like it +8 Vote: I do not like it

      Since one move fixes the problem for one vertex forever, and we can perform up to n moves, this algorithm fixes all the problems and always produces a correct result.

      → Reply
»
13 years ago, hide # |
 
Vote: I like it +14 Vote: I do not like it

waiting for the editorials.... :D :D

→ Reply
»
13 years ago, hide # |
 
Vote: I like it +6 Vote: I do not like it

please post editorial.

→ Reply
»
13 years ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

why I got a wrong answer on this submission?2555192

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

    I'm not sure, but I think, that when you increment the value of the neighbours you forgot that their values can become a.

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

    It fails because you could go through a vertex and nd[i].a == b[ad] might be false at the moment but then b is updated by a neighbour and now it could become true. You need to do the increases when it becomes true.

    → Reply
»
13 years ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

Have any English editorial?

→ Reply