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

Всем привет!

Совсем недавно ВКонтакте и Codeforces провели Финал VK Cup 2018 (поздравляем победителей!), а теперь вас ждут рейтинговые раунды по мотивам прошедшего мероприятия.

17 августа, 17.08.2018 17:35 (Московское время), состоится общий рейтинговый раунд Codeforces Round #504. Некоторые задачи будет совпадать с некоторыми задачами Финала VK Cup 2018, а awoo и vovuh подготовили еще несколько задач для проведения полноценного раунда.

Задачи этого раунда предлагали, готовили и тестировали: MikeMirzayanov, awoo, vovuh, Errichto, Lewin, Endagorion, Um_nik, YakutovDmitriy, budalnik, izban, Belonogov, scanhex, 300iq, qoo2p5, Livace.

Спасибо компании ВКонтакте — в этом раунде также будут разыграны призы! А именно, участникам, занявшим первые 30 мест этого раунда и раунда #505, также частично основанного на задачах Финала VK Cup 2018, будут засчитаны очки GP30.

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

Лучшие 10 получат фирменного плюшевого персика!

Нет никаких ограничений на страну или язык для получения приза. Требования участия в чемпионате тоже нет, приз может выиграть любой участник раунда.

Удачи!

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

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

maximum time for both rounds from the beginning of the round to the last submission that passed the pretests as tie-break

What if the said submission doesn't pass the system test? If it would be counted, it may cost you the price compared to the case where you don't make that submission.

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

3 контеста подряд за 3 три дня. Круто!

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

Пятьсот пять тоже будет общим?

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

Finally, 3 consecutive rated rounds!!!

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

Gateway Timeout Round

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

So basically combined contest with prizes. Nice

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

How many tasks will there be?

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

Participate in the CF round with my GIRLFRIEND-Coding( It is impossible for me to have a girlfriend.....:( )!

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

will it be 20% div2 + 80% div1??thriller one ....

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

You have to compete in all rounds. Not one, because you are a skillful contestant and you eat a garron of the big flute. You are in a state of temporal madness. You compete in all rounds, you solve all the problems, you hack all contestants in rooms, do I explain myself? You are inhackable brother. In 10 contests you are red.

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

Hope CF wont fall again in the middle of the contest)

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

Hope the pretest will be stronger. I got a failed system test last time.

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

I pray for the codeforces hardware.

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

But Is It Contributed?

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

Shall we need to use different languages to solve different problems?

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

Are the questions in English or Russian? Thanks for the reply.

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

perfect weekend, three consecutive rounds.

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

Wish it won't be a Gateway Timeout Round. Good Luck & High Rating!

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

How many tasks will be?

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

I have a strange felling I will do great today :D

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

Scoring?

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

Let's start, good luck to everone and high rating. :D

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

Hackforces again.... Please, the huge difficulty increases are resulting in hackforces, try and prevent that, too easy A B C D then a E-bomb

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

    How to solve D?

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

      The key observation was that you cannot have an interval of large numbers split by an interval of smaller numbers, i.e, something of the form "...8778..." is not possible. You can use a segment tree to check whether this is violated and then also check whether the largest value is present (as no other value can mask it) and take care of the zeroes (by extending the values from either side).

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

    Numbers of ACs to E is basically one third of ACs to D. I wouldn't call that big jump in difficulty.

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

    I don't think E was very hard for a div1C difficulty problem.

    It even had 2 times higher query limit than it needed.

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

      Interesting...i did get AC but my approach uses almost all the queries in worst case(no wonder am just blue)...How do you do that in half the query limit?

      Edit : Now when i think about it, i realized that yeah...half of my queries are actually utter useless! lol...

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

