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

Автор ch_egor, 13 дней назад, По-русски,

Всем привет!

В эти дни в Москве проходит уже четвёртая Международная олимпиада мегаполисов — международное соревнование для школьников из крупнейших городов и столиц мира, одной из дисциплин которого является информатика. Над турами по информатике имели удовольствие работать члены жюри, приглашённые из Санкт-Петербурга, Минска и Белграда, а также Московская методическая комиссия, известная вам по Московской командной олимпиаде, Открытой олимпиаде школьников по программированию и Московской олимпиаде для 6-9 классов (раунды 327, 342, 345, 376, 401, 433, 441, 466, 469, 507, 516, 541, 545, 567).

В составе жюри олимпиады: Chmel_Tolstiy, Jelena Hadži-Purić, Елена Андреева, Zlobober, GlebsHP, andrewzta, meshanya.

Задачи олимпиады разрабатывали isaf27, _kun_, manoprenko, GoToCoding, ch_egor, gritukan, voidmax, grphil, malcolm под руководством GlebsHP и Zlobober.

Задачи адаптированы под codeforces V--gLaSsH0ldEr593--V и _kun_, спасибо MikeMirzayanov за системы codeforces и polygon, который использовался при подготове задач этой олимпиады. Также спасибо за тестирование LHiC, voidmax и wrg0ababd!

Всем удачи и высокого рейтинга!

Раунд состоится 04.09.2019 12:05 (Московское время) и будет идти два с половиной часа.

Раунд будет состоять из 8 задач и будет общим для обоих дивизионов. Раунд будет рейтинговым для всех участников!

P.S. Мы просим всех, кто участвует или знает задачи с основного соревнования, воздержаться от участия в раунде и публичного обсуждения задач, в противном случае вы можете быть дисквалифицированы.

UPD1: Победители!

  1. wxhtxdy
  2. gina0605
  3. grumpy_gordon
  4. Radewoosh
  5. kefaa2
  6. cz_yixuanxu
  7. ko_osaga
  8. mango_lassi
  9. Dreaming_to_be_an_LGM
  10. ksun48

Разбор будет опубликован скоро.

UPD2: Разбор

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

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

Вообще плохо, что слишком рано начинается контест, потому что многие школьники просто не успеют на этот контест.

Но ничего, буду виртуалкой дорешивать. :)

В любом случае, желаю удачи участникам.

P.S : да, получилось не совсем то, что я хотел сказать.

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

    Вообще плохо, что люди пишут мусорные комментарии на CF. Но ты держи всех в курсе, может еще что-то поменяется и ты успеешь на раунд.

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

      Ну да, ответить мусорному комментарию мусорным комментарием тоже отлично.

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

    Если ты из Москвы, то да, а есть те, для кого слишком поздно в 17:35 по МСК.

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

We kindly ask everybody who knows problems of an onsite event not to participate in a round and not to discuss them in public, as this may be a subject for disqualification.

This round reminds me https://codeforces.com/blog/entry/65664

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

Excellent time for Chinese participants! waiting for a good round.

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

Unusual Time.

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

I have rating $$$583$$$ before Codeforces Round $$$583$$$. See how much it will be after the round.

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

Good

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

костры рябин

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

The problems in ( Div-1 & Div-2 ) combined contest are always interesting....

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

Waiting for a nice problems!!

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

US participants be like

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

is this contest like manthan?

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

We are from China, everyone that i am fighting is fucking from China, china, china #Drdisrespect

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

I believe that the main contest have problems go with subtasks. Will there be any mirror that we can gain points by solving subtasks?

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

This round is rated for div 2 ?

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

wish me luck I want to be master

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

is the round rated for everyone?

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

where is score distribution

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

Um_nik жив?

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

Solve E is Enough :D, time for relaxing

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

