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

Автор vovuh, история, 6 лет назад, По-русски

Привет!

21 июня (четверг) в 17:35 (Московское время) начнётся Codeforces Round 490 (Div. 3) — очередной Codeforces раунд для третьего дивизиона. В этом раунде будет 6 задач, которые подобраны по сложности так, чтобы составить интересное соревнование для участников с рейтингами до 1600. Наверное, участникам из первого дивизиона они будут совсем не интересны, а для 1600-1899 покажутся простыми. Однако все желающие, чей рейтинг 1600 и выше могут зарегистрироваться на раунд вне конкурса.

Раунд пройдет по правилам образовательных раундов. Таким образом, во время раунда задачи будут тестироваться на предварительных тестах, а после раунда будет 12-ти часовая фаза открытых взломов. Я постарался сделать приличные тесты — так же как и вы буду расстроен, если у многих попадают решения после окончания контеста.

Вам будет предложено 6 задач и 2 часа на их решение.

Напоминаем, что в таблицу официальных результатов попадут только достоверные участники третьего дивизиона. Как написано по ссылке — это вынужденная мера для борьбы с неспортивным поведением. Для квалификации в качестве достоверного участника третьего дивизиона надо:

  • принять участие не менее чем в двух рейтинговых раундах (и решить в каждом из них хотя бы одну задачу),
  • не иметь в рейтинге точку 1900 или выше.

Независимо от того являетесь вы достоверными участниками третьего дивизиона или нет, если ваш рейтинг менее 1600, то раунд для вас будет рейтинговым.

Спасибо MikeMirzayanov за платформы, помощь с идеями для задач и координацию моей работы. Спасибо Михаилу awoo Пикляеву, Максиму Neon Мещерякову и Ивану BledDest Андросову за помощь в подготовке и тестирование раунда.

Удачи!

UPD: Также спасибо step_by_step, kevinsogo и nhho за помощь в подготовке раунда и его тестирование.

UPD2: Таблица результатов!

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

Rank Competitor Problems Solved Penalty
1 EricHuang2003 6 150
2 JerryKFC 6 151
3 Lovely_qgq 6 170
4 Meroeht 6 181
5 MYTH_vs_REALiTY 6 209

Поздравляем лучших взломщиков:

Rank Competitor Hack Count
1 djm03178 30:-2
2 2014CAIS01 13:-3
3 quailty 5:-2
4 Harmonium_Wale 4:-2
5 kimden 2

Было сделано 110 успешных взломов и 226 неудачных взломов!

И, наконец, поздравляем людей, отправивших первое полное решение по задаче:

Problem Competitor Penalty
A jh05013 0:01
B JerryKFC 0:02
C GrayGlobe 0:03
D T______________T 0:21
E NamikazeBoruto 0:11
F Counting_Stars 0:20

UPD3: Разбор

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

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

Thanks for conducting another div3 round!! Looking forward for participation :)

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

    I love it when people downvote comments for no apparent reason. The community of codeforces is great :)

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

      You know sometimes I downvote some users comments even before reading the comment, I just cant stand those users :3

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

Why it's not in the homepage?

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

Can't be there some provision that people with rating(1600-1899 or maybe some lower) can also participate in div3(rated for them too) rounds with a totally different rank list i.e no cushioning for them and ensuring that ratings don't cross past 1899.

And as stated during announcement of div3 rounds problems will be easy for participants in the range 1600-1899,so it will be matter of just time.

OR

Maintaining a different rating graph can also be a way.

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

    I don't understand what the point of something like this would be. Maintaining two different rating graphs would be an enormous pain with very little payoff imo. If you really want to see how fast you can do it, just participate unofficially, it's not a big deal. Div 2 contestants get enough rated contests as it is.

»
6 лет назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится
div-3 rocks, I think you will give some critical test cases. Getting hacked after contest is too much painful.
»
6 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Div-3 rocks. I think you will add some critical test cases.
»
6 лет назад, # |
  Проголосовать: нравится -8 Проголосовать: не нравится

i do not like ACM_STYLE

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