Hacking process or the compilers have the big problem with RE. I wrote two tests on which the programs had had to get RE, but they'd got OK. That's really strange... :(

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

    Compilers used in local machines and Codeforces servers might not be the same. So, next time, perhaps you should consider testing something through "Custom invocation" first.

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

    In C++ programming mistakes won't necessarily behave like you expect them to. Entering undefined behavior means anything can happen, the program may crash, print an incorrect answer or even appear to "work".

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

i tried this hack attempt to a solution that gives "no" while it should be "yes" to problem A

2 3

a*

asd

why it failed ?

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

    Which one failed? The hack, or the generator/validator/checker?

    If it was the hack, show the submission you intended to hack, so we can have a brief overview.

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

      my hack failed

      I can't open the submission now but the username is ATS

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

        You should see more about the substr function here.

        As it said, exception is thrown only when pos is greater than the string' size, so it'd be not the case.

        Furthermore, the "inner" condition (S.substr(p + 1, N - 1 - p) == T.substr(M - (N - 1 - p), N - 1 - p)) was correct: two strings being compared were both empty strings (you can check the code yourself, or maybe run it through Custom invocation).

        P/s: ATS' solution for reference: Solution 41688303

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

Please say F can be done with HLD with range updates and point query...
If so, any cute way to get rid of HLD?

Also E needs just 2*n-2 queries right??

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

    My solution for E also only need 2n - 2 query. The 4n query limit is probably to distract the contestant.

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

      How to do it?

      I saw 4*n and started thinking that I have to break the square into 4 squares and then do something?

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

        If the problem has no condition that two cells in query must have mahhatan distance at least n - 1, from cell (x, y) one can try to go down and ask if there is a path from there to (n, n) (make a query with (x + 1, y) and (n, n)). If yes, go to cell (x + 1, y), otherwise go to cell (x, y + 1).

        With the distance condition, split the process into two part: find a way to go from (1, 1) to some cell (x1, y1) in the sub-diagonal of the matrix, and find a way to go from that cell to (n, n). To do the later one, find a path from (n, n) to some cell (x2, y2) by asking the query with cell (1, 1), and then reverse the path.

        If one prioritize going down in the first part, and prioritize going left in the second part, it can be proved that (x1, y1) will coincide with (x2, y2), thus the answer is found.

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

          can you give a proof or an intuition as to why they would coincide

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

            I think the best intuition for this one is: if you go from (1, 1) to (n, n) prioritize going down, and go from (n, n) to (1, 1) prioritize going left, these two path are the same. Otherwise, if the second path take some route below the first one, since the first one prioritize going down, it would have taken that route as well.

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

            Think of it as lexicographicaly smallest path, where 'D' comes before 'R'. Trying to greedily put as many 'D'-s as possible at the begining is the same as trying to put as many 'R'-s at the end as possible(or 'L' if you reverse the direction).

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

      With 4n you can be less efficient when finding the next cell to go to though (like trying both right and down although trying only one of them is enough). But yeah, this is probably to make the solution more obscure. xD

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

    Yeah, my solution works in 2*n — 2 queries too

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

      Technically, each query gives you a single instruction. So you don't need to make the last query -- 2n - 3 suffices.

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

    I used simple set for F and I would probably get TLE. I used 2*n-2 queries for E too.

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

      Actually set passes, but it's pretty tight (~2.7s / 3s): 41729054 41726211

      This is probably the same way you did it, but here's a quick explanation anyways: you store in a set pairs {cost of edge, index of edge} for all edges, such that exactly one of its endpoints is in the subtree you're currently handling. Then the maximum value you can put for the edge going up from the subtree is the minimum value for any such edge. To maintain this, keep the aforementioned set, and merge them using the standard smaller-into-larger strategy, except that if you would insert a pair that already exists, delete it instead (both of that edge's endpoints are in the current subtree).

      kllp told me this strategy after the contest. (fun story: During the contest he got memory limit exceeded because his arrays were of size 5e6, not 5e5. When he fixed that he got AC :Dd)

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

        can you please explain the logic behind this part only "such that exactly one of its endpoints is in the subtree you're currently handling"?

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

    In F, one can use path compression. 41719592

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

    i didn't use hld but you can i guess, i changed updates to — minimize edges between a node x and an ancestor y of x with value val. I kept priority queue for each node, then added smaller queue to bigger one in dfs when traversing the tree. So i found the value of each edge offline.

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

    I think I have a cute way to get rid of HLD!

    We have some data of the type "All the edges in the path from u to v have to be at most x", and we want to find the upper bound for each edge. We can assume u is always an ancestor of v.

    Build array bound[MAXN][LOG(MAXN)], which means the edges in the path from v and it's 2b-th parent must be at least bound[v][b]. And also we define par[v][b] as 2b-th parent of v. Then we can easily decompose paths to blocks that exist in bound array. And after all, we do the following:

    for(int b = B - 1; b >= 1; b--)
    	for(int i = 0; i < n; i++)
    	{
    		int x = bound[i][b];
    		bound[i][b - 1] = min(bound[i][b - 1], x);
    		bound[par[i][b - 1]][b - 1] = min(x, bound[par[i][b - 1]][b - 1]);
    	}
    

    and bound[v][0] is the upper bound for the edge between v and it's parent.

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

    A way to get rid of HLD is to use union-find set.

    Consider this process: for each i, mark all edges in the path between fai and fbi with value fwi on MST, if an edge has been marked, then skip. Because each edge will be marked at most once, we can optimize the complexity of finding next edge which hasn't been marked.

    Use a union-find set to maintain all nodes, at the beginning all sets contain only one node. If we mark an edge (pi, i) (pi is the father of i on MST), merge i's set into pi's set. If we do this, at any time the representative element of i's set is a node j, while edge (pj, j) is the first edge from i to the root which hasn't been marked.

    While marking all edges in the path between fai and fbi, let u = fai, v = fbi. Each step, let u, v be the representative element of its set, select the deeper node, find the first edge e using union-find set, and marked e with value fwi, until u = v.

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

Does anyone have any idea about what the grid was for pretest 6 in problem E?

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

Does anyone have any idea about how the grid was for pretest 6 in problem E?

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

    I'm not sure because I didn't fail on that test but might it just be an empty grid? (of any size, probably >2) There's an edge case where if you don't change your preferred move on the second half then the paths might not line up.

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

Ohhh, it is not hackforces, it is F***forces

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

How to solve E?

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

Problem D :

For input : 3 5 0 0 0

Output : YES 1 1 1

why is this wrong ?

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

Should we (somehow, probably with some dp) calculate cut instead of flow (in G)?

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

    Write Blogewoosh #3 about it

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

    Or maybe Dilworth things?

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

    I replace your dinic algorithm with HLPP. It's more than 100 times faster now.

    And it can finish in about 8 seconds on my own laptop. You dinic code is still running now. However, it can't finish in 10 seconds on the custom test.

    Maybe we can squeeze it into the time limit by a faster flow algorithm/implementation or reducing the number of edges.

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

Whew. Boys and girls, my second CF round done on mobile internet. I mean dial-up connection through Ubuntu Network Manager, with help in detecting the phone as a modem from ppp utilities; transfer speed a few kilobytes per second. From a train to boot. I didn't know the meaning of stress and overload with tasks to check until now — the connection can randomly drop, the only moderately fast way of competing is through lynx so I have to switch between terminals, all my browser tabs are terminal tabs, if lynx hangs then I have to log in again, I have to send files from the same directory where I open lynx.... I'm surprised I was able to write this comment at all, JS doesn't load very fast (if at all) and images are even worse.

The round on Sunday will be the same, except not from a train, but with far worse connection. I'm masochistically looking forward to it.

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

From now, I will read first all tasks and see is something Interactive — IF (interactive) skipRound();

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

    This sounds ridiculous. What this problem has done to you so that it activated so much hatred in you? It was cute and simple.

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

      No, I do not hate this concrete task. Round was quite nice.

      I do not like Interactive tasks in global — I think they are much more guessing and lucky than all other types of problems.

      It is my opinion and I believe I won't change it soon.

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

        "I do not like Interactive tasks in global — I think they are much more guessing and lucky than all other types of problems." — that part about guessing/luckiness is just BS. I guess this is just your unreasonable prejudice probably resulting from some fails on interactive tasks.

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

          I won't say it is not my prejudice — but still I do not like them :P

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

            I dont like output only problems too, cause I never actually solved one :).

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

        "I do not like Interactive tasks in global — I think they are much more guessing and lucky than all other types of problems."

        You haven't encountered any output-only problem in your life, right?

        I think that guessing is actually an important part in solving problem. That's how you gain the idea and observation that are required to solve the problems. Experience is a kind of shortcut that allow you to make the observation faster.

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

    Then why did you create interactive problem, if you hate them.
    https://www.codechef.com/AUG18A/problems/INMAT

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

      I knew someone will ask it :D

      But I must disappointed you, both tasks used on the contests are not my tasks. They were on National Selection for IOI. As I am part of committee and was participating in preparation of the tasks I could take testcases and official solutions(I added some other testcases for this one too).

      Normally people from Codechef knew that is not initially mine, we knew that may be some problems if anyone had seen it before, but I think everything was great during contest and you all got 2 new tasks.

      Today Cook-off will have all my tasks and they are new for everyone I hope :)

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

