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

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

Привет! Codeforces Round 581 (Div. 2) начнётся во 20.08.2019 17:35 (Московское время). Раунд будет рейтинговым для всех участников с рейтингом не больше 2099.

Задачи для вас придумали и подготовили rotavirus, rotavirus и rotavirus. Спасибо arsijo за координацию раунда. Спасибо тестерам за тестинг и советы: Ari, antontrygubO_o, awoo, mbrc, tfg, Noam527, stefdasca, Adhami, Rahul, Bakry, farmersrice, BencilSharpeniro, average_frog_enjoyer, dalex, Zain, gamegame.

У вас будет 5 задач и 2 часа, чтобы их решить. Разбалловка будет опубликована позднее 500-750-1250-(1500+750)-2500.

Раунд закончен! поздравляем победителей:
1. 79brue
2. sinus_070
3. baluteshih
4. weishenme
5. shahaliali1382

Разбор.

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

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

you forgot rotavirus

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

Yout better say thanks to Mike MikeMirzayanov Mirzayanov for the amazing platforms Codeforces и Polygon if you want your round to be rated)))

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

All the best for your 1st contest :)

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

Bencil Sharpeniro orz

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

That army of 15 testers...

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

если мне не понравятся задачи, я тебе где-нибудь на сборах пальцы сломаю

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

hello sorry_marymarine,

i am predicting this to be great contest,, because i know for facts that BencilSharpeniro is a very good problem testing man,

last time he giving me the problems, i felt like it was a good problems, so i having the faith in this contest and qualities of this contest,,,..,,..

good luck and high rating mr master, rajeshwar~~

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

Good luck and high rating to all :)

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

I am so psyched.

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

Desire for becoming Candidate Master tonight!! :)

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

Thank you, "spsk spsk"

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

there is a problem with account link ? "The problems were invented and prepared for you by danilz1806, baumanec " both link to ur account

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

Please fix long testing queue for pretests during contests. It's really annoying to wait for results during contest . Thanks

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

Questions made are excellent but I would suggest to improve the testing queues during submissions. I can understand it is a complex job to do given that many submissions are made in a single instant but if this fault is cleared, then people will be more motivated to take part in such thrilling contests. :)

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

I don't know how to tell you, because I'm only a pupil.

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

I will become expert after the contest :))

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

Is it rated guys??

Coz, I know Nothing.

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

With such army of tester, I expect super strong pretest.

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

Hoping to get the last point to be a Candidate Master!! :)

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

About 20 people trying to make a contest for us. How lucky we are. :D

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

Разбалловка будет?

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

15 peoples are tester for contest. <3 I thinks this round don't need hacking. I'm afraid =))))))

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

    I just solved some problems and gave some advice to make statements better, I didn't try to submit wrong or tricky solutions. Most of other testers too, I think.

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

For me you are Mr Master.

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

clashes with Mineski VS Na'Vi :(

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

why I can't get registered

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

Where is the link to ask a question? I think I rember that on every problem page there was such a link, but can not find it. :/ Is it gone? (Maybe caused by to much stupid questions ;)

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

BINARYFORCES!!!

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

The word "subsequnce" appears 7 times in the problem statement of D1 and D2

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

maybe I got it. my bad

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

Uh, why does solving D2 not auto solve D1? RIP penalty. ;_;

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

What is test case 13 for C?

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

My score has plunged to 532

Calc Pro XD

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

rotavirus, а к чему подзадачи в D? Я вообще не особо понимаю зачем делать подзадачи на Codeforces, но конкретно в этом случае меня терзают сомнения что подзадача была добавлена только ради того чтобы в раунде было больше 5 задач.

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

I hope this is the first and last time i ever see 998244853 in a contest.

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

Does anyone know why I TLE on pretest 13 of prob. C. I'm pretty sure my algorithm runs in O(n^3 + m) worst case which should fit in the bounds.

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

Nice task E, thanks)

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