I have doubt on using 20-min WA penalty for all ACM-ICPC style contests. Usually, the contests on Codeforces are length of around 2 hours and have 5-7 problems. But in ACM-ICPC contests, there are usually much more problems (10+) and they have long contest time (3+ hours).

Taking this mathmetically, let's say if a contestant A needs 5 more minutes than B to solve each problem. If they solve only 5 problems, A will get 75 more penalty than B, because every time you spent on the previous problems will affect the later solved problems' penalty. But when there are 10 problems, it becomes 275. In other words, it's proportional to the square of the number of problems. On the other hand, the penalty from the WAs would only increase linearly, as each wrong submissions have fixed penalty.

I'm not the only one thinking this way as I saw similar opinions on previous Div. 3 or Educational rounds too. I'm much like for having just 10-minute WA penalty for 2-hour contests, especially in a Div. 3 round, considering the accuracy of the official contestants would be quite low. How do you think about it?

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

    Strongly agree. It is really painful when get so many WAs in an educational round. Your rank will drop significantly. Codeforces can't just use ACM-ICPC rules without changing them according to their contests.

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

    MikeMirzayanov, you might wanna check this comment and tell us what you think about it :)

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

    Ya even codechef changed their cook off penalty to 10 min for same reason.

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

I tried to make strong tests

I smelled FST :(

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

I like the term Hacked other than Failed System Test

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

2 hours to solve, 12 hours to hack... That's why I love CF... And then you get a "time limit" on the main test... :|

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

Looking for more frequent div3 contests such that beginners like me can learn! :) Best of luck everyone.

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

Rated or not? Maybe a silly question for others:(

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

IIR?

(Abbreviation of Is It Rated? :P)
»
6 лет назад, # |
  Проголосовать: нравится -16 Проголосовать: не нравится
  1. Open Codeforces
  2. See a contest
  3. Checks contest starting time (worries might clash with Argentina's match)
  4. Checks contest length
  5. Gives contest peacefully.

PS- Thanks for not clashing it with Argentina Vs Croatia match.

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

A contest right after the senior high school entrance examination in China. Hope I will win the scores I lost these two days back as ratings.

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

Объясните пожалуйста, чем в итоге отличается достоверный участник от недостоверного, разве это поможет борьбе с неспортивным поведением? Ведь в итоге он рейтинговый для всех. Смогут ли недостоверные взламывать?

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

    Кажется, админы сами не поняли, что ничем не отличается.

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

    Недостоверные участники не попадают в таблицу официальных результатов. Они делят таблицу результатов с неофициальными участниками. Таким образом, они почти незаметны для "достоверных". С одной стороны это понижает дискомфорт для честных участников (это всегда неприятно видеть выше себя нескольких новичков, которые, наверняка, участники из первого дивизиона), а с другой — уменьшает мотивацию читеров так себя вести. На взломы и подсчёт рейтинга это разделение не влияет.

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

      Спасибо, теперь почти всё понятно. У достоверных и недостоверных разные комнаты?

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

        Нет. Может и да, но ты об этом не узнаешь.

        Они просто появляются, когда тыкаешь "показывать неофиц." и отличаются тем, что имеют звездочку рядом с хэндлом

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

          IbragiMMamilov, я не прав.

          Мы будем исключать из официальной таблицы результатов Div. 3 раунда и помещать в отдельную комнату всех тех, кого достоверно сложно назвать реальным участником.

          https://mirror.codeforces.com/blog/entry/59228

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

my first div-3 contest. feeling excited!

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

Does hacking solutions increases points of the hacker?

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

the predictor isn't working !

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

What is the test case 4 of problem E

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

How to solve Problem E? I was using DSU + DFS, but was getting WA!!

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

    I did BFS + greedy

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

    I am just finding all connected components and print number of connected components-1 but keep getting WA on TC 4

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

    2 DFSs — keeping track of finish time.

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

    My idea : First, run dfs on capital vertex. While running dfs, make every path as bi-directional. Now build Strongly Connected Commponents. Count number of vertices which has 0 indegree expect the one containing capital vertex.

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

      I applied your method. Its giving wrong answer at test case #3.

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

        ummm :| I think you should read this

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

          Ok, I ran Dfs on capital vertex. While running DFS, i made bi-directional edge. (Thus every point reachable by capital can reach back to capital). Now i built strongly connected components.....(Correct me if i am wrong until this point). After that, my idea is to count all nodes with either indegree=0 or all strongly connected graphs with connected nodes more than 1.

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

            (Correct me if i am wrong until this point)

            As long as you use correct algorithm, (like tarjan's SCC or something) I think it would be fine.

            count all nodes with either indegree=0 or all strongly connected graphs with connected nodes more than 1.

            You can just count number of SCC vertices which has 0 indegree, but when counting, exclude a SCC vertex which contains the capital vertex.

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

    Kosaraju I think

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

      I used a similar idea but I didn't find the strongly connected components that Kosaraju does.

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

        What was your approach then?

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

          You run two DFSs. The first time you keep track of all the finishing times of the DFSs. Then run a DFS starting from the capital city. Then, while some cities are unvisited, keep starting a DFS from the unvisited city with the highest finish time, adding one each time we do.

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

          Its Kosaraju :P

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

Last three problems were a little difficult for div3

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

Спасибо за контест , задачи интересные были;

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

That was a lot of fun! Thanks vovuh

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

What is wrong with test case 8 in D. Any strong test case?

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

how to solve E?

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

    I did it as follows : 1.)Mark all vertices that can be visited from s(by simple DFS). 2.)For rest of the vertices run DFS and count the number of nodes that can be visited by each of them.Sort according to the number of nodes visited by a particular vertex. 3.)Now run DFS from the last node in the sorted list and count the number of components left.

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

