By 300iq, 6 years ago, translation, In English

Hi!

August 17, Aug/17/2018 17:35 (Moscow time), there will be a rated Codeforces round #504. Some of the problems will be from VK Cup 2018 finals, and awoo and vovuh have prepared other tasks for the full round.

The problems of this round are proposed, prepared and tested by: MikeMirzayanov, awoo, vovuh, Errichto, Lewin, Endagorion, Um_nik, YakutovDmitriy, budalnik, izban, Belonogov, scanhex, 300iq, qoo2p5, Livace.

There will be prizes from VK social network in this round as well! The participants who took the first 30 places of this round and the round #505, also partially based on the tasks of VK Cup 2018 Finals, will get GP30 points.

Participants are sorted by sum of points for both rounds (if the participant did not participate in one of the rounds, the points scored for it are assumed to be equal to zero), with the maximum time for both rounds from the beginning of the round to the last submission that passed the pretests as tie-break.

The top 10 participants will receive a plush Persik!

There is no country nor language restriction, everyone can win a prize. One don't have to have participated in VK Cup to receive the prize. Exact selection algorithm will be announced before the start of the round.

Good luck!

  • Vote: I like it
  • +231
  • Vote: I do not like it

| Write comment?
»
6 years ago, # |
  Vote: I like it +42 Vote: I do not like it

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 years ago, # |
  Vote: I like it +23 Vote: I do not like it

Finally, 3 consecutive rated rounds!!!

»
6 years ago, # |
  Vote: I like it +90 Vote: I do not like it

Gateway Timeout Round

»
6 years ago, # |
  Vote: I like it +1 Vote: I do not like it

So basically combined contest with prizes. Nice

»
6 years ago, # |
  Vote: I like it +91 Vote: I do not like it

How many tasks will there be?

»
6 years ago, # |
Rev. 4   Vote: I like it -67 Vote: I do not like it

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

»
6 years ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

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

»
6 years ago, # |
  Vote: I like it +81 Vote: I do not like it

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 years ago, # |
  Vote: I like it +21 Vote: I do not like it

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

»
6 years ago, # |
  Vote: I like it -64 Vote: I do not like it

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

»
6 years ago, # |
Rev. 4   Vote: I like it +22 Vote: I do not like it

I pray for the codeforces hardware.

»
6 years ago, # |
  Vote: I like it -36 Vote: I do not like it

But Is It Contributed?

»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
6 years ago, # |
  Vote: I like it +14 Vote: I do not like it

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

»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

perfect weekend, three consecutive rounds.

»
6 years ago, # |
Rev. 2   Vote: I like it +7 Vote: I do not like it

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

»
6 years ago, # |
  Vote: I like it +40 Vote: I do not like it

How many tasks will be?

»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
6 years ago, # |
  Vote: I like it +67 Vote: I do not like it

Scoring?

»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
6 years ago, # |
  Vote: I like it -87 Vote: I do not like it

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 years ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    How to solve D?

    • »
      »
      »
      6 years ago, # ^ |
        Vote: I like it +8 Vote: I do not like it

      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 years ago, # ^ |
          Vote: I like it +1 Vote: I do not like it

        Oh damn! I did a similar thing. Perhaps my implementation has a mistake :(

        Thanks for the response

      • »
        »
        »
        »
        6 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Exactly, but it is not necessary the segment tree:)

        • »
          »
          »
          »
          »
          6 years ago, # ^ |
            Vote: I like it +3 Vote: I do not like it

          sure! there is no need to use segment tree. it can be solved with a simple brute force

      • »
        »
        »
        »
        6 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        I'm trying with your approach. But I'm getting TLE on TC 9. Can you please help me out?? MySol

        • »
          »
          »
          »
          »
          6 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          What exactly are you doing? The complexity should be

          • »
            »
            »
            »
            »
            »
            6 years ago, # ^ |
              Vote: I like it +1 Vote: I do not like it

            The complexity should be O(N + Q)

            • »
              »
              »
              »
              »
              »
              »
              6 years ago, # ^ |
                Vote: I like it 0 Vote: I do not like it

              With a segment tree the complexity is if I'm not mistaken.

              • »
                »
                »
                »
                »
                »
                »
                »
                6 years ago, # ^ |
                  Vote: I like it 0 Vote: I do not like it

                Don't use a segment tree then

                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  6 years ago, # ^ |
                  Rev. 2   Vote: I like it 0 Vote: I do not like it

                  Haha...Well it fits within the Time Limit so we can use it... And if you'll notice, the OP asked what the issue was with his code...and he is using a segment tree...

                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  6 years ago, # ^ |
                  Rev. 2   Vote: I like it 0 Vote: I do not like it

                  Segment tree is more complicated to code than O(N + Q)

                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  6 years ago, # ^ |
                    Vote: I like it 0 Vote: I do not like it

                  Maybe so...but that's not the issue here... I was simply conveying the complexity of the OP's code.

      • »
        »
        »
        »
        6 years ago, # ^ |
          Vote: I like it +1 Vote: I do not like it

        Maybe we don't need segment trees. All we need is a monotonous stack.

        • »
          »
          »
          »
          »
          6 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          You can refer to my code for more details.

        • »
          »
          »
          »
          »
          6 years ago, # ^ |
            Vote: I like it +4 Vote: I do not like it

          Exactly a stack! I don't code it but I thought in it.

  • »
    »
    6 years ago, # ^ |
      Vote: I like it +97 Vote: I do not like it

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

  • »
    »
    6 years ago, # ^ |
      Vote: I like it +116 Vote: I do not like it

    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 years ago, # ^ |
      Rev. 2   Vote: I like it +8 Vote: I do not like it

      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 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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 years ago, # ^ |
    Rev. 2   Vote: I like it +18 Vote: I do not like it

    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 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      my hack failed

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

      • »
        »
        »
        »
        6 years ago, # ^ |
        Rev. 2   Vote: I like it 0 Vote: I do not like it

        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 years ago, # |