How to solve C ??

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

    I tried greedy, but I got WA on 5th. Never mind, I had a bug. It is a greed algorithm. O(n^3) (Floyd–Warshall) + O(m) linear search get we erase b in this scenario (a — b — c). If dist[a][c] == dist[a][b] + dist[b][c] then we can erase b, otherwise he stays in array.

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

      I was trying to figure out the condition which can be used to remove element from p(i). But found nothing. :(

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

        Condition to erase p[i] :

        There is a j and a k such that j<i<k and dist[p[j]][p[k]]=k-j . Dist[x][y] is the shortest path in the graph betwen x and y

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

    You can apply Greedy algorithm. For each triplet, ( left, current, right ), if you can go from left --> current and from current --> right ,but you can't directly go from left to right, then we can remove current. This ensures that the shortest path from left to right includes current. Hence, it retains the original sequence.

    You can use a stack to process every triplet.

    The time complexity is O(m + n*n).

    Code

    Edit --> It can't be solved without using Floyd Warshall

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

    You can make a Floyd-Warshall to calculate the APSP,then you just need to search the sequence (starting with the first number) the number that is farther away and that the difference in positions is the minimum path between those two, then you keep it and go to that one and repeat it until you reach the end,O(N*M)

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

I submited D1 without any testing or even compiling in last 30s an it passed, tests are probablu awful for this one.

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

Bonus for E. Solve it in $$$O(n)$$$

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

    I think problem E would be much easier if the constraints are set to fit $$$O(n)$$$, e.g. $$$n \leq 100000$$$, because one need not consider an $$$O(n^2)$$$ approach instead, which could simplify thinking.

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

Upd: Ignore, got it.
In div2E, did we have to use the fact that number of sequences whose maximal prefix sum is k is equal to product of catalan numbers($$$C_{x_{i}}$$$) such that sum of $$$x_{i}$$$ is n-k)?

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

E can be solved in O(n+m) 59161848

to solve this you need to calculate C(n, r) in O(n) preprocess and O(1) query

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

Maybe I should call this round...

UnsuccessfulSubmissionForces.

Problem A and C are really tricky.

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

Anybody want to explain D? The last example does not make sense to me.

0111001100111011101000

Answer should start with 000100... but the example says 001100...

Why? Which condition would not be satisfied if the answer starts with 000100...?

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

    Any subsequences, not only consecutive.

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

    Consider subsequence in [3,6]. The longest non-decreasing in input is 2, but your example is 3.

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

    In 001100 the longest non-decreasing subsequence is 4 In 000100 the longest non-decreasing subsequence is 5

    But in input string the longest non-decreasing subsequence s[1:6] = 4, not 5!

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

    You're considering sub-string(s) . For 't' we have to consider sub-sequences.

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

If you know Catalan number's formula's proof, you could solve E with complexity O(n)

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

Nice problem D

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

I am a new to hacking. Is hacking allowed only during the contest?

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

    In normal rounds yes, but in the extended ICPC rules you get 12 hours of open hacking after the contest ended.

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

Feels really great when you finish debugging C 40s after the contest ended :(

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

What about problem C? Is it Floyd–Warshall algorithm?

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

Основная идея в задаче С такое ? Тип идем сьева направо до М по массиву b , и смотрим можно ли это вершину убрать , а убирать можно только тогда когда между вершинами которые были до этого и с вершиной который стоит после него нету ребра

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

    нет,во-первых, нужно знать путь между всеми вершинами(флойд легче всего),потом фиксируем первую вершину и смотрим расстояние от фиксированной до следующей ,и от следующей до следующей после следующей(был такой массив p : 1 9 5 4 7.Тогда смотрим расстояние от 1 до 9 и расстояние от 9 до 5).Если от 1 до 9 расстояние меньше чем расстояние от 9 до 5 то продолжаем ,иначе фиксируем 9 и кидаем ее массив, далее тоже самое (смотрим d[9][5] и d[5][4],если первое меньше то продолжаем и далее смотрим d[9][4] и d[4][7],или фиксируем 5)...

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

      Ааа , спасибо , теперь понятнее стало)

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

I don't understand problem C.

What " and p is one of the shortest paths passing through the vertexes v1, …, vk in that order." means?

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

    It means, that there is no strictly shorter path than p passing through all vertexes v1, ..., vk in that order.

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

      And i should find the shortest sequence of vertices that this path 'P' pass through?

      Whether yes or no, Could you explain more about what should the output be?

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

        Yes.

        Since $$$v$$$ is a subsequence of $$$p$$$, I will define another sequence, $$$a$$$, such that for all $$$i$$$ in range $$$[1, k]$$$ $$$p_{a_i} = v_i$$$ and $$$a$$$ is ascending.

        You should output a sequence $$$v_1, v_2, \ldots , v_k$$$ such that:

        • $$$v$$$ is of course a subsequence of $$$p$$$
        • $$$v_1 = p_1$$$, $$$v_k = p_m$$$
        • for all $$$i$$$ from $$$1$$$ to $$$k-1$$$ the length of shortest path between $$$v_i$$$ and $$$v_{i+1}$$$ is equal to $$$a_{i+1}-a_i$$$
        • there is no subsequence of length strictly lesser than $$$k$$$, for which above three conditions are all true

        For example in test

        4
        0110
        0010
        0001
        1000
        4
        1 2 3 4
        

        The proper answer is

        3
        1 2 4
        

        because:

        • it is a subsequence of $$$(1, 2, 3, 4)$$$
        • the first and the last elements of both sequences are equal
        • for all $$$i$$$ from $$$1$$$ to $$$k-1$$$ the length of shortest path between $$$v_i$$$ and $$$v_{i+1}$$$ is equal to $$$a_{i+1}-a_i$$$:
        1. shortest possible path from $$$1$$$ to $$$2$$$ has length 1
        2. shortest possible path from $$$2$$$ to $$$4$$$ has length 2
        • there is no subsequence of length $$$1$$$ or $$$2$$$ that satisfies all these three conditions
