NALP's blog

Codeforces Round #149 (Div. 2)
By NALP, 12 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. Fio

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

good luck

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

    Traditionally, the above comment is destined to be negatively rated.

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

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

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

    it's just a small joke to entertain before the contest. the example of being optimistic. besides, it is possible to happen, so who knows.

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

In queue..

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

    Wrong output for 2snd sample. Problem D We have 1 in each vertex after increasing. But we should have 0!

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

      Actually it was asking to not have zeros in any of the counter. (in 2nd example) I too initially missed the not part. :)

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

    Ask the admin please :)

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

    Pretests seldom check for TLE.

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

    seems that any attempts of brute-forcing the xor function work for the pretests...

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

    They add "hacks" to test cases before final judgement.

    → Reply
»
12 years ago, # |
  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
»
12 years ago, # |
  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
»
12 years ago, # |
← 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
»
12 years ago, # |
← 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
  • »
    »
    12 years ago, # ^ |
      Vote: I like it -10 Vote: I do not like it

    Me too!

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

    I got very amused when I realized that TRICK. :D

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

    My god, I thought they were repeating the same sentence below, that the "total number of segments" was <= 10^5 =.=

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

    Could you tell me why?

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

      Because if we use BFS, there will be at most 10^5 states. Which passes tests with good time.

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

        I am not sure about we have at most 10^5 states. What will happen with this case? BFS works? Overflow in the queue?

        1 1 100000 100000
        100000
        1 1 100000
        2 1 100000
        .................. (ith row -> 1 100000)
        100000 1 100000

        King's Path = 100000 (Main Diagonal)

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

          "It is guaranteed that the total length of all given segments doesn't exceed 10^5."

          total length != number of

          total length of all != length of each

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

How solve problem E ?

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

    You make a segment tree for each bit.

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

      a segment tree for each bit? i don`t get it

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

        For each bit, you will build a segment tree which contains the sum for the intervals. This way you can update an interval in O(logN).

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

    just wait,may be will not accepted with strong tests :)

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

    I think bfs is perfect to solve it. there are at most 100000 points you may reach

    → Reply
»
12 years ago, # |
  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://codeforces.me/contest/242/submission/2537756

→ Reply
  • »
    »
    12 years ago, # ^ |
      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
    • »
      »
      »
      12 years ago, # ^ |
      ← 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
»
12 years ago, # |
  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
  • »
    »
    12 years ago, # ^ |
      Vote: I like it -8 Vote: I do not like it

    Mee too! :( , i initialized with 10^7 for max calculation, it should have been 10^9. :(

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

      If you use C/C++ I recommend you this :

      # include <climits>
// for INT_MAX , INT_MIN , LLONG_MAX , LLONG_MIN and so on...
//...
int int_mn = INT_MIN ;
long long ll_mx = LLONG_MAX ;
      → Reply
»
12 years ago, # |
  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
»
12 years ago, # |
← 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
»
12 years ago, # |
← 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
»
12 years ago, # |
  Vote: I like it +5 Vote: I do not like it

Common Rank it.

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

Rating update is slow :(

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

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

→ Reply
  • »
    »
    12 years ago, # ^ |
      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
    • »
      »
      »
      12 years ago, # ^ |
        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
  • »
    »
    12 years ago, # ^ |
    ← Rev. 2   Vote: I like it +2 Vote: I do not like it

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

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

      Yeah I know. But I wonder about my friends. Are they will pass me or not. I'm wondering that... :D

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

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

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

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

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

    You can't make update segment, get sum on segment at same time using only BIT. It can be done with Segment Tree

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

Any idea how to solve problem D. Dispute ?

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

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

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

please post editorial.

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

why I got a wrong answer on this submission?2555192

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

      Thank you ! But according to greedy algorithm, it doesn't matter.

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

      Now I know what you said is right....

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

Have any English editorial?

→ Reply