Блог пользователя NALP

Автор NALP, 12 лет назад, По-русски

Всем привет!

Через несколько часов начнется Codeforces Round #149 для участников Div.2, но традиционно остальные могут поучаствовать вне конкурса. Он был подготовлен небольшой командой авторов: я (NALP), Игорь Кудряшов (Igor_Kudryashov), Павел Холкин (HolkinPV) и Геральд Агапов (Gerald). Кроме того мы выражаем благодарность Марии Беловой (Delinur) и Михаилу Мирзаянову (MikeMirzayanov).

Традиционно всем удачи, полных решений и удачных взломов!

В раунде будет использована стандартная разбалловка: 500-1000-1500-2000-2500

UPD: Соревнование закончилось, всем спасибо!

UPD: Поздравляем победителей:

  1. Fio

  2. ballmaids00

  3. mihaipopa12

  4. Yukari

  5. chlxyd

UPD: опубликован разбор задач на русском языке

  • Проголосовать: нравится
  • +93
  • Проголосовать: не нравится

»
12 лет назад, # |
  Проголосовать: нравится +2 Проголосовать: не нравится

Что-то долго анонса не было)

»
12 лет назад, # |
  Проголосовать: нравится +7 Проголосовать: не нравится

"Через несколько часов..." Один час — не несколько!

»
12 лет назад, # |
  Проголосовать: нравится +11 Проголосовать: не нравится

good luck

»
12 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

УРА! анонс появился

»
12 лет назад, # |
  Проголосовать: нравится +4 Проголосовать: не нравится

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 :|

  • »
    »
    12 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится +35 Проголосовать: не нравится

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

    • »
      »
      »
      12 лет назад, # ^ |
        Проголосовать: нравится +3 Проголосовать: не нравится

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

      • »
        »
        »
        »
        12 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

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

      • »
        »
        »
        »
        12 лет назад, # ^ |
          Проголосовать: нравится -7 Проголосовать: не нравится

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

      • »
        »
        »
        »
        12 лет назад, # ^ |
          Проголосовать: нравится -13 Проголосовать: не нравится

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

        • »
          »
          »
          »
          »
          12 лет назад, # ^ |
          Rev. 2   Проголосовать: нравится +1 Проголосовать: не нравится

          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

          • »
            »
            »
            »
            »
            »
            12 лет назад, # ^ |
              Проголосовать: нравится -6 Проголосовать: не нравится

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

      • »
        »
        »
        »
        12 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        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.

»
12 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

  • »
    »
    12 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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.

»
12 лет назад, # |
  Проголосовать: нравится +9 Проголосовать: не нравится

In queue..

»
12 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

  • »
    »
    12 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

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

    • »
      »
      »
      12 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

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

  • »
    »
    12 лет назад, # ^ |
      Проголосовать: нравится +1 Проголосовать: не нравится

    Ask the admin please :)

»
12 лет назад, # |
  Проголосовать: нравится +9 Проголосовать: не нравится

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

»
12 лет назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

Есть ли какие-нибудь особенности у дерева отрезков в E?

  • »
    »
    12 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    n ^ 2 * log (n) случайно проходит претесты, ждите TLE.

    • »
      »
      »
      12 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      Можно было кормить людей в своих румах.

  • »
    »
    12 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится +3 Проголосовать: не нравится

    Придумал решение но не успел написать. Заметим, что все числа мы можем разложить по степеням двойки с показателем не превышающим 20(2^20 > 1e6). Тогда будем хранить в корнях дерева отрезков степени двойки, дающие нужную сумму на отрезке. Таким образом запрос модификации сведется к покраске вершины дерева отрезков в нужный цвет i, где i это разложение X по степеням двойки. Если текущая вершина покрашена и поступил вновь модифицирующий ее запрос, то номер покраски будет номером разложения X1 xor X2(следует из ассоциативности операции xor — (a xor x1) xor 2 = a xor (x1 xor x2) ) по степеням двойки.

    • »
      »
      »
      12 лет назад, # ^ |
      Rev. 2   Проголосовать: нравится +4 Проголосовать: не нравится

      да, именно так, только вроде еще надо хранить количество бит каждого типа, чтобы корректно сумму поддерживать

    • »
      »
      »
      12 лет назад, # ^ |
        Проголосовать: нравится +3 Проголосовать: не нравится

      Там просто можно хранить в каждой вершине дерева кол-во каждого бита. Потом если эту вершину надо проксорить с Х, то если у Х на каком-то месте стоит единичка, то кол-во этого бита станет равное общему количеству элементов на этом отрезке минус то количество таких битов, что было раньше.

      Объяснение не очень, в общем вот код.

»
12 лет назад, # |
Rev. 3   Проголосовать: нравится +11 Проголосовать: не нравится

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

»
12 лет назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

codeforces быстрый, аж жуть: 5*10^9 ксоров заходят за 3сек

»
12 лет назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

Жаль не хватило минуты засабмитить С. Вообщем, как всегда:)

»
12 лет назад, # |
  Проголосовать: нравится +14 Проголосовать: не нравится

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

»
12 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
12 лет назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

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.

»
12 лет назад, # |
Rev. 4   Проголосовать: нравится -6 Проголосовать: не нравится

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!!!