»
5 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

First competition so I have a few questions. - When do we get our rating? - How do you read the score distribution? I'd be grateful if anyone could answer.

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

    The ratings need like an hour or so, sometimes more.

    Score distribution? There is a link to "Standings".

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

Actually, the first problem was the hardest

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

who can tell me the thinking process about Pro.C,never solve the pro.c since came here

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

    And the meaning of "The main characters have been omitted to be short."

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

      That means "Let's skip the little useless story and go straight to the problem"

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

What's wrong with this solution? Problem A
1- Read the user input as a decimal value in a variable s
2- Output the round up value of log4(s)

for exemple 100000000 is 256 in base 10 and log4(256) is 4 because power(4,4) = 256
and 101 is 5 and the round up of log4(5) is 2 and so on ...

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

    With numbers up to 2^256 I think using that might be not precise enough.

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

      I think the logic is okay the problem is in my implementation I'm using C++ and I used a variable s as uint64_t so I can only store 64 bits so when the user input is more than 64 bits I got problems so I have to use a type where I can store 100 bits if someone know a type in C++ where I can store more than 100 bits please help

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

Could someone help me figure out what is wrong in my logic in question C. 59182371

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

    I mean, they don't need to be adjacent to have a shortest path that goes around the 'inter' in your code.

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

    After experimenting with various test cases, I finally came up with one that your code fails on. I hope this will help you better in understanding where you went wrong

    4
    0101
    0010
    0001
    0000
    4
    1 2 3 4

    The expected answer is of length 3 , but your code outputs a sequence of length 2.

    Hint : Suppose we have a sequence (a,b,c,d). We take a into our path. We cannot reach c from a, hence we neglect b. Now, we cannot reach d from c, hence we also neglect c. This is where you went wrong. Since we've already deleted b, we should check the condition on the triplet (a,c,d).

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

15 testers and even the basic test cases are not covered for problem C. A simple path graph of length 5 is enough to hack a guy. Why were all the basic cases not covered?

http://codeforces.me/contest/1204/submission/59167944

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

    When testing, testers mostly gave feedback on the problems, not the tests. Also, all testers who solved C did so without running into this test case.

    And just because a single case wasn't covered doesn't mean all basic cases weren't covered. A lot of edge cases were covered, for example:

    2 0100 2 1 2

    System tests and hacks are a part of Codeforces, it's really hard to avoid and check every single case.

    Please be considerate of the authors for taking the time to put the round together and writing the problems. It's a shame this happened to many participants.

    Best of luck in the future.

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

    dude, the humans' idiotism, retardness and stupidity don't have limits.

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

      I can understand people posting weird-ass solutions which could pass sometimes, but there should have been a path graph test case in there somewhere.

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

    See the glass as half full: you have the opportunity to hack someone.

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

Will you provide the table of most hacks?

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

What was the intended solution for D?

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

what is the problem with s.size() and (ll)s.size()? s.size() gives wrong answer but (ll)s.size() gives correct answer.

With (ll)s.size() https://codeforces.me/contest/1204/submission/59182674

With s.size() https://codeforces.me/contest/1204/submission/59158562

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

    s.size() returns size_t type integer, where size_t is an unsigned integral data type. So, it can't be negative.

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

    s.size() has type size_t, if say size is 1 and you subtract 2 from it, it won't go to -1, it wraps around, see this : size_t in reverse for loop

    using ll ensures proper conversion. :)

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

      I face this problem many times in codeforces only. I don't face this problem in any other sites like codechef etc.

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

Тот момент когда увлекся задачей С и забил на Д , хотя Д мог решить , а вот С не смог)

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