Rev. 2   Vote: I like it +8 Vote: I do not like it

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 years ago, # ^ |
      Vote: I like it +29 Vote: I do not like it

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

    • »
      »
      »
      6 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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 years ago, # ^ |
        Rev. 2   Vote: I like it +32 Vote: I do not like it

        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 years ago, # ^ |
            Vote: I like it +6 Vote: I do not like it

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

          • »
            »
            »
            »
            »
            »
            6 years ago, # ^ |
              Vote: I like it +19 Vote: I do not like it

            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 years ago, # ^ |
              Vote: I like it +6 Vote: I do not like it

            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 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

    • »
      »
      »
      6 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    6 years ago, # ^ |
      Vote: I like it +6 Vote: I do not like it

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

    • »
      »
      »
      6 years ago, # ^ |
      Rev. 3   Vote: I like it +16 Vote: I do not like it

      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 years ago, # ^ |
        Rev. 3   Vote: I like it 0 Vote: I do not like it

        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 years ago, # ^ |
    Rev. 3   Vote: I like it +13 Vote: I do not like it

    In F, one can use path compression. 41719592

  • »
    »
    6 years ago, # ^ |
      Vote: I like it +4 Vote: I do not like it

    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 years ago, # ^ |
    Rev. 2   Vote: I like it +13 Vote: I do not like it

    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 years ago, # ^ |
      Vote: I like it +8 Vote: I do not like it

    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 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    6 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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 years ago, # |
Rev. 3   Vote: I like it -97 Vote: I do not like it

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

»
6 years ago, # |
  Vote: I like it +2 Vote: I do not like it

How to solve E?

»
6 years ago, # |
  Vote: I like it -7 Vote: I do not like it

Problem D :

For input : 3 5 0 0 0

Output : YES 1 1 1

why is this wrong ?

  • »
    »
    6 years ago, # ^ |
    Rev. 2   Vote: I like it +26 Vote: I do not like it

    The last query was with i = q, so q has to appear at least in one position.

  • »
    »
    6 years ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    There has to be at least one 5. 5 cannot be overwritten

  • »
    »
    6 years ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    because last query will affect atleast 1 value. there would be atleast one 5 in the final answer.

  • »
    »
    6 years ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    every query has to be applied on atleast one element of the array. So if the output is 1 1 1 that means you didnt apply 2 3 4 5 queries

  • »
    »
    6 years ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    because q = 5 should be in the final array

»
6 years ago, # |
  Vote: I like it +7 Vote: I do not like it

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

  • »
    »
    6 years ago, # ^ |
    Rev. 2   Vote: I like it -52 Vote: I do not like it

    Write Blogewoosh #3 about it

  • »
    »
    6 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Or maybe Dilworth things?

  • »
    »
    6 years ago, # ^ |
      Vote: I like it +23 Vote: I do not like it

    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 years ago, # ^ |
        Vote: I like it +3 Vote: I do not like it

      Sorry, what is HLPP? A quick google search turned up nothing.

      • »
        »
        »
        »
        6 years ago, # ^ |
          Vote: I like it +24 Vote: I do not like it

        Highest label preflow push algorithm / Highest label push relabel algorithm.