Was it only me who was facing problem to submit in the last 45 min?

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

For E, I removed all vertices that are reachable from s (excluding s itself), and then found the condensation of the new graph. The number of SCC's with indegree 0 (excluding the possible SCC that contains s and has indegree 0) is the answer. Is there a simpler way to do it?

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

    Is this approach wrong? 1. Find out the topological sort of the graph 2. run dfs for given s mark all visited 3. In the order of the toposort, run dfs and count components. 4. answer is components-1.

    Btw, if u find anything wrong, u are free to hack!!

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

      What about cycles in graph ?

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

        I'm marking visited, so cycles won't be a problem. Provide a test case if u find anything fishy

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

          I mean , how are you doing topological sort if the graph has cycles

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

          which algo you are using for topological sort kahns or ... because kahns need atleast one vertice with indegree=0 in starting

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

            I'm marking visited, and then not visiting a vertex if its already visited. Cycles will be handled automatically I guess. Sorry that I'm not able to comprehend what u are trying to say, so u may look at the code:-

            999E

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

              I had a similar idea. But I cannot convince myself that this approach works. Can you please help me?

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

                Topological sorting gives you an order of vertices along which if you run dfs, you will get connected components in a directed graph. Thereafter, the answer is simply numComponents — 1

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

    if you don't mind can you please elaborate this : "The number of SCC's with indegree 0(excluding the possible SCC that contains s and has indegree 0) is the answer"?

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

      Each vertex in the condensation graph corresponds to an SCC in the original graph. Look at the vertices in the condensation graph that have indegree 0: clearly they are not reachable from s. The other vertices, ones with indegree > 0 are reachable from some vertex with indegree 0. Therefore, we can add edges from s to the vertices with indegree 0, and then the entire graph is reachable from s.

      However, there is one corner case: when the vertex (in the condensation graph) containing s has indegree 0, we don't want to count it since a vertex is certainly reachable from itself. The second example input corresponds to this case.

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

        thanks for the reply !

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

        What about the case when all the SCC's(excluding the vertex s) form a cycle(i.e none of them have indegree 0) and the vertex s is disconnected from the whole graph ?

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

          In that case, the cycle will actually just be 1 SCC. And since s is not a part of the cycle, the answer will be 1.

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

    Let a[i] be equal to 1, if we need edge (s, i) in optimal answer. Then instead of SCC after removing all nodes reachable from s, launch dfs from every non-used node v and assign a[i] to 0 for all reachable nodes from v. After that assign a[v] to 1. We can do it, because instead of any edge (s, i) we can place edge (s, v) if i is reachable from v.

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

    For every vertex count the number of vertices that can be visited from there. Use dfs from start and then you can iterate through every of these vertices in decreasing order and just use dfs once again.

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

    Can you please share your code ? I am not able to view your submission for problem E.

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