Why 1e8 operations doesn't fit to 2 sec in C, when 1e9 fit to 1 sec in Codeforces? Even when I make 1e7 for get WA I get TLE can anyone explain?

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

    shit I wrote

    for (int j = i - 1; j >= max(1, j - 100); j--) {
    

    instead

    for (int j = i - 1; j >= max(1, i - 100); j--) {
    

    get AC in 0.6 s

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

Test case 2 in problem C. I don't understand why not true??? May be Im wrong??? Help me. Thanks you so much <3

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

I am a newbie now. I want tips how to become a legendary grand newbie. Help is highly appreciated

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

I am confused in test case 3 of problem C. Why the solution of test case 3 in Problem C can't be 6 1 2 3 3 2 1. Even if 1 is deleted from the sequence , shortest path from 3 to 3 is of distance 2 only.

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

That's rally quite strage, that this army of testers didn't crash my solution in D2 (I did it after the end of the contest), in the worst sitation I have O(n^2), but on max systemtest my solution got only 30 ms.

Sorry, for my poor english

https://codeforces.me/contest/1204/submission/59180412

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

    dude, the humans' idiotism, retardness and stupidity don't have limits. i can't foresee which bad solutions can you invent

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

    Most people in "army of testers" (at least me) just wanted to solve the round beforehand and didn't work on wrong solutions.

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

      I thought that one of the most important thing is to try to build good maxtest. It's not quastion for you, it's a quastion for organisator of testers' work. And there are some hacks of task C with really simple tests too(n=4 and m=4)!

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

what a smooth contest!

No announcement and also fast testing.

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

every thing about this contest is really good, but the best thing is rotavirus'comments on this post lol

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

I solved problem C in O(m) without using Floyd-Warshall and without computing shortest paths. Here is my code: 59178907

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

    I also applied a similar logic. Although it cleared all the test cases (still does), but there is a big flaw in the logic. After dry running it a couple of times, I came up with this test case which fails with your code.

    4
    0100
    0010
    0001
    0000
    4
    1 2 3 4

    This is a linear chain. The answer should be of length 2. But your code produces an answer of length 3. The test cases for this question are too weak.

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

Test #4 in problem D1 Why isn't 0001000100001000101000 the answer? Maybe I didn't get the problem right, but I don't see values of l and r which can fail the test.

I've even cheched it for every [l;r] in program.

//before
    for(short int l=0;l<s.length();l++)
        for(short int r=l;r<s.length();r++){
            short int loc=1,i=l+1,max=1;
            while(i<=r){
                if(s[i]>=s[i-1]) loc++;
                else {
                    if(loc>max) max=loc;
                    loc=1;
                }
                i++;
            }
            if(loc>max) max=loc;
            before[l][r]=max;
        }

//changing the string
    short int i=0;
    while(s[i]!='\0'){
        if(s[i+1]!='0' && s[i]=='1') s[i]='0';
        i++;
    }

//after
for(short int l=0;l<s.length();l++)
        for(short int r=l;r<s.length();r++){
            short int loc=1,i=l+1,max=1;
            while(i<=r){
                if(s[i]>=s[i-1]) loc++;
                else {
                    if(loc>max) max=loc;
                    loc=1;
                }
                i++;
            }
            if(loc>max) max=loc;
            if(before[l][r]!=max) printf("\n%hi %hi",l,r);
            else printf("\nok");
        }
»
5 лет назад, # |
Rev. 2   Проголосовать: нравится +12 Проголосовать: не нравится

solution for problem D2. So fun =))

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

+262 good contest

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

Finally reached blue :)

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

Принятое решение D2 59185691 работает за квадрат на тесте вида 1010...10.

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

E can be visualised as a path counting problem in an $$$n$$$ by $$$m$$$ grid. Where going up is +1 and right is -1. And can be solved in $$$O(n+m)$$$.

Let $$$F(i)$$$ be the number of paths from $$$(0, 0)$$$ to $$$(n, m)$$$ that satisfy each point $$$(x, y)$$$ in the path satisfies $$$x - y \leq i$$$.

Answer is summation of $$$(i . (F(i)-F(i-1)))$$$ for $$$i$$$ in $$$1$$$ to $$$n$$$.

$$$F(i)$$$ can be found by counting all the bad paths for $$$i$$$ and subract it from total paths $$$(C(m+n,m))$$$. A bad path is a path where there exists atleast one vertex that is of the form $$$(y+i, y)$$$, in other words, the path meets the line $$$x-y=i$$$. It can be seen that the bad paths, given $$$i$$$ have a bijection with paths from $$$(0,0)$$$ to $$$(m+i+1, n-i-1)$$$. (If we swap the number of up and right moves from the first point of intersection with $$$x-y=i$$$). Number of bad paths is $$$C(n+m, m+i+1)$$$.