Really hard to understand prob C. "Subsequence is a sequence that can be derived from another sequence by deleting some elements without changing the order of the remaining elements." What is elements,, order,, English is too hard....

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

    Subsequence is a string that can be obtained after deleting some symbols from original string

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

G looks like problem C from the last World Finals. I guess it has a similar solution with merging sets or treaps.

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

F*** your pretests

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

is this the hardest div2A in the history of codeforces

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

any idea about pretest 7 for problem D ?

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

    Might be because of including 0's in range minimum.

    Try this: 8 4 0 1 0 2 4 0 2 3

    possible answer: YES 1 1 1 2 4 4 2 3

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

    I had problems with test 7 too, but this test helped me.

    3 3

    0 1 3

    YES

    1 1 3 or 2 1 3

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

Weak pretests = Never ending system testing !!

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

Can anyone see something wrong in here?

http://codeforces.com/contest/1023/submission/41722815

I noticed that the second lower_bound should be changed to upper_bound, but didnt have the time to submit it.....

Is it AC if I change to upper bound?

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

In E, as long as the distance from my current cell to the destination is at least n, then using one query I can know to which cell I should move such that it is allowed and it can reach the destination.

But when the distance from the current cell to the destination is n-1 or less (so the distance from the next cell to the destination is n-2 or less), what strategy should be followed then?