how to solve D ?

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

    first put all the remainders with counts less than n/m in a set and then iterate on each index with value greater than n/m and for each of them find the closest element in the set and add the required value.

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

      Can you please explain a little more what you did. What do you mean by "and for each of them find the closest element in the set and add the required value."

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

        yes, sure. First put all the remainders with counts less than (n/m) into a set and then iterate over each remainder which have value greater than (n/m) (let's suppose we are currently at 'i') and notice one thing we have to only move forward so, the best we can do is to conver current 'i' to it's nearest remainder having value less than (n/m) and so just do a binary search for that and find that index.(set's lower_bound will help you). Now, it may happen that we are at 'i' and there are no index in range [i, m-1] having value less than (n/m) so, in that case we have to search for the same from front.

        Hope it helps!

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

          Yes, Your comment made it very clear. Thank you :)

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

          Why should we convert "i" to the nearest remainder having value less than (n/m)? Can't we covert it to any remainder having value less than (n/m)?

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

            because it may happen that some of the remainders before it (nearer to the current one) has a value greater than (n/m) and so, if we convert that then we have to pay less.

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

              Anyway, all remainders have to be filled equally. So if we convert "i" to its nearest one, then there may be some "j" which needs to travel farther and satisfy the next remainder. Else, if "i" already travelled farther and satisfied the second remainder, then "j" will just have to satisfy the nearest (first) encountered remainder. Both ways seem the same to me. Am I going wrong somewhere? If yes, please explain with a small counter case.

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

                you forget that we can only move right!

                let's aarray be 3 1 4 1 1 and we have to make all 2's.

                Then if we add 3's 1 to the 4th position (instead of nearest 2nd) then we have to take the 4's 1 to the 2nd position in which we have a total cost of (3 + 2 + 4) instead of the optimal cost which is (1 + 1 + 2).

                Hope it makes your doubt clear.

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

      i thought abt it..but don't u thnk it's complexity will be O(n*n/4)??

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

        see there are atmost 'n — m' elements that are greater than n/m and similarly 'n-m' indexes are there which have less than value n/m. So, we are inserting 'n — m' elements and for each of 'n-m' element we are doing a binary search. so, O(NlogN)

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

    Consider every reminder c[i] a container that can hold at max n/m numbers. As you read the input you put a[i] in the container c[ a[i] % m ], if it's full: you put it in the next available container and add to a[i] the number of steps. To do it quickly the next available container is registered in another array.

    Let me know if that makes sense.

    EDIT: An array to store the next available container isn't good enough, a set is needed.

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

      Hey there! I am also very stuck on this problem and your solution is not making sense to me. I have some questions, hope you will answer.

      -- If C[ a[] % m ] is full, how do you decide the next bucket in the container? Why do you add a[i] number of steps?

      -- At the end how do you track what the final array is?

      Thanks

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

        This is the code if you couldn't find it 39498091.

        -I decide the next bucket by lower_bound(a[i] % m) in a set of buckets, every time a bucket is full I erase it

        -I add to a[i] the difference between the buckets, which is how many times I have to increase it

        -The final array is the original one that I changed every time

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

How to solve F?

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

    Consider any single number of card. Now the problem is 'For given N cards and M people, each person can have at most k cards. What is the maximum score?'

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

      orange4glace, Sorry, I didn't get. Can you please elaborate more, what's the intuition behind solving problem F with an example?

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

        Since h is strictly increasing, it is optimal to distribute as much as favorite cards to each peraon. eg. Let 3 people likes card 1 and each person has 2 cards. If number of card 1 is greater than or equal to 3×2, just distribute 2 cards for each and leftovers are 'dont care'(any other will have it and it has no effect to score) Else if the number of cards is less than 3×2, now the problem is distribute m cards to 3 people while maximum the score

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

Четкие задачи, но резкий скачок от C (3372 успешные посылки) к D (381 успешная посылка) — это мощно)

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

can anyone help me how to solve problem D????

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

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

