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

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

Привет, Codeforces!

30 марта 2016 года в 19:05 MSK (время московское) состоится очередной раунд Codeforces #346 для участников из второго дивизиона. Традиционно, участники из первого дивизиона приглашаются поучаствовать в соревновании вне конкурса. Этот раунд будет необычным: будет предложено 7 задач и 2,5 часа на их решение. Надеюсь, что все найдут для себя интересные задачи. Обратите внимание на необычное время начала раунда!

Задачи для вас готовили я (IlyaLos), Эдвард Давтян (Edvard), Данил Сагунов (danilka.pro), Роман Глазов (Roms) и Владимир Петров (vovuh). Хотелось бы сказать большое спасибо Глебу Евстропову (GlebsHP) за помощь в подготовке задач, Марии Беловой (Delinur) за перевод условий на английский и Михаилу Мирзаянову (MikeMirzayanov) за замечательные системы Codeforces и Polygon, а так же за помощь в подготовке контеста и идеи нескольких задач.

Разбалловка будет объявлена позднее.

UPD Разбалловка: 500-1000-1000-1250-1500-2000-2500

UPD2 Соревнование завершено! Всем спасибо! Разбор

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

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

Необычное время, необычная длительность, необычное количество задач... Может, стоит поправить "...очередной раунд Codeforces..." на "... необычный раунд Codeforces..."?

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

Expecting a good round :)

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

A regular Codeforces round after a long time :).

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

Just learnt coding about two weeks ago and this is my first round. Wish me luck!

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

Жду с нетерпением этот раунд! Спасибо всем тем кто стараются ради нас и проводят такие раунды!

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

Hope to advance to Div1 this time!

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