Как Um_nik сначала писал раунд а потом внезапно пропал ?

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

    Я понял, что задачи слишком сложные, у меня не получится выиграть и я солью рейтинг. Рейтинг — самое важное в моей жизни, поэтому я встал на колени и умолял Майка перевести меня во внеконкурсное участие. Великий Майк, храни его Господь, согласился.

    Я опубликовал скринкаст, на нем можно видеть как я просматриваю задачи и осознаю, что у меня нет шансов.

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

    Выяснилось, что Um_nik встречался с одной из задач во время тестирования другой олимпиады. Как я понимаю туда эту задачу не взяли, а на олимпиаду мегаполисов — взяли. И я и _kun_ извинились, когда узнали о ситуации. Я бы на месте участника просто порешал раунд внеконкурсно без этой задачи, есть же еще 7 других задач.

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

      Дада, это абсолютно полностью моя вина! Остальные задачи великолепные! Не читал, но восхищаюсь!

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

Why did you have to include finding a solution in G? It's just more coding and more ways to make stupid mistakes without any more interesting ideas. Also, why such high constraints? Do you want heavily optimised $$$O((N+M)Q)$$$ to pass?

Apart from that, G is very nice! I realised that the condition we need to check is if it's possible to keep removing fully black/white columns until nothing remains — if we can't, there is a solution.

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

What is test case 16 in D?

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

What was pretest 10 for F?

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

what was pretest 8 on problem D ?? I believe that answer should be either 0,1 or 2 . I got wa on pretest 8

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

What is pretest 12 in Problem D

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

what's in case 8 in D?

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

A was much harder than C

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