Help on E appreciated, please let me know what's wrong with this approach (which fails pretest 4):

  • Mark all vertices that are reachable from the capital (via DFS);
  • For any vertices not reachable from the capital, count (via DFS) the number of child vertices that are still not reachable from the capital, and put them in a priority queue sorted in decreasing number of children;
  • Greedily add an edge from the capital to the first vertex in the priority queue, and mark (via DFS) vertices that are now reachable from the capital, removing them from the priority queue;
  • Repeat the previous step until the priority queue is empty.

Thanks a lot for any insight!

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

    When you remove the first element of the priority queue along with all of its childs it is possible that you change the degrees of some of the vertices that are still going to stay in the queue.

  • »
    »
    6 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    check this test
    8 7 1
    2 3
    2 4
    2 5
    2 6
    7 4
    7 5
    8 7
    
    the answer is 2
    in your approach the answer will be 3 as i think ,is it ?
    
»
6 лет назад, # |
  Проголосовать: нравится +27 Проголосовать: не нравится

I don't think it's OK to have contests in which almost all participants solve the first X problems, but then only a small percentage of them solve the (X + 1)th problem. The difficulty distribution seemed a little off for this round.

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

Any miniature version of test 4 of E?

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

    This test is just a complete directed graph with a 71 vertices and n * (n — 1) edges.

    UPD: Woops, the fifth test was a complete graph. I was wrong. The fourth test is a just random directed graph with an 5000 vertices and 5000 edges.

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

      vovuh Can you please tell will there be editorials for this round. They are not on home page.

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

        The editorial will be available in few minutes =) Sorry for delay, i was on the exam today

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

Can someone tell why 39491266 gives WA but 39491559 gives RE for problem D.

I only changed all "int" to "long long".

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

    maybe something overflowed and when you took the remainder you got a negative value, which then caused you to look at a negative entry of an array?

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

I had been debugging my solution D(39490746) for half an hour. When the contest is over and I saw the test case, I realized the result is long long. So it(39494662)passed...

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

I rage quited after 3WA's in E and D
After the contest I checked my E again and Saw this:

""Diagnostics detected issues [cpp.clang++-diagnose]: p71.cpp:92:12: runtime error: index 5000 out of bounds for type 'int [5000]'
SUMMARY: UndefinedBehaviorSanitizer: undefined-behavior p71.cpp:92:12 in""

I wish I would have checked my array sizes rather than rage quieting cf after 3WA's
and also wish codeforces will give RTE verdict rather than WA for these :p

Nice Problems Overall :D

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

Contest was not beautiful as its id.

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

How MYTH_vs_REALiTY solved all tasks in an hour ?

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

So, this was my first contest on Codeforces and I can't seem to find any ROOM link on the top menu bar nor can I find a way to lock my submissions so that I can participate in hacking. Do first time users don't have this privilege of hacking or am I missing something?

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

Thank vovuh for your contest, it was more difficult than last div 3 round.

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

    Funny, it seemed simpler to me! BTW, I found the last div 3 round more difficult than some div 2 (not that I have much experience, however)

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

I solved only 4 problems and its my first constest, my rank will go up or down?

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

Why My code for D getting runtime error on test 8 ?

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

In problem D i used a queue to store the number remainders . If the size of the remainders > n/m then we move one by one to the next container with the value (previous + 1). And keep doing that until everything is equal to n/m (only 1 needed 1 for) and traces and etc, why am i getting TLE ? and how can i fix this or maybe another approach ? Code : https://ideone.com/Z6Y8I5

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

    It seems to me like you have nested for loops. Oouter loops iterates until m and inner loop iterates until trace[i], which (at least at first glance) seems like it could be O(n). So overall complexity would be O(n^2)?

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

      ah okay i think i get it, so is there anyway to optimize it because i cant find a way to trace the answer

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

        You can use something like dsu (I don't know the name for this technique) so every remainder >= n/m won't be visited again

        http://mirror.codeforces.com/contest/999/submission/39476990

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

          Correct me if I am wrong but I think your solution has quadratic complexity as well. If n = m, then the only stop condition of your cari function is that val[x] is 0. So For a case like:

          200000 200000
          200000 199999 199998 199997 ...
          

          When processing the first number you'll take 1 step, when processing the 2nd number you'll take 2 steps etc. So overalall you'll take N*(N+1)/2 steps.

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

            Isn't the answer for that tc is 0 change? My val[x] is only incremented after I found the valid position for current number, so cari will only be called once for each number (Because val[x] is still 0)

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

              Sorry, I didn't notice you actually modify the nex array (also the test I wanted to type was an array full of zeroes, but it doesn't matter anyway).

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

          Nice technique bro thanks, i finally understand your code!

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