»
6 years ago, # |
  Vote: I like it +74 Vote: I do not like it

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 years ago, # |
  Vote: I like it -92 Vote: I do not like it

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

  • »
    »
    6 years ago, # ^ |
      Vote: I like it +56 Vote: I do not like it

    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 years ago, # ^ |
      Rev. 2   Vote: I like it -25 Vote: I do not like it

      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 years ago, # ^ |
        Rev. 2   Vote: I like it +38 Vote: I do not like it

        "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 years ago, # ^ |
            Vote: I like it -8 Vote: I do not like it

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

          • »
            »
            »
            »
            »
            »
            6 years ago, # ^ |
              Vote: I like it +13 Vote: I do not like it

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

      • »
        »
        »
        »
        6 years ago, # ^ |
        Rev. 4   Vote: I like it +26 Vote: I do not like it

        "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 years ago, # ^ |
      Vote: I like it +10 Vote: I do not like it

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

    • »
      »
      »
      6 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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 years ago, # |
  Vote: I like it -44 Vote: I do not like it

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 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

»
6 years ago, # |
  Vote: I like it +16 Vote: I do not like it

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

»
6 years ago, # |
Rev. 2   Vote: I like it +15 Vote: I do not like it

F*** your pretests

»
6 years ago, # |
  Vote: I like it +39 Vote: I do not like it

is this the hardest div2A in the history of codeforces

»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

any idea about pretest 7 for problem D ?

  • »
    »
    6 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      any idea about 10th pretest case. I failed on it. Could not figure out my mistake :/

»
6 years ago, # |
  Vote: I like it +15 Vote: I do not like it

Weak pretests = Never ending system testing !!

»
6 years ago, # |
  Vote: I like it -8 Vote: I do not like it

Can anyone see something wrong in here?

http://codeforces.me/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 years ago, # |
Rev. 5   Vote: I like it -8 Vote: I do not like it

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.me/blog/entry/61254?#comment-451801

»
6 years ago, # |
  Vote: I like it -8 Vote: I do not like it

How to solve C?

  • »
    »
    6 years ago, # ^ |
    Rev. 2   Vote: I like it +6 Vote: I do not like it

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

    • »
      »
      »
      6 years ago, # ^ |
        Vote: I like it +3 Vote: I do not like it

      Damn that's a simple solution. Thanks!

    • »
      »
      »
      6 years ago, # ^ |
      Rev. 2   Vote: I like it 0 Vote: I do not like it

      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 years ago, # ^ |
        Rev. 2   Vote: I like it +10 Vote: I do not like it

        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 years ago, # |
  Vote: I like it +15 Vote: I do not like it

How to solve A?

  • »
    »
    6 years ago, # ^ |
      Vote: I like it -6 Vote: I do not like it

    your question is soo tough please wait Editorial like me!

  • »
    »
    6 years ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    t[:-len(v)].startswith(u) and t[len(u):].endswith(v)

    After a red bold number showed, I found this — t[:-0].

  • »
    »
    6 years ago, # ^ |
      Vote: I like it +8 Vote: I do not like it

    Maybe Python will help.

    I tried Python's unfamiliar regular expression, found it didn't work, then waste a lot of time using C++'s strtok...

    All I actually need is Python's split、startswith、endswith...

  • »
    »
    6 years ago, # ^ |
    Rev. 2   Vote: I like it -8 Vote: I do not like it

    I have a solution using STL string functions xD

»
6 years ago, # |
  Vote: I like it +16 Vote: I do not like it

»
6 years ago, # |
  Vote: I like it -65 Vote: I do not like it

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

  • »
    »
    6 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    really ez, just don't take the case s.size() > t.size() and s dosen't have the character *, but take the case s.size() — 1 > t.size() ans s does have the character *, REALLY EASY

»
6 years ago, # |
  Vote: I like it +10 Vote: I do not like it

Can someone please explain how to solve D ?

  • »
    »
    6 years ago, # ^ |
    Rev. 4   Vote: I like it +23 Vote: I do not like it

    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 years ago, # ^ |
      Rev. 3   Vote: I like it -12 Vote: I do not like it

      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 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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 years ago, # ^ |
          Vote: I like it +4 Vote: I do not like it

        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 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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 years ago, # ^ |
        Rev. 3   Vote: I like it +5 Vote: I do not like it

        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 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          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 years ago, # ^ |
      Rev. 2   Vote: I like it 0 Vote: I do not like it

      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 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        i mean set 0 to q only once if there are no q in array.

  • »
    »
    6 years ago, # ^ |
      Vote: I like it +10 Vote: I do not like it

    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 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    6 years ago, # ^ |
      Vote: I like it +10 Vote: I do not like it

    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 years ago, # ^ |
      Vote: I like it +4 Vote: I do not like it

    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 years ago, # |
Rev. 2   Vote: I like it +84 Vote: I do not like it

Problem C, D and E today are great.

»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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 years ago, # ^ |
      Vote: I like it +45 Vote: I do not like it

    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 years ago, # ^ |
      Vote: I like it +16 Vote: I do not like it

    Don't be angry, be careful.

  • »
    »
    6 years ago, # ^ |
    Rev. 2   Vote: I like it +10 Vote: I do not like it

    "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 years ago, # |