So $$$F(i)$$$ is just $$$max(C(n+m,m)-C(n+m,m+i+1), 0)$$$

Also, feels good to be on the blog for the first time :)

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

C can't be solved without using Floyd Warshall (equivalently, BFS from all vertices)

Going through the solutions of problem C, I have observed a lot of people (including me), solve the question without using Floyd Warshall and deleting vertices in a greedy manner. Although the solution passes all the system test cases, I believe it is wrong.

People have used 2 approaches for greedily deleting the vertices.

Approach 1 :: Checking every window of size 3 without modifying the array.

This approach fails for this test case.

4
0101
0010
0001
0000
4
1 2 3 4

Expected 1 3 4
Output 1 4

Approach 2 :: Checking every window of size 3 (while actually deleting elements using stack).

This approach fails for this test case. 4
0100
0010
0001
0000
4
1 2 3 4

Expected 1 4
Output 1 2 4

rotavirus Can you add these test cases to the problem ?

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

    I fail in C because my bfs counts only one way from u to v (if v has other way) Today morning I fix it and get AC. I think that my solution also greedy.

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

      As I said, BFS from each vertex is essentially the same as Floyd Warshall. The time complexity of your code is O(n*m + n*n*n). My point is that you cannot lower that O(n^3) factor to O(n^2).

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

finally expert :)

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

When you want to troll ~12k contestant with 998244853 but almost no one got tricked

Spoiler

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

    I spent 30 minutes on this module number. I have wrote the code of E for 3 times. At first I use the math formula. It's right and the complexity is $$$O(n)$$$. At last I use $$$O(n^2)$$$ dp. I won't believe the module number any more. 555...

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

      Me too.And even worse,I spent 2h on this number without finding out it.

      Perhaps I am a fool:(

      I learnt a lesson,and it taught me a lot

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

Does anynoe use modulo 998244353 on problem E like me...

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

    I think you can't pass the fifth sample if you use 998244353... XD

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

      Yes.And I thought my solution is wrong until I found it.

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

        Your previous submissions don't even have modulo hardcoded. Did you type ...353 by memory? It is one of the things you should never do on contests. If something is written in the statement, copy it from there.

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

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

I am solving the problem c in o(n3 + m) time complexity still getting a tle Here is a link to my solution , can somebody please help me https://codeforces.me/contest/1204/submission/59177220

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

Please help me with this test case. ( Problem C)

4
0110
0001
0001
0000
3
1 2 4

The answer according to accepted code is

2-> 1 4

But if you draw the graph you can see that there is another road to go from '1' to '4' which is 1--3--4.

So why the answer is

2-> 1 4.

I think it may be 3-> 1 2 4.

Help me with proper logic of this test case.

Thanks in advance

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

    Important only that way from 1 to 4 shortest (not important how many ways exist).

    I think it means that you can't restore original way from correct solution and it not necessary.

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

    To prove, that this is correct answer for this problem, suppose, that there exists a correct answer of strictly lesser length than 2 (in this case we are only considering a subsequence of length 1).

    Of course a path of length 1 is incorrect for this test case, because (from the statement) the first and the last elements of path $$$p$$$ and its subsequence $$$v$$$ must be equal, so if path of length 1 would be correct, we would have $$$1 = p_1 = v_1 = v_k = p_m = 4$$$, so there is no correct answer of length strictly lesser than 2.

    We proved that the answer's length is at least 2, so now we can prove, that $$$v = (1, 4)$$$ is a correct answer:

    • $$$v$$$ is a subsequence of $$$p$$$
    • $$$v_1 = p_1 = 1$$$, $$$v_k = p_m = 4$$$
    • the shortest path between vertexes $$$v_1 = 1$$$ and $$$v_2 = 4$$$ has length 2

    As you can see $$$v = (1,4)$$$ satisfies all needed conditions, so it is a correct answer.

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

Why problem d was two parts? I think E Should be two parts

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

The system test of Problem C is too weak

I hacked about 15 solutions after the contest!

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

    sorry for this. i am rather unexperienced problemsetter and i can't foresee all the wrong solutions to invent the countertests

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

Hello! I think that the output for the fourth input of this problem D1 has mistake.

Because the longest non decreasing subsequence of output is 13, but the input is 12. If i made a mistake help me understand.

Sorry for my poor english.

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

    both have the same length of the longest nondecreasing subsequence. please don't say "the output is wrong" 2 weeks after a contest. it was carefully prepared, tested and then a lot of participants solved that problem.

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

Your round is one of the best rounds I have participated in. Thanks a lot