can someone help me to find out why the first solution was not accepted but second got accepted for problem B

http://mirror.codeforces.com/contest/999/submission/39483346

http://mirror.codeforces.com/contest/999/submission/39486399

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

    It is not advisable to insert characters in C++ string like this s[i]=ch. You are allowed to do this in character array string.

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

      Really? So... how did you do it in your solution?

      Are both of you joking?

      Maybe I miss something but...isn't the problem with s1[r--] operation? These parts of code aren't the same, of course:

      s1[r--]=s[i];
      

      compare with

      s1[r] = s[i];
      r--;
      

      Doing something with s1[-1] and s1[0] aren't the same.

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

        changing s1[r--]=s[i] to s1[r]=s[i] doesn't make any difference. Still runtime error in testcase 8.

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

          Oh, sorry. I was a little tired yesterday. aditya10 is right. Little more: string is an object. When you initialise "string s1;" constructor make it s1 = "".

          So, when you write "s1[r] = s[i]" you just change the element with address s.begin() + r (not s1). And... we don't no, what the rubbish is there. When you are trying to change it, you can get an error.

          When you print the s1 itself (cout << s1), you see that it doesn't change. s1 = "".

          So...just initialize "s1 = s;". Now it has got the same number of elements as s, and all will be ok.

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

        Doing s1[r--]=s[i]; and s1[r]=s[i];r--; are actually same. In post decrement value is decremented after being initialized.

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

Regarding question D

I wrote the code using lower_bound(st.begin(), st.end(), t) and got TLE but when i wrote the same code using st.lower_bound(t) it got AC. Why this happened???

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

A, B, C was too easy and C, D, E was too hard. So the standings will probably depend on penalties.

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

    ""A, B, C was too easy and C, D, E"" i geuss you meant F D E and thats actually true , they are harder than most B's in div 2

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

I just realized I really need to practice to be a better coder.. I got the idea of d but struggled alot coding it and didn't have the time to solve it because of some annoying coding mistakes :(

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

Why my solution for problem C is exceeding the time limit in testcase#5 despite having linear complexity? here is the link: http://mirror.codeforces.com/contest/999/submission/39496135

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

    I assume that anss=s[n-1-i]+anss; may be O(N).

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

    Because it doesn't have linear complexity :)

    The + operator for strings (from line anss=s[n-1-i]+anss;) is not constant time, but linear (see documentation). Considering the outer for loop as well, it results in quadratic time complexity.

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

Че-то у вас уже второй раз нифига не див 3 получается.

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

Hello! Can someone help me with Problem D? I saw the comment, but I do not understand it. Will appreciate if someone can explain the idea and how you reached it.

For Problem D, I did a BFS from the initial array until one array suceeds. This I feel is correct, but I had a memory limit exceeded within test 5.

Thanks

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

Hack for Problem C?

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

Can D be solved using two pointers ?

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

    I think its possible if you first sort the entries of the array in increasing value of the remainder mod m.

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

What is the effect on rating after hacking others solution in this round?

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

    Hacking that take place after contest have no effect on rank (for hacker). So no effect on rating.

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

can someone explain the idea of F?

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

    For a fixed type of cards you have x cards and c players that them likes this type, so compute the dp[i][j](maximum value that you can get) where i is the number of remaining players and j is the number of remaining cards initially dp[c][x]=0 and the answer will be in dp[0][0..x] I leave the link to my solution for a better understand of this idea: 39504913

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

Can someone explain question F to me? I've read it thrice but I do not understand.

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

My solution for D: 39490456.