EDIT: Never mind. The answer to my question (which doesn't have to query such distances less than n-1) is here http://codeforces.com/blog/entry/61254?#comment-451801

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

How to solve C?

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

    For each '(' find corresponding ')'. Delete these pairs from the string while its length is greater than k

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

      Damn that's a simple solution. Thanks!

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

      What does it mean "corresponding"? I was found pairs "()" on the beginning and on the end of string. If I can't find, I delete '(' from the beginning and ')' from the end. Can I claim, that I find corresponding chars? Or maybe, I must find nearest ')'? MySol

      Sorry for poor english.

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

        Make an empty stack. For each character in string, if it is '(' then put it on the stack, else remove the top '(' from the stack, and this ')' becomes corresponding to removed '('.

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

How to solve A?

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

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

Hey noobs , how can you fail A? i can't understand you, noobs. it is rather easy task but you failed it. noobs.

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

Can someone please explain how to solve D ?

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

    if there are three indices i < j < k such that ai = ak and ai > aj and aj > 0 then the answer is NO, it can be checked with segment tree. if there is no q in array and no 0 in array, then the answer is NO. otherwise the answer is YES. if there is no q in array and there is any zero in array, make it equal to q. for each zero , make it equal to any neighbour nonzero element.

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

      That is too complicated. Let me introduce an easy one.

      Iterate over a skipping 0's. There should be a increasing prefix, a sequence S full of maximum value and a decreasing suffix. Or a is invalid.

      Consider a but not to skip 0's. If maximum value is less than q, try to find a 0 surrounded by the elements in S and replace it with q. Or a is invalid. (Because q must appear in a according to the description.)

      Replace 0's with previous element in a iteratively (or replace it with 1 if there is no previous element).

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

      I thought the exact same solution but couldn't implement. Instead of using Segment Tree I was stuck on using Java TreeSet. Can you explain how segment tree would help here?

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

        for each i from 1 to q if there is any i in array, I know when its first and last occurence in array. If the minimal element (except for zeroes) in range between its first and last occurence is less than i, then the answer is NO. Minimal element on range can be found using segment tree.

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

      For the first check, I didn't use segment tree, I used an array of vectors vector <int> v[N] that save in each vector i the indeces where the number i appears in the given array, and as it is known, each vector will be sorted automatically. Now, for each i where 1 <= i < n I will check for each index j where 0 <= j < v[i].size() if v[nxt][0] <= v[i][j] <= v[nxt][lst] where nxt is the next number after i that appear at least once in the given array, and lst is the last index in the vector of nxt.

      And if that condition is true then the answer is NO.

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

        your solution says "YES" for test
        4 3
        2 3 1 3
        Next time when you want to share your solution, please check if it is not wrong.

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

          I commented after I had got AC, but you are right that this test hacks my solution, so it is wrong. Sorry about that. MikeMirzayanov, please, check this situation.

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

      Applied the same, didn't know where I went wrong.

      EDIT: Apparently I built segment tree without handling the case when the length of range is 1 and element is 0. It worked after that :(

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

      Why is it optimal to always set 0 to q?

      For example what if you have: (a < q) 0 a a a 0 and wouldn't [q a a a q] be invalid and we should set it to [q a a a a] instead?

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

    First, there are a few nasty cases related to the last query: is there any q in the input array, or else is there at least one zero to put it there...

    After that, I had another approach, somewhat technical yet trivial on the other hand. For each query from 1 to q, remember the first and the last index for this query. (For query 1, let's say it covers the whole segment, just to get rid of zeroes.) Now process all queries in order; to do it in , we can just use a segment tree. Alternatively, a scanline-like approach would also work, treating first and last indices as "query started" and "query ended" events, and processing them from left to right. Finally, check that what we got corresponds to the non-zero entries of the given array.

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

      i thought about "segtree","priorityque",etc at the first glance,but the time limit 1 sec roared at me,"_stay away kid_"...

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

    Consider the construction of a as follows: First, place 1's from the start to the end. Then, place the smallest possible segments for each number (so, for query q, go from the first instance of q to the last one). If there are no instances of q, place it where you will eventually place the last query (so, don't worry about it). If the last query is empty according to above setup, put it on a 1. If the last query is empty and there are no 1's, then the situation is impossible.

    Of course, this is O(NQ). We want to do it a bit faster, so let's store the ends of each segment in some array. Then, go from the first position of a to the end, while maintaining a priority queue of the segments you are currently looking at. For each number in a, add it to the queue. Check if that number is the end of a segment, if so, remove it from the queue. If at any point the highest number in the segments is greater than the number in a, then it is impossible. When you come to a zero, just put whatever number is in the queue currently or 1 if there are none. But, if it is the last zero and there is no segment with the last queue value, then place the last queue number instead.

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

    I did D with just a priority queue by constructing what the array has to look like after the queries (41700329).

    You find the leftmost appearance for every number, and the rightmost appearance for every number. Then, with a priority_queue, you go left to right, doing the following:

    1. If the value at the current index is 0, continue
    2. Otherwise, if it is the current indexes values leftmost appearance, add it into the priority queue
    3. While the rightmost appearance of the topmost element of the priority queue is less than the current index, pop it.
    4. If the priority queue is not empty, set the value at the current index in your construction to the largest value in the priority queue.

    This achieves the same as having query i fill between leftmost appearance of i to rightmost appearance of i.

    After this, if the number q (from the last query) doesn't appear, put it at some zero. If q doesn't appear, and no zeroes exist, fail. This is since all intervals have nonzero length.

    Then check that at all indexes that don't contain zeroes in the original array, your construction matches the original array. If it doesn't, fail.

    Then fill all zeroes with arbitrary adjacent elements, and output the construction.

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

Problem C, D and E today are great.

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

In problemE ,I ask a wrong query. But why return me a TLE and MLE rather than WA or invalid input? As I know, every round in codeforces didn't return TLE and MLE in the past time. I'm very angry now, it wastes me too much time.

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

    Answer "BAD" instead of "YES" or "NO" means that you made an invalid query. Exit immediately after receiving "BAD" and you will see Wrong answer verdict. Otherwise you can get an arbitrary verdict because your solution will continue to read from a closed stream.

    Maybe this?

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

    Don't be angry, be careful.

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

    "Answer "BAD" instead of "YES" or "NO" means that you made an invalid query. Exit immediately after receiving "BAD" and you will see Wrong answer verdict. Otherwise you can get an arbitrary verdict because your solution will continue to read from a closed stream." EDIT: I got ninja'd.

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

what a great contest!

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

Kudos to problemsetters :D

The problem set was balanced with fun tasks(specially D)

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

I think there is either a problem in the solution of A or the test cases are very weak.

For 7 7

abc*abc

abc!abc

the answer should be NO.

But codes that give YES are also getting accepted. I think the constraint that * can only be replaced by lowercase Latin letters has being ignored.

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

    the string t consists only of lowercase Latin letters

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

    The third line contains string t of length m, which consists only of lowercase Latin letters.

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

    ...the string t consists of only lowercase Latin letters...

    The test is invalid.

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

    Problem the statement, "The third line contains string t of length m, which consists only of lowercase Latin letters."

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

Thank you for the contest!

Problem E is very nice.

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

How to view on which test case my solution was hacked?

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

Freaking A again!

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

my E will fail. (

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

Editorials please!

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

Вопрос по задаче D. Как массив с 0 может быть вообще получен, ведь элементы могут меняться на значения от 1 до q?

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

Really weak pretests :(

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

tc 87 for problem A ??

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

Deadly problem A :D

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

What were the problems that were taken from VK Cup finals 2018?

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

F was easier than A!

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

What is going on with my solution for problem E? I submit a query and, even though I never receive BAD as an answer, I do not receive an answer sometimes on test case 18 (see diagnostics). Does the interactive program print extra characters or whitespace?

Edit: Never mind, the diagnostics are just bogus.

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

when will be the solutions available?

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

How to solve problem B, please explain the logic of math behind it.

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

    Imagine you have n=10, in how many ways can you make the sum 10?

    1+9 = 2+8 = 3+7 = 4+6 = 10 (4 pairs)

    Do you see the pattern?

    Now, why is this surely the answer? Well, because it is stated that the pairs (a,b) and (b,a) are the same and because we have each number only once. Now, there are 3 cases to consider: 1. n>=k 2. k-n>n and 3. k-n <= n

    Lets think about the first one together, then you can think about the other two:

    n>=k means that we have numbers that are bigger than the sum k. You can't use such numbers because, well, they are already bigger than k. What is the biggest number you can use then? Its k-1, because you can pair it with 1 to sum k. So just assume n=k-1 and count the pairs like I did in the first example. You will end up with (k-1)/2 pairs.

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

Can anyone explain why this code gives TLE for Problem C . Link for the solution http://codeforces.com/contest/1023/submission/41695850

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

CONFUSED BETWEEN PYPY2 AND PYTHON2

I have been using pypy2 for over a month and I shifted to pypy2 from python2 just because pypy2 is faster than python2, but today when I tried question C using pypy2, it gave TLE and when I submitted the same code with python2, it worked fine. Pypy2 solution: 41730885 -- verdict=TLE. Python2 solution: 41730897 -- verdict=Accepted Can someone tell me when to use python2 instead of pypy2 ?????? Thanks

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

Benq kept his promise to become a LGM :)

Congratulations !!

My mission is nearly done unless you win the IOI!

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

Since a lot of people seems to be using max segtree for D (my in contest idea was lazy max segtree but it would go against my morals to submit something like that), I thought I'd elaborate on the sweep/set technique.

Basically you store O(n) amount of start, and end events.

Here is how you calculate them:

Spoiler

Then you can use this information to calculate, for a point, which values have hit their leftmost point but not yet their rightmost point. We call the maximum of these values "val", in my code I called it "maxcover".

This can be stored in set , or priority_queue (heap), because you only care about the maximum. (I think mango_lassi did this)

Code

Then using this information you can optimally assign any 0 values to val[i] described above.

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

C looked easier than A. Link for Editorial of C

I have also tried to explain A's approach. Link for Editorial of A

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

My problem F got TLE because I didn't remove the "cerr" in my code. So my code printed 5e5 integers to stderr...... (It is interesting that "cerr" in my code was not executed for samples) I know this is a hilarious mistake and it is my own fault... Well, I expected this would get "WA", but I got "Pretest passed" instead... QAQ

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

    Stderr is ignored when checking correctness, cerr can cause TLE only, it can't cause WA. In order to not worry about time it takes I suggest you do the following:

    1) Compile with -DLOCAL flag locally

    2) Add
    #ifndef LOCAL
    #define cerr if(0)cout
    #endif
    to your templates.

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

