Если вы используете C++, пожалуйста, выберите в качестве компилятора при отправке решения: C++14 (GCC 6-32) или C++17 (GCC 7-32). ×

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

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

Всем привет!

В эти дни в Москве проходит уже четвёртая Международная олимпиада мегаполисов — международное соревнование для школьников из крупнейших городов и столиц мира, одной из дисциплин которого является информатика. Над турами по информатике имели удовольствие работать члены жюри, приглашённые из Санкт-Петербурга, Минска и Белграда, а также Московская методическая комиссия, известная вам по Московской командной олимпиаде, Открытой олимпиаде школьников по программированию и Московской олимпиаде для 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, cdkrot, manoprenko, GoToCoding, ch_egor, vintage_Vlad_Makeev, voidmax, grphil, malcolm под руководством GlebsHP и Zlobober.

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

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

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

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

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

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

  1. jqdai0815
  2. gina0605
  3. never_giveup
  4. Radewoosh
  5. 244mhq
  6. cz_yixuanxu
  7. ko_osaga
  8. mango_lassi
  9. GoForIt
  10. ksun48

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

UPD2: Разбор

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Unusual Time.

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

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

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

Good

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

костры рябин

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

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

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

Waiting for a nice problems!!

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

US participants be like

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

is this contest like manthan?

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

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

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

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

This round is rated for div 2 ?

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

is the round rated for everyone?

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

where is score distribution

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

Um_nik жив?

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

Solve E is Enough :D, time for relaxing

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

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

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

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

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

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

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

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

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

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

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

What is test case 16 in D?

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

What was pretest 10 for F?

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

What is pretest 12 in Problem D

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

what's in case 8 in D?

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

How To Solve D...?

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

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

  • »
    »
    5 лет назад, # ^ |
    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.

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

      Can You Elaborate regarding minCut ?

    • »
      »
      »
      5 лет назад, # ^ |
        Проголосовать: нравится +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?

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

      Seems quite overkill, but a cool idea!

  • »
    »
    5 лет назад, # ^ |
    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.

  • »
    »
    5 лет назад, # ^ |
      Проголосовать: нравится +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.

  • »
    »
    5 лет назад, # ^ |
      Проголосовать: нравится +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.

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

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

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

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

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

  • »
    »
    5 лет назад, # ^ |
    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.

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

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

      • »
        »
        »
        »
        5 лет назад, # ^ |
          Проголосовать: нравится +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.

        • »
          »
          »
          »
          »
          5 лет назад, # ^ |
          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!!

          • »
            »
            »
            »
            »
            »
            5 лет назад, # ^ |
            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.

      • »
        »
        »
        »
        5 лет назад, # ^ |
        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

      • »
        »
        »
        »
        5 лет назад, # ^ |
          Проголосовать: нравится +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.

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

A was much harder than C

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

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

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

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

      Can we find articulation point in directed graph?

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

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

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

        No, you have to make it undirected.

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

          • »
            »
            »
            »
            »
            »
            5 лет назад, # ^ |
            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.

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

        Yes, we can use dominators tree.

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

    check for both cases by blocking one by one.

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

  • »
    »
    5 лет назад, # ^ |
      Проголосовать: нравится +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.

  • »
    »
    5 лет назад, # ^ |
      Проголосовать: нравится +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.

  • »
    »
    5 лет назад, # ^ |
    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.

  • »
    »
    5 лет назад, # ^ |
    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.

  • »
    »
    5 лет назад, # ^ |
    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.

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

      • »
        »
        »
        »
        5 лет назад, # ^ |
        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.

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

        You can refer this code. 60043962

  • »
    »
    5 лет назад, # ^ |
      Проголосовать: нравится +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.

    • »
      »
      »
      5 лет назад, # ^ |
        Проголосовать: нравится +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 -_-.

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

  • »
    »
    5 лет назад, # ^ |
    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

  • »
    »
    5 лет назад, # ^ |
      Проголосовать: нравится +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.

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

Problem H "Thinking is very very easier than coding"

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

Any hints for E???

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

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

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

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

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

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

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

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

    It's confusing!

    sample inputs doesn't output minimum number!!

    • »
      »
      »
      5 лет назад, # ^ |
      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 .

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

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

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

    I think this might be the case:

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

    Probably because you count useless cells?

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

      Ooops, that's the hack! Thanks

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

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

        deleted

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

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

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

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

      • »
        »
        »
        »
        5 лет назад, # ^ |
          Проголосовать: нравится +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.

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

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

  • »
    »
    5 лет назад, # ^ |
      Проголосовать: нравится -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).

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

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

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

»
5 лет назад, # |
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

  • »
    »
    5 лет назад, # ^ |
      Проголосовать: нравится +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.

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

    maybe try increasing the percentage of mango next time

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

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

  • »
    »
    5 лет назад, # ^ |
    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.

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

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

      • »
        »
        »
        »
        5 лет назад, # ^ |
          Проголосовать: нравится +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.

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

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

    60035603

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

TLE on Test 189 of problem D, that hurt!

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

Please open the test cases...

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

How to solve problem A? Can someone please help.

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

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

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

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

  • »
    »
    5 лет назад, # ^ |
    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.

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

      You're right.

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

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

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

        • »
          »
          »
          »
          »
          5 лет назад, # ^ |
          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.

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

What is test 44 of problem D?

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

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

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

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

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

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

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

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

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

»
5 лет назад, # |
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.

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

Has someone link with results from official contest ?

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

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

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

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

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

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

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

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

        Moreover, 1e9 + 11 isn't prime.

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

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

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

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

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

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

Lesson learnt: Always use 2 hashes.

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

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

  • »
    »
    5 лет назад, # ^ |
    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)$$$.

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

    Same pblm...can't understand why?

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

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

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

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

Please Publish the editorial

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

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

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

A was harder than D

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

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

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

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

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