I believe my answer is just a permutation of the correct answer ( 4 2 1 6 11 12 ). Should this not get accepted considering any array satisfying the required condition is correct?

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

    The only operation you can do is incrementing an array element, changing order is not allowed.

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

vovuh please check my submission for B it is not showing output on codeforces while the same is giving correct answer in my ide. This took my 40 mins. here is the code-!! :( Anyone having idea of this? Thanks for your insight!

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

    You can't use scanf/printf with ios_base::sync_with_stdio(false); You can read this blog (look for comments)

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

      Thank You! :)

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

      Actually, that's only half true. What you shouldn't do is MIXING either scanf/cin or printf/cout in the same code (since different streams aren't synchronized, there's no guarantee what will be read or written first). Otherwise, using only one from each pair is usually safe.

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

Problems A, B, C vs problems D, E, F

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

    But really why was it like this? 100 participants with a full mark and almost all others with only three questions... Then the one who just codes faster, gets a better result. Is it a marathon or a contest???

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

Newbie here! Can anyone explain why I got TLE on problem C?? Problem C submission

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

My solution for D: http://mirror.codeforces.com/contest/999/submission/39505442. I think it's O(n) ?

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

    can you please explain your approach?

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

    Last two for loops where each runs m times, contain a while loop. Can you explain how its complexity is still O(max(n,m)).

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

      each for loop runs m times, each while loop runs maximum n / m times => I think total complexity is O(m * n / m) = O(n) ?

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

        If we look at while loop independently, it will run the number of times equal to number of elements not "in place". So say all elements have same reminder, the while loop might run, roughly speaking, O(n*n/2) times. Still I am not sure, what do you think about it?

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

          int d = n / m;

          int need = d — v[i].size();

          => need <= d

          => need <= n / m

          while(need--) => each while loop runs atmost need times or n / m times.

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

Can anyone figure out the mistake in this solution for E? LINK

For tc #4, it is computing 1818 as the answer instead of 1817.

Approach : Run a dfs from source and mark all reachable nodes. Now, run a dfs from every unreachable node and mark all the ones that are being traversed from some parent. Suppose, we're running dfs from 2, we will mark every node reachable from 2 as visited, but we'll keep 2 as unvisited. This way, we will know the nodes(and components) which require a path from source.

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

    What if while running the second DFS you reach a node marked by the first DFS. What do you do?

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

      I'm ignoring it, because the nodes which can be reached from this node would've already been marked.

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

      I am facing the same problem. And does it matter that after running second dfs if we come across the visited nodes from the first dfs,as they are already visited and reachable from s.

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

    Check for this test case 5 4 5 1 2 2 3 3 1 4 3

    Correct Output: 1

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

Why is this http://mirror.codeforces.com/contest/999/submission/39505722 submission of mine for A giving WA on this case: 6 6 7 1 1 1 1 1 The answer is actually 5, but in cf it is showing 4. But in ideone compiler it is giving right answer. Link: https://ideone.com/je07LC

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

why rating is not updated yet?

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

did all the testcases are run or some testcases are yet to be judged during system testing

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

Is the system testing done? If not, when?

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

Can't believe that i have solved 5 problems!

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

For some reason 999F reminds me of game theory/mechanism design about auctions, when I first look at the joy level constraint I thought "oh this is a gross substitute valuation" instead of "oh it's strictly increasing"... Weird.

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

System testing has started now.

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

Need editorials!

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

.

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

Well I got TLE for C problem due to Java. That is why I am providing a link which could be helpful for Java programmers:

https://letsdocp.wordpress.com/2018/06/22/java-in-competitive-programming/

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

It would be great if someone can put editorial's link here. Thanks in advance.

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

I got TLE in Java for problem C and I got very confused about my logic. But then I researched a little more and I wrote this for Java programmers:

https://letsdocp.wordpress.com/2018/06/22/java-in-competitive-programming/

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

I am getting MLE in problem-D test-5 here. I have made vector and map of linear order.Anyone help ?

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

    I guess vectors do not release memory after popping up the elements. I used stack in your code hereinstead of vector and it shows TLE. The underlying approach is wrong.

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