Problem C was easier than A...

Just remove n-k characters from the string. When you remove '(' from the string, remove ')' from it too. Where index of '(' is less than ')'.

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

Weak testcases in D

My solution gives NO for

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

When will the editorial be published? I'm so eager to see how problem G can be solved. (Because nobody has solved it yet :-)

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

How to solve Problem E ?

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

In D shouldn't be the output of the following testcase YES but it's showing 'NO'. 3 3
2 1 3 Weak test cases.solution

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

Can anyone explain what is meant by the error or what does it mean in the following E problems solution?

Solution link is

Your text to link here...

Thanks in advance:)

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

Where's the editorial?

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

While I was looking through the top Accepted solutions for 1023D I found out that someone got his solution accepted on the following test case:

5 4

4 3 3 3 4

Answer his code produces is 'YES'.

According to me the answer should be 'NO'.

Can someone explain to me how this solution got accepted?

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

still waiting for editorail...

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

Can someone explain what I must to do in C?

Sorry for poor english.

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

    Given a regular bracket sequence with size n, you have to find a subsequence of it with the size k, which is also a regular bracket sequence (answer guaranteed to exist).

    A subsequence of a string is created by removing some (maybe none) characters of that string, and keeping the remaining characters by the original order (more details on that below).

    A bracket sequence is a sequence/string consisting only of ( or ).

    We can define the term "regular bracket sequence" recursively, like:

    • "" (empty string) is a regular bracket sequence (RBS).

    • If R is a RBS, then "(R)" (R being inside a pair of parentheses) or "R()" or "()R" (the string "()" stands right before/after R) is also a RBS.

    Take the first sample test for example.

    With the string ()(()), there are many subsequences with the length of 4, like ()((, ()(), ())), (((), (()), )((), )()).

    Among them, only a few are regular bracket sequences, like (()) or ()().

    You can choose any sequence among these — they are all valid answers.

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

    Maintain a stack and traverse the string. If you encounter '(', push onto stack. If you encounter ')', pop from stack. This removes 2 elements from the final string. You need to pop (n — k) / 2 times. Print the contents of the stack.

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