How To Solve D...?

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

    Basically we have to find cut vertex if I am not wrong . Answer can be 0,1,2

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

    You can solve it by maxFlow algorithm — you actually need minCut (same as maxFlow) from cell ($$$1,1$$$) to cell ($$$n, m$$$).

    EDIT : I had wrong implementation, but idea is correct.

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

      Can You Elaborate regarding minCut ?

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

      I believe Max Flow algo's generally take a significant time, of order (N^2-3).I may be wrong. Could you please elaborate on how to apply Max Flow Algo?

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

      It seems that you need to connect an edge with 1 capacity between the same point, say u -> u, or you will fail on this testcase:

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

      Seems quite overkill, but a cool idea!

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

    The insight is that there are only 3 possible answers: 0, 1, 2.

    The answer is 0 iff there is no path from (1, 1) to (n, m);

    As for the case when the answer is 1, the reasoning is as follows. Let's denote the set of valid paths from (1, 1) to (n, m) as P. It's obvious that the length of these paths is (n + m — 2). Let's say that, the kth step in all of these paths is the same. Then we can block this square and, by doing that, we guarantee that no paths remain. It's easy to see that the set of squares visited on the kth step satisfies the equation i + j = k (0-based notation). So we can simply set an array counting the number of such squares visited in the code for dfs. We include one more dfs to check, for every square, whether (n, m) is reachable from it. In this way we do not count "useless" squares which would not contribute to any path.

    In all other cases the answer is 2.

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

    My approach was, do a dfs mark all the cells which come path from 1,1 to n, m. Then we group marked cells on basis of there distance from 1, 1. If any group has only one cell answer is 1 other wise 2. Got runtime error so don't know for sure but looks like solution to me.

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

    Solution for Problem D:

    Let's call cell good if cell (n, m) is reachable from it. Now if cell (1, 1) isn't good then answer is obviously 0.

    Now let's delete every not good cell from graph. Let's consider every path from (1, 1) to some (i, j), we can easily see that every path have same length.

    Now we can think about graph, as graph made of layers. In layer number X, are all cells that distance from (1, 1) to it is equal to X.

    We know that every path from (1,1) to (n, m) must go through at least one vertex in each layer. We know that layer number 0 contains only cell (0, 0) and last layer contains only cell (n, m), so if we look at all others layers and at least one of them contains only one cell, then we know that every path from (1, 1) to (n, m) must go through that cell, and answer is 1.

    All of this can be done by two bfs's. Bfs on reverse graph to delete not good cells and second one to check if there is a layer with size equal to 1.

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

      can we solve D using concept of articulation point and bridges? Im getting TLE at 16th test case

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

        You can make a undirected graph using edges that belog to at least 1 path from 1,1 to n, m, and them check if there exists articulation point, if it exists, answer is 1 else its 2

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

      Does layers here directly correspond to the queue if we do a bfs from (1,1) to (n,m) ? If the queue contains only one element at some point of time then the answer is 1.

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

        yes but only if at queue you have only cells that have same distance from (1, 1)

        you can look at 60048095 where I implemented BFS using layers.

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

          So, here basically we are using one queue for each level of layer and the layer is defined by i+j=w. Nice!

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

    Simple solution :

    I did two DFS, the first to find a path going greedily downwards before rightward, and marking the cells with 'A'. If there is no A-path the answer is 0 Then try to find another path that does not use the 'A' cells, if there is one the answer is 2, else it's 1.

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

      can you share your code, i didn't get the complete intuition

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

        http://codeforces.com/contest/1214/submission/60006023

        In the code I make the second path (B-path) greedily rightward but it's not necessary.

        pt() just prints the map for debug.

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

          now i understood the solution. thanks for the code. and very nice solution

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

          i did same thing but getting TLE can u tell me the reason?

          60030230

          edit:: i think i got my problem,there is no need to backtrack!!

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

            Your DFS has a problem, because you unmark cells when you exit a dead-end, they might get visited again. On a map like this your code will be super slow :

            ....#
            ....#
            ....#
            ....#
            ####.
            

            So either you leave cells marked like I do (and think about why it won't change the validity of the algorithm), or you make an extra boolean map keeping if each cell has been visited.

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

          Thanks for your solution.

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

        The intuition as others said is :

        • the answer is at most 2 because you could block (1,2) and (2,1)

        • it is 0 if you can't reach the treasure

        • it is 2 iff there is two disjoint paths from start to end

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

        60023871

        In my solution check pathes from (0,1) and (1,0)

        After: I check that each diagonal have 2 diffirent ways for this pathes. I check diagonal because all points on diagonal points that we can reach by the same number of steps.

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

A was much harder than C

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

How to check wheter blocking 1 cell is enough in D?

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

    If there is any articulation point in the graph of all the vertices that reach the cell NxM, starting from 1x1, the answer is 1.

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

      Can we find articulation point in directed graph?

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

        I wasn't able, but I was trying to consider all the edges bidirected. I recieved TLE 16.

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

        No, you have to make it undirected.

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

          We can do so because of the fact that graph is acyclic, in other case we wouldnt be able to do so am i right?

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

            I'm not sure why it would matter here. The definition of articulation point is based on the connectedness of undirected graph so it doesn't care about how you transform your directed graph. The only thing to take note here is we should exclude cells that are not connected to either top left or bottom right.

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

        Yes, we can use dominators tree.

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

    check for both cases by blocking one by one.

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

    If we block cell (i,j) Then cells with row = i & col > j should have paths originating only from (i,j) and same for cells with col = j & row > i. Use some precalculation and cumulative sums.

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

    Let x = number of paths from (1, 1) to (i,j) and y = from (i, j) to (n, m). Then, it suffices to check if there exists some cell(i, j) such that x*y = Number of paths from (1, 1) to (n, m). It can be checked mod prime with some randomization to prevent hacks.

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

    If you can only reach one cell in the diagonal defined by cells having same sum of (i + j) then after blocking that cell you can't reach the corner.

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

    First, ignore all cells through which there is no path from (1, 1) or no path to (n, m). Then do a bfs on this new grid. If at any point the queue size is 1 and the element in the queue is not (1, 1) or (n, m), then this cell can be blocked. The same idea works for any general graph.

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

    I checked for it during BFS,when queue size was exactly 1, and it didn't have points of start and end, but i didn't push useless cells in queue.

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

    I've created two paths, one trying to go right whenever possible and one trying to go down. If those two paths intersect that intersection should be necessary and answer is 1.

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

      I used the same solution, but I TLEd on test case 189. How did you precompute which squares had possible paths, and which didn't?

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

        dp[i][j] = true iff u can reach (i,j) from cell (n,m); else dp[i][j] = false; U can easily calculate it in n*m. After this just greedy construct these 2 paths using this dp to check wheter you can go in direction you want.

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

        You can refer this code. 60043962

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

    I have another way to find the blocking cell:

    Denote $$$f(i_1, j_1, i_2, j_2)$$$ as the number of ways to go from $$$(i_1, j_1)$$$ to $$$(i_2, j_2)$$$. A cell $$$(i, j)$$$ is a blocking cell if and only if $$$f(1, 1, i, j) * f(i, j, n, m) = f(1, 1, n, m)$$$

    We can calculate the required terms using DP. The number of ways can be large so we need to use some hashing.

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

      Sounds good, doesn't work. I had exactly the same solution with 2 different modulo for hashing, but it got WA on the test 224. OMG -_-.

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

        Oh my god... I got passed by using 4 random modulos among the 7 I chose. You are so unlucky....

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

        I got the same result. I guess your modulos are 1e9+7 and 1e9+9.

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

      I think you don't need to calculate number of ways. If exists way from (1,2) and (2,1) you can only check that all diagonals (same step) have different way for way1 and way2. If only one way exists result = 1, else result = 2. Solve after contest :) 60023871

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

    Build the directed graph $$$G$$$, represent cell $$$(1,1)$$$ as node $$$0$$$ and cell $$$(n, m)$$$ as node $$$nm-1$$$ in $$$G$$$. Now we need to check if the min number of nodes needed to delete in order to disconnect $$$0$$$ and $$$nm-1$$$, which is essentially max flow with node capacities $$$1$$$, is 1 or not. Make another graph $$$G^t$$$ consisting of two nodes $$$I_u$$$ and $$$O_u$$$ for each node $$$u$$$ in $$$G$$$. Add edge $$$I_u \rightarrow O_u$$$ for all $$$u$$$. Also for every edge $$$u \rightarrow v$$$ in $$$G$$$, add edge $$$O_u \rightarrow I_v$$$ in $$$G^t$$$. All edge capacities are $$$1$$$. Now, we just need to check if the max flow from $$$S = O_0$$$ to $$$T = I_{nm-1}$$$ in $$$G^t$$$ is $$$> 1$$$ or not. Take a simple path from $$$S$$$ to $$$T$$$, if none exists, print $$$0$$$, otherwise, reverse the direction of every edge of that path. Now, try to go from $$$S$$$ to $$$T$$$ again, if it's possible, then max flow is $$$\ge 2$$$ (more precisely, exactly $$$2$$$ in this problem), print $$$2$$$, otherwise, max flow is $$$1$$$. To see why it is what it is, this is essentially the first two steps of Ford Fulkerson's algorithm. Code. Credit goes to Bruteforceman

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

    One easy idea on D. You BFS from (1, 1) to (N, M), and back from (N, M) to (1, 1) — and paint these cells. Any painted cell means that there exists a path through it. Then you check every diagonal line (up-right direction): how much painted cells does it contain. Minimum is an answer.

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

Problem H "Thinking is very very easier than coding"

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

Any hints for E???

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

    Try to place bulbs with indexes 2,4,6..2n in the line in order of decreasing di corresponding to each bulb.

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

    You can initially construct a chain $$$n$$$ node.

    Sort the distance from long to short.

    Then for the distance $$$k$$$ :

    For the $$$2i-1$$$ it takes the $$$i$$$_th vertice on the chain. Then we check if $$$i+k-1$$$:

    If $$$i+k-1>n$$$ we create a new vertice on the chain, as we sorted it before, the vertice $$$i+k-2$$$ must be existed.

    Otherwise it links to the vertice $$$i+k-1$$$ on the chain.

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

В задаче 981F - Круговой марьяж используется совершенно такая же идея как и в сегодняшней F. Причем с этой идеей задача становится крайне простой.

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

Can someone explain me what exactly B was trying to ask?

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

    It's confusing!

    sample inputs doesn't output minimum number!!

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

      I'll explain to you the second sample : 5 boys 3 girls

      5 board games tournament participants. ===== I have n+1 decks of n badges as follows : 1: 0 5 //wrong because all the g girls is 3not5 ******** 2: 1 4 //wrong because all the g girls is 3not4 ******** 3: 2 3 //correct ******* 4: 3 2 //correct ****** 5: 4 1 //correct ****** 6: 5 0 //correct ******

      Notice : I can have a number of blue badges is less than b Or number of red badges is less than g .

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

        My answer got accepted which is: ~~~~~ FOR(i, n+1) { if (i <= b && n — i <= g) { ans++; } } ~~~~~ And this doesn't look for minimum, it checks for correctness!!

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

          Exactly , I think word"minimum" is mentioned by mistake :( And this is my correct answer :

          long long b , g , n , x=0,y=0, c=0;

          cin >> b >> g >> n ; 
          
          for(int i=0 ; i<=n ; x++,i++)
          {
              y=n-x;
          
              if(x<=b && y<=g) c++ ; 
          }
          
          re cout<<c,0;
          
»
12 дней назад, # |
  Проголосовать: нравится +4 Проголосовать: не нравится

For problem D, I initially did sth like count the number of cells can be reached at every second and I believed the answer would be the smallest count of all instances except the starting and ending ones. However, it failed on pretest 12. Could anyone explain to me why this is wrong? Thanks.

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

    I think this might be the case:

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

    Probably because you count useless cells?

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

      Ooops, that's the hack! Thanks

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

      But can I fix this by go in the reverse direction (starting from the lower-right cell and moving only upwards and leftwards) after the first iteration? Then I count the number of cells in each distance in both ways?

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

        deleted

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

        It works if you count number of cells in intersection, rather than in forward/backward sets separately.

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

          Sorry that my explanation was not clear here. Yes, I mean to count only the cells reachable from both directions.

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

        You are correct, just got AC with it. I implemented this during contest but got WA because of using bool dp[n][m]={0}, I forgot that variable length arrays can't be initialized.

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

I think I saw Um_nik on scoreboard but cannot see him now, Why?

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

    It seems to me that this is an unpleasant working situation, which occasionally may well happen. It seems that there is no regular similar problem. (I want to thank MikeMirzayanov for beautiful Telegram and Google Translate platforms).

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

      What do you mean ?

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

        He mean he performed badly, but since he's an LGM he can message MikeMirzayanov and get away with it, I'm wondering what will happen if I asked that ?

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

          Lol.
          It means he knew some problems beforehand. Hence, he asked mike to remove him.

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

            Not exactly, but on basic level that is what has happened, yes.

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

            As far as I know, once you submit a problem the contest will be rated for you, can you tell me why it didn't apply in this case?

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

      ah man, that's some rick level shit

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

when we can see the Editorial ????????????????????????

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

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

I was late by half a minute to submit to G, I think I had a valid solution :(

solution? to G

Edit: 60020107 so seems to work

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

    Seems like it should work, you can submit now.

    I had a completely different approach to the same condition — removing unicolored rows and columns. It doesn't allow bitsets, but I'll see if I can get it to pass.

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

    maybe try increasing the percentage of mango next time

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

The problem F was absolutely the same as 2006-2007 Summer Petrozavodsk Camp, Petr Mitrichev Contest 1 problem H.

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

    It's also the same as this problem (in Finnish), except that here $$$m$$$ was large and you had to output who works where, and in that problem you are given the number of workers and factories at every location. Furthermore, that problem is from a problemset of known educational problems we use here to practice for IOI, so I'm surprised this contests's organisers thought it was novel.

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

      so you have to solve it with min cost max matching? Could you detail the solution?

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

        So the translated problem statement of that problem is:

        There are $$$n \leq 10^{5}$$$ children in a circle, initially the $$$i$$$'th has $$$k_{i} \leq 10^{9}$$$ candies. At every second, one child gives one candy to either of the children sitting next to them. At least how much time must pass so that all children have the same amount of candies?

        So if there are $$$nm$$$ candies in total, then if $$$k_{i} < m$$$ we can say there are $$$m - k_{i}$$$ factories at position $$$i$$$, and otherwise there are $$$k_{i} - m$$$ workers at position $$$i$$$.

        To solve both problems, let $$$w_{i}$$$ be the amount of workers at position $$$i$$$, and $$$f_{i}$$$ the amount of factories respectively. If no worker travels between cities $$$1$$$ and $$$m$$$, the total cost is $$$cost(0) = \sum_{i = 1}^{m} \left|\sum_{j = 1}^{i-1} w_{j} - f_{j}\right|$$$ (the sum of absolute values of prefixes), since exactly $$$\left|\sum_{j = 1}^{i-1} w_{j} - f_{j} \right|$$$ workers have to travel between cities $$$i$$$ and $$$i-1$$$ on their way to work.

        Let $$$c$$$ denote the number of workers who travel from city $$$m$$$ to $$$1$$$, where $$$c$$$ is negative if $$$|c|$$$ workers travel from $$$1$$$ to $$$m$$$. Then the total cost will be $$$cost(c) = \sum_{i = 1}^{m} \left|c + \sum_{j = 1}^{i-1} v_{j}\right|$$$ with the same argument as before. But defining $$$v_{i} = \sum_{j = 1}^{i-1} w_{i} - f_{i}$$$, we get $$$cost(c) = \sum_{i = 1}^{m} \left| c + v_{i}\right|$$$, which is easy to minimise with the sweeping line technique.

        To apply sweeping line, notice that the term $$$\left|c + v_{i}\right|$$$ contributes $$$1$$$ to $$$cost(c+1) - cost(c)$$$ if $$$c \geq -v_{i}$$$, and $$$-1$$$ otherwise. Therefore the gradient changes only at $$$m$$$ positions, and we can loop until $$$cost(c+1) - cost(c) > 0$$$.

        Once you know the optimal $$$c$$$, it is easy to find the optimal pairing of workers and factories. Having large $$$m$$$ just adds weights to the absolute values corresponding to the distance between cities $$$i$$$ and $$$j$$$. So the reduction from that problem to the one in this contest doesn't show any difficulties.

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

    I see a submission using ternary search in F, why is it works?

    60035603

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

TLE on Test 189 of problem D, that hurt!

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

Please open the test cases...

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

How to solve problem A? Can someone please help.

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

    let k,k1 be the number of dollars and euros used respectively. k1 must be a multiple of five and the answer will be the minimum of n-k1*e-k*d for given values of k1 and k, which you can get by running a loop on k1 and stopping when k1*e is bigger than n

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

The problem in this round is good,but the pretest is not strong.

Some my classmates read the wrong problem of D,they think that's cut the edge,not cut the points,but they passed the pretest.

Why many div1+div2 rounds is hackforces(Codeforces Global Round 1,2,3 is hackforces,too.)

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

Is It me only or problems B and C were easier than A?

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

    The number of users who solved problem B and C is more than problem A.

    So I think problem B and C is easier than A.

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

      You're right.

      Can you tell me how did you approach both A and D?

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

        I use maxflow to solve D,but I think their have an easy way to solve it.

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

          I solved it later on using DFS. I'm not certain if there's a way to hack it, though.

          You can run a DFS and stop once you reach the destination. Then you mark the start and end points as unvisited and run the DFS for the second time. If now you weren't able to reach the destination node, that means that there was a single path to the end point that was blocked, so the answer is 1. If you could still reach the destination node, that means there are more than 1 possible paths from start to end, so you must block both.

          If you couldn't reach the destination node from the start (first DFS), then the answer is 0.

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

What is test 44 of problem D?

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

No tall, thin grids in pretests for D? Sad.... I guess I'm used to assuming n, m <= 1000

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

how to approach problem A? i used ans= min((n%d)%(5*e), (n%5*e)%d) and failed -_-

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

    I tried use that and failed too...

    Just use brute force:

    int ans = n % d;
    n -= 5 * e;
    for (int i = 1;n >= 0;i++) {
    	ans = min(ans, n % d); n -= 5 * e;
    }
    
  • »
    »
    11 дней назад, # ^ |
    Rev. 5   Проголосовать: нравится 0 Проголосовать: не нравится

    Basically you want to find x and y such that (n - x*d - y*(5*e)) is minimum.

    What you do is brute force x (with the possible set of bills given, you can have any amount since you can take unlimited bills) and calculate the maximum amount of euros you can buy with what's left: n - x*d.

    Something like this:

    e*=5; // there's no 1 euro bill
    int ans = INF;
    for(int x = 0; x <= (n/d); x++){
        int y = (n - x*d)/e;
        ans = min(ans, n - x*d - y*e);
    }
    
  • »
    »
    11 дней назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Another way could be to use dp. At any point we can choose b/w taking 'd' dollar or '5*e' euros. dp[i] represents the minimum money you'll end up with if you start from 'i'. for every multiple of d and every multiple of 5*e dp[i] will be zero. For every i<min(d,5*e) dp[i]=i and for i>min(d,5*e) you've dp[i] = min(dp[i-d],dp[i-(5*e)]). Ans will be dp[n]

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

Very weak pretests. In every single page of standing you can see several fails!

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

Why can't we see another's submission now ?

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

Crappy English in statements. In problem B where was it mentioned that you could take take some decks but when distributing badges, you only have to distribute from a single deck? I wasted 45 minutes figuring out on this, and later just assumed it to be that way got Accepted. Also the word "minimum" was missing before but I could not complain much about that because it was somewhat clear from the sample test cases.

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

Has someone link with results from official contest ?

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

Problem D I got WA on test 224, someone pls tell me where I wrong

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

    You should use more than 1 prime number to hash the number of ways.

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

      But I failed that test case for both prime numbers, so I don't think that's problem

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

        The probability that you will fail on both numbers at the same time is extremely low.

        Moreover, 1e9 + 11 isn't prime.

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

          If it's just the modulo, that doesn't have to be prime. Hashes modulo several numbers are equivalent to the hash modulo their LCM (because CRT). That shouldn't be a problem.

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

      I got Accepted using only 1e9 + 7(During onsite). But I got WA122 with 998244353.

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

Congratulations to cerberus97 for having highest rating ever on Codeforces from India.

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

Lesson learnt: Always use 2 hashes.

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

Can someone explain why my code fails for test 20 for D? https://codeforces.com/contest/1214/submission/60018456

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

    Vasya got off the ship in cell $$$(1,1)$$$. Now he wants to reach the treasure. He is hurrying up, so he can move only from cell to the cell in next row (downwards) or next column (rightwards), i.e. from cell $$$(x,y)$$$ he can move ONLY to cells $$$(x+1,y)$$$ and $$$(x,y+1)$$$.

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

    Same pblm...can't understand why?

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

Congrats on Emdadul_Islam who got submission #60000000 in this contest!

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

Why so strict limit for problem D? It is 1000 ms for 1 million chars input.

I tried with Perl, but got TLE, and after contest I found only one solution with Python (PyPy3 996 ms). Was problem adopted for Codeforces? Why not to limit by 2s or 4s? Or any bad solutions with C++ could pass?

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

Please Publish the editorial

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

Can someone explain why my code for D fails for test 22.I used the code for articulation point.60033722

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

A was harder than D

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

Thank you for great round, When the editorial will be published?

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

One of the best D. :p. A was so hard , harder than D

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

I'm a newbie, how to good at Competitive Programming and algorithms and Data Structures, I don't know where I have to start, please guide me.

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

Would someone tell me how to solve F? Thank u.