all those who got stuck on test 4 of problem E can try this test case no 47: 8 8 1 3 2 3 4 4 5 5 3 6 4 6 7 7 8 8 6 ans:1 you might be getting 2...

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

UPD: I got the mistake

In E, for test case 20, I get answer as 11, whereas the solution ans is 12. I even added the edges and put asserts to check that every node is indeed reachable from s, however I did not get any assert failures. Someone please point out what's going wrong with my solution, thanks! 39515068

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

    i think you were first doing dfs of capital node and then for every non visited node ,finding all other nodes from where you can reach to that node ,by backtracking the reverse adjacent vector and doing dfs on all back nodes....

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

      I'm not sure about that. The mistake here was I added edges as bidirectional from input, but it actually has way more issues :P

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

    How to solve E?

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

      First check for every vertex 'a' how much vertices can go to 'a'. Then sort vertexes by sizes of groups. Notice that for every group you only need to add one road for all vertices in group to be connected to root. Iterate groups from biggest to lowest, check if road exist before you add one. If you add one road, notice that you made all vertices that belongs to the group connect to root. If they are connected, you shouldn't build roads because they're already connected.

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

      If you have for example root: 1 2->3 2->1 4->3 First sort groups (3 will be first, then 1 and 4)

      You add one road (3->1) and then 4 becomes connected. Next up is 4, but 4 is connected trough 3 so we move on. Next up is 2, but 2 is also connected to root.

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

I need help, even though my solution for test 1 was right, it gives WA on problem D. Here's the submission. Mine code outputs: 3 0 2 3 8 10 13 their answer: 3 0 2 3 7 10 14

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

    Input:

    6 3
    3 2 0 6 10 12
    

    Your Answer:

    3
    13 8 0 3 10 2 
    

    You can just increase elements by 1, you can't change the order.

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

I am getting WA at test# 4.

I tried Solving E: 1. Did the DFS on s, marked nodes visited. 2. initialized c = 0(counter: for counting connected components in Graph), then started running DFS on every node except S, forwardly(means when in the edges direction) and then took a step backwards(means run the loop to iterate over all the node which is pointing towards current node, for, eg, if 2 is current node and there is an edge 4->2, then I went back to 4.) and obviously marked the nodes visited. 3. then counted all the connected components.

here is my link: http://mirror.codeforces.com/contest/999/submission/39517716

Actually, my idea was simply to have the no of connected components fo graph. can someone please point out the mistake??

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

Since the system testing is done and my solution for E passed the tests,though i still don't know if its correct.

My solution:Find all the cities not reachable from capital and add a directed edge from capital to it.Now for all newly added edges just remove that edge and check if its possible to reach all cities from capital.If yes, then just remove that edge and continue checking for other edges,else add that edge back and continue checking.

I don't know how to prove that this gives the optimal answer.Can someone prove it or give some counter test for this?

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

    We know that an optimal solution is given by the following algorithm: for every SCC with in-degree zero, add an edge from the capital to some arbitrary node from that SCC.

    It is obvious that the edges your solution provides includes a set of edges that can be generated by the algorithm above (in other words, your solution does add an edge from the capital to every SCC with in-degree zero).

    What's left to prove is that your solution does not add any extra edges. Let's suppose via reductio ad absurdum that such an edge is added. Since it is an "extra" edge, it can fall into one of the following two categories:

    1) An edge from the capital to some SCC with non-zero in-degree. 2) An edge from the capital to some SCC where such an edge was already added.

    For case 1, that SCC is still reachable without this edge, so by definition your algorithm will have removed it, therefore it is impossible to have this kind of edge in the end.

    For case 2, since an edge was already added to this SCC, it means that its in-degree is now non-zero, therefore it can be reduced to case 1.

    We can conclude that your algorithm can not produce any extra edges, therefore your solution is optimal.

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

What is the solution of problem D????

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

    For every a[i] (if number of a[i]%m is greater than n/m) find nearest x (0<=x<m) which is greater a[i]%m and number of x in array a[] is less than n/m and increment a[i] by (x-a[i]%m)

    check my solution for more details

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

I got WA test 8 problem D, I used set and binary search but I still don't know what is going wrong? Here is my code

EDIT: Oops, fixed it!.

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

editorial?