Can anyone suggest what I am missing out in my submission for question D. 41737987

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

Can anybody tell the link of editorials for this contest?

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

Where is editorial?

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

Can someone please explain the stack or priority_queue method for solving D. I was able to solve it using Segment Trees but even after reading comments, I couldn't understand how to do it using stack or priority_queue.

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

Why does 4*n number of queries seem inefficient in problem E ?

https://codeforces.com/contest/1023/submission/41731400

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

    Try this:

    9
    .........
    ####.....
    ...#.....
    ...#.....
    .........
    ...#.....
    ...#.....
    ...#.....
    ...#.....
    

    Your program correctly goes to r=5, c=5 and then asks ? 5 4 9 9 which is YES (? 1 1 5 4 would lead to NO if that query was allowed). Your program then stumbles around in that trap, querying some fields repeatedly, using up more than 4*9 = 36 queries...

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

Can someone explain a solution with HLD for problem F?

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

    I can explain the idea.

    We can obtain a minimum spanning tree T of the graph by setting the weights on our edges to 0 and running any MST algorithm, since we know that we will eventually set the weights on our edges such that they will all be included in the MST.

    The main observation is that given any edge e = (u, v, w), we know that the path from u to v in the minimum spanning tree T cannot contain any edge e' with weight w' > w. Otherwise, T - e + e' would be a lower cost MST.

    We can use HLD to compile all such constraints imposed by our competitor's edges and determine the maximum possible weight for each edge in the MST.

    However, I am not sure if it's an intended solution. I was barely able to squeeze my HLD implementation under the 3s time limit. To do it I had to make use of the fact that we update arbitrary paths but only query single edges, so we can use a segment tree without lazy propagation: http://codeforces.com/contest/1023/submission/41885123

    Interestingly, you could modify it further using the fact that all of the queries come after all of the updates; it is not even necessary to use a segment tree at all.

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

can someone please provide a test case where this solution will fail http://codeforces.com/contest/1023/submission/41825727

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

Where can I find the editorial of this round?

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

Где разбор? Если не сложно можете скинуть ссылку на разбор

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

editorial ???

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

For problem D of the contest following test case: 4 4 4 2 1 3 Some have answer: YES 4 2 1 3 But some solution printing "NO" instead are also accepted. Please include this test case.