»
12 лет назад, # |
Rev. 2   Проголосовать: нравится +33 Проголосовать: не нравится

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

  • »
    »
    12 лет назад, # ^ |
      Проголосовать: нравится -10 Проголосовать: не нравится

    Me too!

  • »
    »
    12 лет назад, # ^ |
      Проголосовать: нравится +1 Проголосовать: не нравится

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

  • »
    »
    12 лет назад, # ^ |
      Проголосовать: нравится +5 Проголосовать: не нравится

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

  • »
    »
    12 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Could you tell me why?

    • »
      »
      »
      12 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

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

      • »
        »
        »
        »
        12 лет назад, # ^ |
        Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

        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)

        • »
          »
          »
          »
          »
          12 лет назад, # ^ |
          Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

          "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

»
12 лет назад, # |
  Проголосовать: нравится +5 Проголосовать: не нравится

How solve problem E ?

»
12 лет назад, # |
  Проголосовать: нравится +4 Проголосовать: не нравится

А как С решается?Напишите пожалуйста

  • »
    »
    12 лет назад, # ^ |
      Проголосовать: нравится +1 Проголосовать: не нравится

    если у нас есть клетка (X,Y) запишем ее как (S=X*10^10+Y) тогда из клетки (X,Y) можно переходит в клетки:

    1)S+10^10; =(X+1,Y);

    2)S+10^10+1;=(X+1,Y+1);

    3)S+10^10-1;=(X+1,Y-1);

    4)S+1; =(X,Y+1);

    5)S-1; =(X,Y-1);

    6)S-10^10; =(X-1,Y);

    7)S-10^10+1;=(X-1,Y+1);

    8)S-10^10-1;=(X-1,Y-1);

    все "хоршие" клетки запишем в MAP затем пустим БФС из клетки S0=X0*10^10+Y0 и посчитаем минимальное количество ходов чтобы прийти в клетку S1=X1*10^10+Y1;

    вот мой код : 2538101

    • »
      »
      »
      12 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      а зачем так сложно? заполняем Map<Pair, Integer>, в котором будем хранить расстояния от стартовой клетки до каждой. далее БФС от стартовой и ответ готов.

»
12 лет назад, # |
Rev. 4   Проголосовать: нравится 0 Проголосовать: не нравится

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.

»
12 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

  • »
    »
    12 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

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

    • »
      »
      »
      12 лет назад, # ^ |
      Rev. 2   Проголосовать: нравится +1 Проголосовать: не нравится

      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)

»
12 лет назад, # |
  Проголосовать: нравится -9 Проголосовать: не нравится

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

  • »
    »
    12 лет назад, # ^ |
      Проголосовать: нравится -8 Проголосовать: не нравится

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

    • »
      »
      »
      12 лет назад, # ^ |
        Проголосовать: нравится +1 Проголосовать: не нравится

      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 ;
      
»
12 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Блин в С самое главное надо было обратить внимание на "Гарантируется, что суммарная длина всех разрешенных отрезков не превосходит 10^5", для того чтобы спокойно применить bfs по клеткам.

  • »
    »
    12 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Я, когда читал задачи, пропустил этот момент. Без этого условия задача похожа на усложненную версию этой задачи...

»
12 лет назад, # |
  Проголосовать: нравится -9 Проголосовать: не нравится

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.

»
12 лет назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

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?

»
12 лет назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

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?

»
12 лет назад, # |
  Проголосовать: нравится +6 Проголосовать: не нравится

Никто не сказал, но задача D, по-моему, отличная задача!

»
12 лет назад, # |
  Проголосовать: нравится +5 Проголосовать: не нравится

Common Rank it.

»
12 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

как решать Е ?

»
12 лет назад, # |
  Проголосовать: нравится +7 Проголосовать: не нравится

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

»
12 лет назад, # |
  Проголосовать: нравится -9 Проголосовать: не нравится

Rating update is slow :(

»
12 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

  • »
    »
    12 лет назад, # ^ |
      Проголосовать: нравится +9 Проголосовать: не нравится

    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)

    • »
      »
      »
      12 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

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

  • »
    »
    12 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится +2 Проголосовать: не нравится

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

»
12 лет назад, # |
  Проголосовать: нравится +11 Проголосовать: не нравится

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

»
12 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

  • »
    »
    12 лет назад, # ^ |
      Проголосовать: нравится +5 Проголосовать: не нравится

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

»
12 лет назад, # |
  Проголосовать: нравится +4 Проголосовать: не нравится

Any idea how to solve problem D. Dispute ?

  • »
    »
    12 лет назад, # ^ |
      Проголосовать: нравится +6 Проголосовать: не нравится

    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.

    • »
      »
      »
      12 лет назад, # ^ |
      Rev. 3   Проголосовать: нравится +8 Проголосовать: не нравится

      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.

»
12 лет назад, # |
  Проголосовать: нравится +14 Проголосовать: не нравится

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

»
12 лет назад, # |
  Проголосовать: нравится +6 Проголосовать: не нравится

please post editorial.

»
12 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

why I got a wrong answer on this submission?2555192

  • »
    »
    12 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

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

  • »
    »
    12 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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.

»
12 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Have any English editorial?