Rev. 4   Vote: I like it +1 Vote: I do not like it

what a great contest!

»
6 years ago, # |
  Vote: I like it +25 Vote: I do not like it

Kudos to problemsetters :D

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

»
6 years ago, # |
  Vote: I like it +1 Vote: I do not like it

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 years ago, # ^ |
      Vote: I like it +14 Vote: I do not like it

    the string t consists only of lowercase Latin letters

  • »
    »
    6 years ago, # ^ |
      Vote: I like it +6 Vote: I do not like it

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

  • »
    »
    6 years ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

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

    The test is invalid.

  • »
    »
    6 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

»
6 years ago, # |
  Vote: I like it +133 Vote: I do not like it

Thank you for the contest!

Problem E is very nice.

»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    6 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    You can see that after the contest is finished.

»
6 years ago, # |
  Vote: I like it +16 Vote: I do not like it

Freaking A again!

»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

my E will fail. (

»
6 years ago, # |
  Vote: I like it +5 Vote: I do not like it

Editorials please!

»
6 years ago, # |
  Vote: I like it +9 Vote: I do not like it

Really weak pretests :(

»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

tc 87 for problem A ??

»
6 years ago, # |
  Vote: I like it +32 Vote: I do not like it

Deadly problem A :D

»
6 years ago, # |
  Vote: I like it +12 Vote: I do not like it

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

»
6 years ago, # |
  Vote: I like it -10 Vote: I do not like it

F was easier than A!

»
6 years ago, # |
Rev. 6   Vote: I like it 0 Vote: I do not like it

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 years ago, # |
  Vote: I like it +3 Vote: I do not like it

when will be the solutions available?

»
6 years ago, # |
  Vote: I like it +3 Vote: I do not like it

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

  • »
    »
    6 years ago, # ^ |
    Rev. 2   Vote: I like it +5 Vote: I do not like it

    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 years ago, # |
  Vote: I like it +1 Vote: I do not like it

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

  • »
    »
    6 years ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

    You allocate a new copy of the answer string on each iteration. Try ans += '('; instead.

    Even better, just print the output directly to cout.

  • »
    »
    6 years ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

    Use a+=x instead of a=a+x for strings. AC solution: 41731870

»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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 years ago, # |
  Vote: I like it +8 Vote: I do not like it

Benq kept his promise to become a LGM :)

Congratulations !!

My mission is nearly done unless you win the IOI!

»
6 years ago, # |
Rev. 2   Vote: I like it +17 Vote: I do not like it

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 years ago, # |
Rev. 3   Vote: I like it 0 Vote: I do not like it

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 years ago, # |
  Vote: I like it +29 Vote: I do not like it

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 years ago, # ^ |
    Rev. 3   Vote: I like it 0 Vote: I do not like it

    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 years ago, # |
Rev. 3   Vote: I like it +11 Vote: I do not like it

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 years ago, # |
  Vote: I like it +32 Vote: I do not like it

Weak testcases in D

My solution gives NO for

Testcase
»
6 years ago, # |
  Vote: I like it +8 Vote: I do not like it

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 years ago, # |
Rev. 2   Vote: I like it +18 Vote: I do not like it

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 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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 years ago, # |
  Vote: I like it +18 Vote: I do not like it

Where's the editorial?

»
6 years ago, # |
  Vote: I like it +28 Vote: I do not like it

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 years ago, # ^ |
      Vote: I like it +23 Vote: I do not like it

    Also this test

    3 3
    2 1 3
    

    Real answer is "YES", but his answer is "NO".

»
6 years ago, # |
  Vote: I like it +16 Vote: I do not like it

still waiting for editorail...

»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Can someone explain what I must to do in C?

Sorry for poor english.

  • »
    »
    6 years ago, # ^ |
    Rev. 3   Vote: I like it +8 Vote: I do not like it

    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 years ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    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 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
6 years ago, # |
  Vote: I like it +8 Vote: I do not like it

Can anybody tell the link of editorials for this contest?

»
6 years ago, # |
  Vote: I like it +8 Vote: I do not like it

Where is editorial?

»
6 years ago, # |
Rev. 2   Vote: I like it +11 Vote: I do not like it

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 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

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

  • »
    »
    6 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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 years ago, # |
  Vote: I like it +3 Vote: I do not like it

Can someone explain a solution with HLD for problem F?

  • »
    »
    6 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.me/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 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
6 years ago, # |
  Vote: I like it +16 Vote: I do not like it

Where can I find the editorial of this round?

»
6 years ago, # |
  Vote: I like it +3 Vote: I do not like it

editorial ???

»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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.