Just wondering : If there are 7 problems then why not make a Div.1 Round too?

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

    No, because tourist now has a 4000+ of rating. I respect that!

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

    Kinda related, I wonder if it would be difficult to allow for div1 users the option to register to div2-only rounds as ranked competitors. If I'm not mistaken, it's not allowed because div1 users might run out of problems to solve, but if they wanted to register as ranked competitors into div2-only rounds, they'd have to accept that possibility, yet could still get the fun of competing in a ranked round. Many div1 competitors usually can't solve any problems past the first 3 anyway (I know I can't).

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

      It would be nice. We can just have separate rankings, which means some may loose rating even though they solve all problems (but too slow).

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

      Div1 competitors will quickly solve problems and will begin constantly hack others. Poor chance for div2 competitors to hack somebody (and learn how to hack).

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

    Probably because the F and G problems in this round would be way too easy as Div1 D and E.

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

    Is someone going to answer his question!?

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

Let's hope this be a nice round for everyone :D

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

Good luck everyone

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

Good luck everyone

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

It's been a long time since a totally normal rated Codeforces Round. :(

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

Интересно будет увидеть разбалловку для 7-ми задач

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

    Здравствуйте. На Codeforces я всего 10-11 дней,по-этому не знаком с понятием разбалловка — объясните пожалуйста.

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

      Разбалловка это информация в которой указано сколько баллов будет предложено учаснику за решение конкретной задачи.

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

When Soni says something, you repeat it!
When Soni does something, you do it!
When Soni has something, you don't have it!
And that's so because Soni is a cool guy!

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

Why 7 problems for div.2???

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

    maybe for easy problems :-"

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

    I guess maybe they found those problems were too easy for div.1. So, 7 problems for div.2. lol Okay,frankly, maybe just for fun.

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

I wonder if there's something that could tell me my expected ranking to get a +rating. Even 5 minutes before the contest would be great. Don't know if that's even possible though.

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

    you expected rank can't be computed before the contest is finished, because it depends on the people who make at least one submission

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

    Try the NBHEXT extension for Chrome. It is not completely accurate because systest, but you get a rough estimate.

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

      I think that it consistently gives lower ratings because it interprets newcomers as having "0" rating instead of "1500" rating.

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

        Yup, and it also occassionally shows a 0 difference for Legendary Grandmasters when it obviously shouldn't be 0. But like I said, rough estimate.

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

Can I request a 10 minute delay? The bus is slow : O

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

Funny. When using CHelper, you can see "April Fools Day Contest 2016" before today's round. Did that one already happen?

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

UPD Разбалловка: 500-1000-1000-1250-1500-2000-2500

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

Is something changed regarding contest registration. Though I registered, it's still asking for registration while submission.

http://i.imgur.com/35uAN1W.jpg

--- [Edit] Now option to register re-appeared, and can submit after re-registration.

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

.

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

Всем здравствуйте. Я пишу с планшета, написал 3-ю задачу, заблокировал, при попытке просмотреть код других участников для взлома, пишет "Content on this page requires a newer version of Adobe Flash Player" и появляется ссылка на флэш плеер, перехожу по ней, там пишут, что эта программа не предназначена для моего устройства. Что мне с этим делать? Заранее спасибо за ответ

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

Why is problem A blocked? I want to resubmit my solution.

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

I am not put in a room for hacking, so I cannot hack. Is this a bug?

EDIT: I also registered late, so I don't know if this is the problem?

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

Какая-то магия происходит. Пытался взломать двух человек. Переписал их код себе. У меня выдаёт неправильный ответ. Взламываю и получаю Неудачная попытка взлома ...

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

I don't want to see all human defeated by AlphaGo, but this will happen if AlphaGo passes all system tests

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

    His submissions look suspicious though. He got B and C accepted in the same minute, and it only took him 8 minutes to solve G.

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

    By the way, I think that the problem statements are pretty formal and the next challenge for the DeepMind team could be trying to compete in the programming contests.

    Correct me, please, if I am wrong and there is something about artificial neural networks that doesn't allow them to compete here.

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

      Are you joking? Sometimes I can't figure out what the hell the authors want from me by myself, and you want to make computer understand that?

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

        Well, aren't computers better at solving CAPTCHAs than humans already? But I agree that it seems very unlikely to happen

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

        You know that can't be an argument :)
        Sometimes we cannot recognize faces on the pictures, but Google can (despite the millions of years of evolution that crystallized our ability to recognize human faces).

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

    I wanna see AlphaGo vs tourist face-off assuming AlphaGo is AI and not a team/user.

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

За 10 секунд до конца я не успел отправить решение, так как меня разлогинило.

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

Interesting contest, what was the solution to F?

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

    Loop through all the cells. If k is evenly divisible by the number in the cell, and cellnum*m*n is greater than k, then do a BFS across adjacent cells that are greater than or equal to cellnum. If we have processed k/cellnum nodes, immediately print YES, print a matrix such that any cell examined in this BFS is given number cellnum and all other cells are 0, and then return. If the loop completes without finding anything, print NO.

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

      Won't this time out, if all the cell numbers are divisible by k and none have required adjacent cells greater than its value?

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

        You are correct... for example, the 1000x1000 checkerboard pattern of 3 and 7 with a 1 on the bottom right and k=3000000 times out horribly with the wording I gave. I should add, then, that I kept track of which cells I had visited in BFS's for a given factor, so I wouldn't do duplicate work (i.e., a full BFS every time I ran across the number 3). With this addition, it doesn't time out in practice because the number of distinct factors of k such that you will need to examine a sizable subset of the matrix is exceedingly small.

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

        Mine didn't. I used the same approach. But I used some heuristics to reduce the time (eg. I consider only those values in the arr[][] such that k/arr[i][j] <= n*m). Please refer to 17055152.

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

      If you want O(nlogn), you can use DSU on components to store the number in each component and a priority queue to process cells by descending height so that you dont have to process any large amount of area twice.

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

Please someone explain problem 5. I think it is somewhat related to cycle finding or some trick to be used using dfs/bfs.

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

    Answer can not exceed the number of connected components. So define answer=number of connected components. If there is a cycle in a connected component then decrease answer.

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

    Consider each connected component separately.

    If the connected component is a tree, the answer is 1. This is because there are only V - 1 edges — not enough edges for all vertices. It is not more, we can root the tree and direct all edges from parent to child. Only the root will have no incoming edges.

    If the connected component has cycles, the answer is 0. To see this, take an arbitrary cycle and direct the edges in it the obvious way. Now you can throw out some edges (and direct them randomly) to get a tree for every vertex in the cycle. Direct all those trees from parent to child and you'll see that all vertices have incoming edges.

    So, for each connected component, check if it is a tree, and if it is, add one to the answer.

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

    Alternate (greedy) solution:

    • count undirected edges as "inward" edges
    • use a min-heap to store number of incoming edges to each node
    • assign "inward" edges by popping off min heap

    at the end, the answer is the number of nodes without any "inward" edges (http://codeforces.com/contest/659/submission/17054791)

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

    Consider a connected component If it has a cycle it is possible to assign directions to edges such that no vertex has zero incoming edges
    If it has no cycles there will be exactly one such vertex
    So just count connected components which do not have cycles

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

    if you don't want to find cycles, then just count the number of edges in each connected component, you can do it by summing up the degrees of all nodes in that component then divide it by 2. if the number of edges is equal to number of nodes minus 1 then it's tree and there's no cycle, otherwise there's a cycle

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

Hacking test of B?

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

    5 2 Ivanov 1 763

    Andreev 2 800

    Petrov 1 800

    Sidorov 1 800

    Semenov 2 503

  • »
    »
    8 лет назад, # ^ |
    Rev. 3   Проголосовать: нравится +8 Проголосовать: не нравится
    3 1
    a 1 1
    b 1 1
    c 1 0
    ans a b
    
    3 1
    a 1 1
    b 1 0
    c 1 0
    ans ?
    
    3 1
    a 1 0
    b 1 0
    c 1 0
    ans ?
    
    3 1
    a 1 0
    b 1 0
    ans a b
    
  • »
    »
    8 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    4 2 Ivanov 1 800 Andreev 2 763 Petrov 1 800 Semenov 2 503

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

    some people wrote if (list[i][0] == list[i][2]) printf("?"); else print answer, which is wrong (should be list[i][1] == list[i][2])

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

Задачки прикольные, кажутся сложными, а потом понимаешь, что всё просто

Почему мне не удалось взломать эту посылку? там из priority_queue достаётся 2 элемента, и 2ой сравнивается с верхним в оставшейся очереди, но эта очередь может быть пуста. как сломать это при условии, что очередь пуста?

  • »
    »
    8 лет назад, # ^ |
      Проголосовать: нравится +5 Проголосовать: не нравится
    if (a[i].size() && t == a[i].top().y){
          cout << "?" << endl;
    }
    

    Он проверяет размер очереди

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

Problem B Hack

3 1

dushyant 1 20

sumit 1 16

snigdh 1 16

Answer --> ?

PS — My submission will fail. :(

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

Look to the solutions of problems B and C user AlphaGo , they sent in 10:48 and 10:51, and had so different style code, i think it wrote by different people

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

why geometry why :'(

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

    I kept trying to solve D for two hours. Did you solve it? . I couldn't get my algorithm right for finding whether a line segment will properly cut any segment of the polygon when extended in the direction given.

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

      All of the left turns are dangerous, while right — not. If we know this, we can solve the problem with no geom using some conditions.

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

        It is never stated that she is travelling clockwise. If she goes counter-clockwise, then a right turn is dangerous, and left is not.

        Edit: I retract my statement, I didn't realise that the staring positions was always the bottom left

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

      the answer is the number of left turns (you can get that by cross product)

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

      My approach to D was to keep a counter for the dangerous turns if the water is on the left and if the water is on the right. While iterating through all the points, use the previous point, current point and next point to determine whether she is turning left or right. If you are turning left, the it would be dangerous for the water to be on your right, so increment the right counter. If you are turning right, the it would be dangerous for the water to be on your left, so increment the left counter. Then when you are done iterating through every point, just output whichever counter is smallest.

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

      My solution is simply (N-4)/2. Consider 90 degree and 270 degree angles.

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

    After some minutes of thinking how to solve it in a nice way, I give up and seek for pre-written geometry library that do the job for me (I hope there's no bug inside tho).

    For those who solve it without a generic written code, how do you guys managed to write decently? (e.g. without using lots of if)

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

      Which library did you use?

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

      I used 4 ifs (in fact 8 so that the conditions are more clear), is that a lot?

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

      You can solve it with just basic things like calculate area of polygon & CCW

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

        Turns out area isn't even needed because you start at the bottom left...

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

        As it has been said the answer is (N-4)/2 since when you have more than 4 edges on the polygon all the left turns will have one corresponding right turn. I am amazed how almost none of us didn't figure that out, going instead for a longer solution...

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

          Hahaha almost thought of convex hulls and stuff until I realized "hey could I find a pattern". and I noticed it was something like linear (clearly it must) and then I remembered of 90 and 270 degrees.

          Basically if we have an n-gon composed of 90 degrees and 270 degrees suppose there are a 90 degrees and b 270 degrees. Total angle is 180(n-2). Then 90a+270b=180n-360... a+b=n. Solving we get b=(n-4)/2.

          Yay

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

        You can do it without calculating the area or point-in-polygon queries, by just checking 4 conditions regarding the previous and next directions of movement, for each corner point. Please refer 17044429.

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

      Collect all if's in one place and use enums: 17046342

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

 Who is AlphaGO?

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

6 минут не хватило, чтобы разобраться, где ошибка в G =( Главное формулы правильные вывел, но забыл в коде в одном месте умножение поставить...

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

Please suggest an approach to solve F and G.

Thank you.

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

    F is already explained, as regards G I did dp:

    dp[i][0] — the number of ways where you remove something from position i and the remaining height is not greater than h[i+1]

    dp[i][1] — the number of ways where you remove something from position i and the remaining height is greater than h[i+1]

    Obviously if h[i] <= h[i+1] then dp[i][1] = 0;

    Hope that helps.

    Edit: If not, here is the submission implementing that logic: http://codeforces.com/contest/659/submission/17059428

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

    I think it can be solved in a greedy manner, using DSUs. Start processing the cells in decreasing order of their values. When you process a particular cell, check its neighbouring 4 cells. The cells among those 4 which have their values >= value of current cell, are combined with the current one using DSU. After each combination, check whether that set has the required number of cells (if value of the cell is v, the set should have at least k/v elements). The moment this occurs, you have found the answer. Assign exactly k/v cells of this set to v, and assign all remaining cells in the grid to 0.

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

Hack you back.

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

Would binary search in F pass the time limit?

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

Nice and balanced problem set, perfectly suits for div2 difficulty in my opinion. But, Problem statements were not easy to understand (at least for me).

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

Wasted my whole time on a silly mistake with B, could have easily solved 4 problems :( :( :(

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

Codeforces team: Please check FlappyBird's submissions.
http://codeforces.com/contest/659/room/112
Seems like he wasn't codding alone.

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

Any ideas how to solve C? I did simple greedy algo but it failed on tc #10.

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

    Greedy was okay.. Can you post your code ?

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

    You just made 100100 sized array to mark used toys, but that can be from 1 to 1e9. Your update will fail if used toy is greater than 100100.

    Your code->

    const int N = 100100;
    
    int n, m;
    bool toys[N];
    
    
»
8 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

На последних минутах придумал решение для F.

  1. Сохранить карту склада.
  2. Рассортировать все стоги по высоте, сохранив их первоначальное положение.
  3. Разложить k на простые множители меньше или равной максимальной высоты стога.
  4. Перебором пройтись при помощи простых множителей по всем делителям k до максимальной высоты стога, и если существует стог такой высоты как делитель, то мы проверяем количество вершин в компоненте связности около этого стога, где между соседними клетками есть путь, если обе клетки больше или равны делителю.
  5. Если нашли компоненту с количество вершин большим или равным k / (делитель k) то выводим его, иначе не получится реорганизовать склад.

Как думаете, такое решение зайдет?

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

    Не нужно ничего раскладывать. Все гораздо проще.

    Достаточно лишь отсортировать значения в ячейках по невозрастанию и пройтись по ним поддерживая СНМ.

    Каждый раз, когда добавили чиселку x, проверяем, если k делится на x и размер текущей компоненты не меньше k / x, то выводим ответ (обойдя компоненты дфсом, чтобы получить необходимое количество клеточек).

    Если не получилось найти ответ — выводим NO.

    Собсна, все.

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

What is approach to solve question D ?

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

    (n-4)/2

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

      Are you serious!? Does that actually work?!?

      Edit: Ah, I see now! First there is the 4 turns which MUST be made to get back to the start, so subtract them. Then every variation other than those 4 turns require 2 turns to go straight again (1 safe turn and 1 dangerous turn), hence the division by two.

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

      Can you provide some explanation for this?

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

        very rough idea

        rectangle-> 4sides,0turnings,take a side possible modification gives 2 turns for 4 more extra points

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

      ...and here I thought I was being clever with my vector solution counting the left turns.

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

      Lol and here was I dangling with geometric algorithms and what not :P

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

Мне кажется, или я стал слишком часто попадать в одну комнату с кем-нибудь из своих друзей... За последний месяц раза 3-4 это случилось, причем 2 из них — подряд и с одним и тем же другом.

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

Before that contest finished, I was 1200 and now I have two failed problem and I am 3200. Ohhhhhh noooooo.

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

Anyone else not realize that you couldn't add to piles in problem F? I had the solution but made that dumb mistake ugh.

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

Can someone tell me some hacking tests for 'A'. A guy I know made 11 successful hacking attempts :D

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

    Possible mistake can be giving output a negative number, because of improper modulo operation.

    Mine failed at this->

    10 6 -100

    answer should be 6.

    my code outputs -4.

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

Please enable upsolving !

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

I hate that kind of simple but tricky problems like A!

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

How is this even working?? Problem D. answer is n/2 — 2 ; http://codeforces.com/contest/659/submission/17055800

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

    n/2 — 2 is the exact same as (n-4)/2, to which there are multiple explanations in the above comments. One of them should help you out.

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

The difficulty of C, D, E problems weren't even of Div2 level.. The contest should be renamed to "DIV 3".

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

The difficulty of C, D, E problems weren't even of Div2 level.. The contest should be renamed to "DIV 3". 1000+ people solved C,D,E

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

    I liked problem E!

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

    But A and B were?

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

    Can you please explain how you solved problem E?

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

      If you are given a tree, then the answer will be 1. Let's say you root the tree from a certain vertex, then we can draw directed edges from parent of all vertexes to them (And none of them will be seperate). Except the root (which has no parent) .. So in a tree we will always have answer 1.

      But, if we add one more edge to the tree. We can satisfy the earlier separated node (i.e root). So, if we have a cycle in the tree. It would have answer 0.

      So finally see all the connected components that doesn't have a cycle (count all the connected components that are actually trees). This could be done easily with a DFS.

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

Please someone explain this solution ( http://codeforces.com/contest/659/submission/17054528 ) for problem D.

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

I first submitted a solution in problem E which got WA in pretest 9, then i get a new idea which gets AC, but i do not understand why my first idea was wrong!!

I gets the in degree for each node and greedlly subtract the highest m value of them (one by one using priority queue ) and the answer is the number of zero in degree after that, and this is the code 17050130

why this is wrong?! what i missed here?!

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

When will the ratings be updated? Has anyone's been updated yet?

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

Can anyone help me please ? Why I am getting WA at Test 15 for Problem B ???

http://codeforces.com/contest/659/submission/17059710

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

Is AlphaGo not a single coder?

The coding style of the submissions by this account are different. For examples, solutions on C and F used:

#ifndef ONLINE_JUDGE
	freopen("input.txt","r",stdin);
	freopen("output.txt","w",stdout);
#endif

while others don't.

And solutions on E and F used:

#include <bits/stdc++.h>

while others don't.

We can find that the coding styles of different codes are not similar.

On the other hand, AlphaGo used only 3 seconds to submit B after C. Should this kind of accounts be banned?

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

Can someone tell me why I am getting TLE in my solution for B , I am trying to find bug around 2 hours : 17055144 ?

Thanks in advance.

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

First time to solve A-B-C-D-E during the contest time and guess what!! my rate decreased :(

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

Please let us open the problemset now

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

This is my first round to get an AC problem, nice problems (y)

btw this is also my first comment in CF xD

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

Can someone tell me what is wrong with my B solution? 17044686

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

Before and After system test

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

thanks dude! 17057269

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

I had a problem with the 53 test case of the B problem. My output is correct, and the author of the problem didn't estipulate any order of the names of the selected member of the team...

I got wrong answer, and the checker message was "wrong answer Jury solution is better than the participant [region=143]" ... I just don't understand the reason that i've received WA...

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

    Before checking [1] == [2] you must ensure that there is at least 3 participant, otherwise equality checking result would be undefined

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

Can anyone explain this solution to E. for me? 17042676 by AlphaGo

I think I get that the array fa represents the "root" of each node's connected component. What are tot and TOT?

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

    tot: vetexes count TOT: edges count if TOT==tot, there is a circle

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

      Thank you! Do you know what purpose this line serves? tot[u] = TOT[u] = 0

      Edit: I just tried running the submission, exactly copied, but with that line removed. It still passed all tests. So it looks like that line is unnecessary.

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

As the tutorial said, we can make a boolean array in problem c; but i failed to do it at c++, because array size of 1e9 was too great, can anyone tell me how to achieve that, thank you

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

    Using sets. Learn STL as soon as possible. Because it's very useful and easy.

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

    The editorial also specified to maintain a boolean array of max 2*10**5 and from the input numbers mark only those that are less then 2*10**5.