doreshnikov's blog

By doreshnikov, history, 3 years ago, In English

Hello Codeforces!

Once again, we are glad to invite you all to Codeforces Round 753 (Div. 3), the third division round held on Nov/02/2021 17:35 (Moscow time). This round was prepared (again) by me and MikeMirzayanov. The problems are different but our anticipation is the same :) Hope you will like the problems we've prepared!

Big thanks to MikeMirzayanov for great ideas as well as for helping me with writing good statements and better tests. I'm still a bit slow with some aspects of preparing problems so it's a really noticeable help for me. (UPD: as of this moment, it became much more noticeable, so, really, thanks a lot!)

Also special thanks for testing the round to RisingWizard, Capta1n_Shy, Mazaalai, GustavoMG, nizamoff, 2020akadaver, ashmelev, p0kemanbr, Kofta and, as usual, to Gassa for valuable comments! And last but not least, thanks to everyone who'll be participating! This round contains 8 problems and is expected to have a decent level of difficulty for participants with ratings up to 1600. However, all of you who wish to take part and have a rating 1600 or higher, can register for the round unofficially.

The round will be hosted by rules of educational rounds (extended ACM-ICPC). Thus, during the round, solutions will be judged on preliminary tests, and after the round, it will be a 12-hour phase of open hacks. We tried to make tests strong enough but it doesn't at all guarantee that open hacks phase will be pointless.

You will be given 8 problems and 2 hours to solve them. We remind you that the penalty for the wrong submission in this round (and the following Div. 3 rounds) is 10 minutes. Also please note that the number of problems has slightly increased since the last edit.

Remember that only the trusted participants of the third division will be included in the official standings table. As it is written by link, this is a compulsory measure for combating unsporting behavior. To qualify as trusted participants of the third division, you must:

  • take part in at least two rated rounds (and solve at least one problem in each of them)
  • do not have a point of 1900 or higher in the rating.

Regardless of whether you are a trusted participant of the third division or not, if your rating is less than 1600, then the round will be rated for you.

Good luck to everyone!

UPD: Editorial is out!

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

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

I hope to become Expert in this round. Please, wish me luck :)

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

Look forward to great problems in this round! And I find that there is no testers in this round.

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

i hope to add 50 points

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

    you can make it :)

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

      Hey I don't see any changes in rating. When will they be updated?

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

        Yes same thing I too wanted to ask

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

          this round is considered unrated in my contests don't know why.

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

            Are you sure that if it's listed there then it means it will not be rated for us? because I feel it's listed under the unrated contests because they didn't finish the rating calculation.

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

              I don't know actually just wait that's all we can do

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

                Bro Div 3 contests are rare for us beginners and also 1 done in one month they make it not rated where will we live then

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

                  Its not unrated guys it always appears in the unrated section until the rating updates . This contest is rated don't worry!!!!!

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

                  Oh, Im so worry

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

                  Such a relief to hear that, but do you know when is the update of rating?

                  UPD: nevermind, +173 is here

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

                  same

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

                  adu hi người cùng fanbase :))

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

                  Hii :)) tiện thể học tiếng anh luôn :)))

»
3 years ago, # |
Rev. 2   Vote: I like it -21 Vote: I do not like it

Note the unusual time of the round.

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

My first unrated round and this means a lot to me. It feels a lot better than I thought. I put a lot of effort into this in last 3 months and now this feeling is different kind of motivation to improve further. Codeforces has been sort of home to me. A big thank you to the best place on internet.

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

    .

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

      No explanation. There can't be any explanation for cheating ever. I still regret it and never did that again. I was deservedly skipped from that contest. And I can only say one thing and assure you that It will never ever happen again. I never should have done that. I'm Sorry.

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

      I think there is no way to cheat on codeforces, codeforces have too good security to cheat.

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

    U cheated in codeforces round 743 div2. Any explanation for that?

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

      NO, I DIDN'T. I did it only once and have accepted it and will never never do ever again.

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

      That contest was made unrated for everyone.

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

        Yes, right. Due to long queue issues.

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

Hope to cross 1400.

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

    Sir, i have one doubt.

    Is it difficult to increase one's rating in div3 round after one has become pupil?

    Because in last div3 round, I solved 4 problems and gained only +3 .

    Moreover the predictor was indicating -10.

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

      no, just solve more

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

      I think rank matters more than the number of problems solved.

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

      I gained +42 in last div 3 by solving 4 questions try to solve them quickly and without any wrong submission.

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

Is it unrated?

»
3 years ago, # |
  Vote: I like it -12 Vote: I do not like it

My first unrated round!

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

I hope to cross 800 cause this is my first time and I'm new to coding ^_^

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

Hope to solve 5 problems.

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

Wish I could also comment My first unrated round. LOL!

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

I hope to return to monke in this round.

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

It's gonna be my first unrated div3 contest

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

GL HF!

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

Perfect. A round on my birthday where i can't lower my rating :D

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

Hope to become pupil in this Round, wish me luck :)

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

As a tester, I want contribution. :)

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

We tried to make tests strong enough but it doesn't at all guarantee that open hacks phase will be pointless.

Thank you for your honesty.

»
3 years ago, # |
  Vote: I like it +16 Vote: I do not like it
As a first time tester, I must say
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Hopefully I will become Specialist after this contest.

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

As a tester, i feel problems are very interesting.

Hope you get more rating in this contest.

Have a nice day :).

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

I'm +3 away from being green, wish me a good luck guys.

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

At this point, it's really become necessary to remind this:

note the usual start time

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

is expected to have a decent level of difficulty for participants with ratings up to 1600.

Such a nice word decent.

As I have to say, I'm always hoping for solving those decent problems in div.3 in contest. But almost always, it turns out that those problems are too hard for me or even someone else with higher rating than 1600 to pass QWQ.

Wish me solve some of these decent problems in the upcoming div.3 round today.

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

Hoping to recover points which i had lost on the previous round :)

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

i guess that div3 is a great choice for the first round ever

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

50 points away from expert, wish me good luck !

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

Expert to be ♥

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

i have a feeling that my solution for D is wrong and gets ac

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

GG crappy memory limit like FHC

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

can't wait for the editorial, G is a new thing for me

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

Infinite loop / massive stack memory usage case for MLE on test case 4 of F? Is there no way to get AC without building the solution iteratively?

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

    Just stack memory usage. I had to stop using vector of vectors and use normal functions instead of std::function to get AC.

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

    Accurate enough DFS implementations were accepted, most of the testers' solutions used DFS and got AC :)

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

      Anything that stands out to you as problematic in this solution? 134105154

      Three cases are general non-calculated, cycle found and value already known.

      I can't really think of much that's removable except removing $$$on_cycle$$$ and using a reference to a common int for cycle start node or something like that.

      Anyway is there a reason for the constraints to be so high in this problem? I can't think of any incorrect solution that needs to be cut off that won't also fail for $$$n \times m \leq 3 \times 10^5$$$

      • »
        »
        »
        »
        3 years ago, # ^ |
        Rev. 3   Vote: I like it -27 Vote: I do not like it

        As I see it:

        1. gridx and gridy arrays are unnecessary, there's no point in storing them explicitly
        2. solve() can be slightly optimized by making curval global (and x and y also, but it will make code a bit less readable). Also local variables can be inlined

        I understand that these kinds of optimizations are not what you expect from Div.3 but the main expected solution doesn't use dfs at all, so it's not like we wanted to fail dfs explicitly, we just didnt' tune ML for any dfs to pass.

        UPD1: (sorry, previous UPD wasn't true, fixed)

        UPD: We just re-checked your solution in Polygon with double ML after making some modifications and it passed, so I guess we should've made the ML larger. Sorry about that :(

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

          My solution failed because of that too. I considered that to be a problem. But I didn’t believe that it was a true reason to get ML. After the contest I wrote solution without dfs and it passed

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

          Just wondering, in polygon, does increasing the ML also increase the stack limit (the option given to gcc -Wl,--stack=268435456)?

          I am debugging in gym and it doesn't seem like setting a higher memory limit changes the stack size. You still get a RTE/stackoverflow when you use above 250ish mb which is making this really annoying to debug.

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

I am completely apalled that you need to do a constant optimization in MEMORY on a official cf round. There are currently 15 PAGES of MLE solutions on F. Even using std::function at all gives MLE. Actually disgusting.

»
3 years ago, # |
Rev. 3   Vote: I like it +10 Vote: I do not like it

Was it really that necessary to make the limits tight for problem F, so that scc with recursion would TLE/MLE ??? Was it ???

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

How to solve D?

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

    My idea was greedy : first take the blue marked numbers and red marked numbers in the ascending order and keep a variable can = 1 Iterate through blue numbers : if (blue_number>=can) then can++ else we cannot convert this number to any other number in the permutation ans = NO;
    similarly for red numbers if ( red_number <=can) for each red_number if this too fails then ans = NO

    in all the other cases ans = YES

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

is G greedy?

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

    Yep

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

    Yup, identify maximum prefix increase of a — b possible for first $$$i$$$ nodes. Then as we go backwards make operations so the difference is below the max prefix possible and as close below it as we can get (so it lies above the min prefix possible).

    I think the intuition is clear, but I do hand wave away some details so maybe there is a small edge case I'm missing and I'll get hacked.

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

    A simple-ish way to think about G is as follows:

    Given values of a[i] and b[i], there is a minimum amount of each that the tester must eat (sometimes 0). Iterate once through and assign this minimum amount. This leaves a remaining 'variable amount' for each dish, and a starting difference. Iterate through again and assign this variable amount in such a way as to bring the difference back as close to 0 as possible.

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

      It feels so good when someone has done the exact same thing that you did and got AC .. Glad I could think this in time..

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

Am I the only one for whom was the 2 hours too tight for this contest?

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

such a bad div 3 round I have ever given. Authors div 3 is for newbies, so kindly make the problems for newbies and not for pros.

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

Someone please explain problem G, i don't understand :( example: test case inp 3 6 1 8 1 9 30 10 out 7 1 5 1 5 6 0 why the first line = 7 @@

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

    the minimum imbalance after eating for that testcase is 7

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

      Yeah out 7: 1 5 -> 1 5 -> 6 0`` but abs( (1 + 1 + 6) — (5 + 5 + 0) ) = 4 or did I misunderstand

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

        its the absolute value of what is left, not what is eaten

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

    You need to maximize the balance of dishes after the taster eat some of them, not maximize the balance the dishes eaten by the taster.

    Really annoying statement :(

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

Really annoying G for its unclear statement. The taster needs to maximize the balance of dishes WHICH IS LEFT AFTER EATING BY HIM, not eaten by him. It drops me from rk 40~ to 170 :(

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

    doesnt the first testcase show what they meant?

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

      I didn't saw it until I finish my program. I think the statement is clear enough, but it doesn't.

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

    You don't need tarjan x)

    The graph is a functional graph so it's enough to just iterate while you don't cycle and keep track of the nodes you're visiting in a vector. Then, if you visit a node X you visited in the same run, there is a cycle starting at node X and you can recover the cycle with your vector

    See my code here for more details: [submission:https://codeforces.net/contest/1607/submission/134137875]

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

the MLE of F is awful

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

I believe, F should belong to an educational round, not to a div3 round. Like I am not against teaching people how to write dfs using stack (though I believe that the authors who design such problems are quite... strange), but asking a beginner to do this optimization? For me it looks like the best way to discourage them from doing cp.

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

    It's true that DFS is one of the first things that come to mind when one sees this problem, but it's not the only thing that could be used...

    The ML wasn't set up to explicitly fail all DFS solutions (and I mean it), we just expected a solution without DFS as we know it so we didn't tune the ML for any DFS to pass.

    Since if you think about the board as a graph, each vertex has only one outcoming edge and you can walk through the graph with a single loop without even knowing that such thing as DFS exists. And that's what actually written in main solution.

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

      Actually there are some DFS solutions be able to be optimized enough to pass. Yet they are very rare compared to those get MLE.

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

      Well, that's great that you have a solution that does not need any additional optimization. But it seems you don't get the point, the thing is that failing recursive solutions (with correct time and space complexities) is not nice. Did you not think of dfs while setting up this problem? That's really strange, because that's the first thing that comes to mind.

      I believe that in beginners contest (in any contest, actually, but for beginners it's even more important) the authors should try to cut off solutions with bad complexity and allow solutions with good complexity to pass comfortably and I also belive that this does not hold for this problem.

      UPD. So you say that none of the testers solutions were close to ML, while having recursive dfs inside? Seems unbelievable. Or you mean that they were able to squeeze dfs into time limit? This is possible, of course, but really, you wanted 1600- rated people to optimize dfs?

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

        Maybe the authors wanted to SendThemToHell

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

        I understood your point, yes. The fact that in the end this task was challenging not because of it's algorithmic difficulty but because of the memory limit is kinda frustrating, this was not how it was intended.

        Well, I can't argue with the fact that this Div. 3 is not as well-adjusted as the previous one, sorry for that. We'll try to make the next one more pleasant to solve.

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

          I solved 7 problems in 1 hour. And couldn’t optimize dfs to pass in the remaining hour of the contest :(

          everything else is super. Thanks for the great contest :) спасибо за интересные задачи

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

        Yes most of the recursive solutions fail just because of MLE. But my main point is that there are so rare dfs solutions with heavy optimization to be able to pass, I did not mean that DFS is enough to past.

        I think that the author make a miscalculation to use 256Mb instead of 512Mb and kill around atleast half of the solutions.

        Yet some of my CM friend still find it very confusing to optimize further, some even spend an hour without being able to solve it.

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

      But is there a solution that even needs to be cut off? If not why set the constraints so high? Additionally you mentioned earlier that some testers had dfs solutions, were none of them close to the memory limit?

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

    the graph is a functional graph so you can just use a loop 134137875 (although I used a DFS during the round and got few problems)

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

      Is there a prerequisite technique on how to find the longest path in a functional graph? I dont get your solution, what do the while loops do?

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

        First, why do I have that much downvotes :') ?!!

        I'll try to explain my solution step by step. First notice that in the graph, each node has at most one child. So basically, any connected component has at most ONE CYCLE.

        Indeed, let's assume you're currently constructing the connected component starting from node $$$1$$$. When we're at node $$$i$$$ we have two choices: we can either add an edge to node $$$i + 1$$$ (so the graph looks like a path and we don't have any cycle) or we can add an edge to some node $$$j$$$ such that $$$j < i$$$ and we'll create a cycle. Notice that after a cycle has been created, we can't add any more edge.

        Now let's say we found the cycles. For a given cycle, the length of the longest path is the same for each node of the cycle (it's the size of the cycle).

        So now we know that a functional graph looks like

        ......x

        ......|

        ......|
        ......v

        x->x->x->CYCLE

        (the . are used to align the edges. I'm sorry I couldn't do something clean. I'll try to send a drawing asap)

        Imagine it as we link some sort of directed tree (where all the edges are directed toward the root) to a cycle.

        About my code:

        What you can do is store for each node:

        1) if it has been visited

        2) if we are visiting the node (this means the node is part of the path we are exploring right now)

        3) the longest path starting from this node

        In my code $$$ans[i][j] == 0$$$ if the node hasn't been visited, $$$ans[i][j] == -1$$$ is we're visiting the node, else it's the longest path starting from this node.

        Now let's iterate over each node $$$u$$$. If the node hasn't been visited, let's start a walk in the graph (basically we explore the unique path starting from node $$$u$$$). We'll keep track of a vector of all the nodes in the path ($$$curCycle$$$ in my code) and we'll also remember the length of the path ($$$cnt$$$ in my code)

        This is what I do in the first while loop.

        Let's say the child of our current node is $$$v$$$. If it's the first time we see it then we move to $$$v$$$ and keep exploring (don't forget to update $$$curCycle$$$ and $$$cnt$$$). If we already computed an answer for node $$$v$$$, we simply increment $$$cnt$$$ by this answer and break. Now, if $$$v$$$ is already part of our path (in my code it's $$$ans[i][j] == -1$$$), it means we cycled. So we're going to look for the last occurence of $$$v$$$ in our array $$$curCycle$$$. All the nodes after this occurence are part of the cycle and their answer should be updated accordingly. Notice that as we cycled, we can't expand our path anymore.

        Now we also need to update the answers of all the nodes in the path (nodes which are outside of the cycle). So we basically start again to walk from node $$$u$$$ and we set it's answer to $$$cnt$$$. Then when we move to the child of the current node, $$$cnt$$$ should decrease because the length of the path is reduced by $$$1$$$.

        The time complexity is $$$O(N)$$$ where $$$N$$$ is the number of nodes (here $$$N = nm$$$). Indeed, we visit each node exactly once because after a node has been visited, it's answer is remembered and we'll never explore again it's path.

        Essentially, finding cycles in a functional graph is the same as finding if there is a cycle in a directed graph (See CSES Round Trip)

        The only difference is that:

        1) As the graph is pretty simple we can use a while loop instead of a DFS

        2) We're actually finding ALL the cycles of the graph because each connected component has at most one cycle

        About the other part of the algorithm, imagine you "compress" the cycles into one big node with it's answer = the length of the cycle. We now have a DAG (and more specifically it's a kind of directed chain) so we can apply DP (here we have only one transition per node).

        The while loops are just a more convenient/efficient way to implement the algorithm.

        A few problems about functional graphs:

        Usaco silver, Swapity Swapity Swap

        Usaco silver, Dance Mooves

        Usaco gold, Exercise (well this one is a bit less related but it's an interesting problem)

        I hope my explanations were clear, if they weren't just ask me and I'll do my best to explain :)

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

Why the memory limit for F is so tight ? As a beginner I find it very hard to optimize memory further more (though there are better algorithm but I cant just think of it)

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

    The same for me. Seems recursive programming does not work. Have to do in a loop.

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

      Most of my friend using DFS are failed due to MLE (and there are CM too). Just one among them be able to pass using kosaraju instead of tarjan.

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

        wait, did you really compressed the graph using strongly connected components ?

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

        U wrote opposite maybe
        I believe he would have used tarzan as Kosaraju takes more memory . I too passed it in recursive way but I had to find cycles by simple DFS . And code is still on the edge for MLE .

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

        But isn't Kosaraju also dfs?

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

          I mean that he is the only one among us used DFS and be able to pass lol

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

Someone please tell me why my code is not working in problem D.

134132886

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

    You forgot return statement in the flag == 1 condition :/

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

    You misunderstood the problem. The numbers can be completly out of range of 0..n, so the code does not work at all.

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

      No, they added specific conditions for 'B' and 'R'. Since 'B' can only be decreased by 1 and 'R' can only be increase by 1, it seems right to me.

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

        Consider in example all red numbers bigger than n. Obviously output must be No.

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

          Sorry I don't get your point. This is exactly what is done in their code + what I explained.

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

            No, the code does not check this.

            The var temp1 never gets incremented if values are out of range 1..n, so output is never No.

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

              Parts of the code

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

Can anyone help me understand why this is TLE on F? https://codeforces.net/contest/1607/submission/134130569

I'm pretty sure it's just linear time complexity DFS with the board size, but why TLE?

Is this because it's using recursive and cause stack overflow?

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

    I see you're using std::map and std::set in your code, both of them will make total time complexity of code as: $$$t \times n \times m \times \log(n \times m)$$$ which will surely give TLE over all test cases :(

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

      even if it's using map and set, the complexity is 4*10^6 log (4*10^6) which is less than 100 millions. Why would that TLE over all test cases?

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

        100 millions operations is at the border of the time limit per cases

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

How to solve B? :(

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

    The key observation is that after 4 steps you are where you started.

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

I really like it to solve so much problems as in div3 possible. But today there was also a big difficulty gap from E to F,G,H.

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

This input data is from Test Case #3 of problem D.

Test Case :

Hi doreshnikov, Could you please help me? I wanted to know what is the logic behind this test case. I have stress tested my solution on random 10000 inputs of array length 20 but my generator couldn't catch this.

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

    Not sure what's so exceptional about this test. If you sort all the numbers by (color, value), you get something like this

    As you can see, all blue numbers can be decreased to the corresponding number from permutation and all red numbers can be increased to get the number from permutation (the first number in the row is the expected number from permutation).

    It could be the fact that there is a Blue number that you don't have to apply operations to (2), but I was sure a similar case was in the example test...

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

WTF! Why do you put a blank line in the input?

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

    If there was no blank line it would be hard to know which testcase is which. The extra blanks don't affect input

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

    So it is easier to distinguish tests in a multitest when you read it

»
3 years ago, # |
  Vote: I like it -30 Vote: I do not like it

B was trash

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

    It was a pretty straightforward observation after dry running any testcase that we land at the starting position after every 4 jumps.

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

      oh is it so straightforward? Please teach me how to make observations.

      Observations suck!

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

        Observations are quite important in the world of competitive programming :) it's pretty valid advice from yasserkhan45: if you can't see the answer immediately, experiment with some test cases. As is pointed out, a single test case was enough to see what happens in general, and a small modification was required for an odd starting position.

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

          What to do if I still can't see through, happens with me most of the times, observational questions are the ones that take up most of my time in a contest, for most people they are straightforward but for me :(, any advice on how to improve?

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

            If observation doesn't work, sometimes it helps to write a solution that you know is slow and will not pass but is really easy to implement (in this case it's just to simulate the process).

            Either you'll find a way to optimize it later so it would get OK (not in this particular problem though) or you'll have a way to search for patterns in answer a bit faster. In IOI format it also may help you to get at least partial score.

            If nothing else, at least you'll have a solution you can stress-test your main solution with if something goes wrong with it.

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

            There's no catch-all answer here and I don't want to reel off any cliches but:

            • practice really does make an enormous difference here: the more questions you solve, the more your past experience can inspire the right ideas.

            • limits often provide a clue. The limits here were big, so it was clear there must be some sort of pattern that did not require us to iterate over all moves.

            • look for patterns. Here, if you choose a starting point of 0 and iterate for a few moves, you get [0, -1, 1, 4, 0, -5, 1, 8, 0, -9, 1, 12, 0, -13, 1, 16, ...]. It's clear that we keep getting back to 0, and that this happens every 4 moves — think about why. It's because every 4 moves, the first and last move go left, and the middle two moves go right. What's happening between those moves? Every other even move (n % 4 = 2) brings us back to 1 (it's easy to consider why this happens). If n % 4 = 1, we're subtracting n from 0. If n % 4 = 3, we're adding n to 1. So this gives us the complete set of cases [0, -n, 1, n+1] for the four possible values of n % 4. Then we add the starting position. If we start on an odd position, it turns out (by similar experimentation and consideration) that the complete set of cases is [0, n, -1, -(n+1)].

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

              you are right but my observation took a lot of time, I guess more practice will help, thanks for the advice :)

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

              It’s took almost 1 hour for me to solve B problem. After contest I asked my friends why B problem is so hard(After B I solve 2 more problems in less than 20 min), I was shocked that we can n%4. My solution is arithmetic progression, after we start in even number we move -1, +2, +3, -4, -5, +6, +7 etc. So I saw we have progression +2,6,10... and 3,7,11... -4,-8,-12... I just don’t know why this problem is B, because C is easier. In C you don’t need to notice anything, just write easy code. In B you have to write complicated arithmetic progression(which is obvious will pass 10^14 tests, after that I just didn’t think about another solution), or notice n%4 somehow.

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

                That’s why you shouldn’t spend much time on one problem. You only read B and didn’t read other problems. Try to read next problems too, because they may be easier for you. If you just skipped B, you would have taken higher place on the contest. For example I solved problems in this order A B C D E H G and F after the contest.

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

      I still think its dumb. If you try to work out an idea instead of looking at the sequence and guessing you waste a bunch of time and get nowhere. To this point i have no idea why my solution works (will probably work it out now that i said this).

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

134139660 please see my solution .I am getting tle . for no reason .

please do not ignore .

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

Question B and C someone please explain approach of these :))

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

    C, consider the array a[] to be sorted. So the first value is smallest, so gets removed first. Observe that all values allways change by the same amount, so the relative sorting allways stays the same. So the values are removed from left to right.

    When removeing a[0], a[1] becomes a[1]-a[0], a[2] becomes a[2]-a[0] and so on.

    When removing a[1], a[2] becomes a[2]-a[0]-(a[1]-a[0])=a[2]-a[1] Same for a[3] becomes ... =a[3]-a[1]

    When removing a[2], a[3] becomes a[3]-a[2]...

    So ans=max(a[0], max(a[i]-a[i-1]))

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

I got runtime error in test 10 problem H. Can someone fix for me

https://www.ideone.com/64cEbJ

»
3 years ago, # |
Rev. 3   Vote: I like it +18 Vote: I do not like it

I guess this is because the pointer in 64bit system is 8 bytes :(

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

I tried solving F. Robot on the Board 2 using dfs with dp on the matrix using directions as edges and cells as nodes.

My idea was to first find a single nodes for each simple cycle for which I used dfs1. Then I used dfs2 to set each nodes of every cycle to it's cycle length. Finally, I used dfs3 to get length of paths for the remaining nodes of the graph. I'm getting Memory limit exceeded due to some bug. Can anyone point out the issue here.

Here is my submission #134144883.

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

    When you have recursion(dfs) system reserves memory for that recursion. It is usually called stack memory. So your dfs uses additional O(N*M) memory. That’s why you got MLE, and me too. Try to solve this problem without recursion.

    Hint: all cells have only one outgoing edge

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

    My Solution got AC with DFS although it is also on the edge of MLE. You can have a look if u want .

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

Memory limit was too tight for problem F. I used dfs and got MLE with a memory usage of 283MB using C++17(64). However, I submitted it for C++17 and got AC, only 161MB.

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

I hope to become Expert today :) (unless any of my question is hacked :( ) Thanks for this wonderful round!

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

Thank you so much for interesting & worth studying problems :) I really enjoyed it. p.s. Any editorials yet?

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

when will system testing / hack rejudging start??

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

I hacked 10 users!

When will system test begin?

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

    I hacked 10 users! — r/lethal

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

    And I made my first ever hack...

    Kinda excited for my testcase to appear lmao

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

      rip whoever got TLE'd by my test lol

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

    any tips for hacking?

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

      To hack the records whose times are near the bound.

      If the time limit is 1s,we can find the records in 950~999ms.

»
3 years ago, # |
Rev. 3   Vote: I like it -9 Vote: I do not like it

how to improve my logic

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

Can anyone tell how to get rid of MLE in test 4 in problem F. Link to my submission:- https://codeforces.net/contest/1607/submission/134177362

I used Kosaraju's algorithm and then did dp in the condensed graph.

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

    here's what I did:

    1. i was earlier using SCC to find cycles, but then I switched to using just DFS

    2. iterative DFS using stack, instead of recursive DFS

    my submission: 134172739

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

This was my first ever contest. I was not able to solve all the problems and wanted to know the solutions of it. PLease tell me where can I find the tutorials

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

    They aren't out just yet, they should be in a short while :)

»
3 years ago, # |
  Vote: I like it -9 Vote: I do not like it

This was my first round, and I solved 7 problems but i'm still unrated :( Is this round unrated for me?

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

how to do problem C minimum extraction

I did a brute force but got tle

My solution

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

    $$$1\leq n\leq 2\times 10^5$$$

    And your code is not less than O(n^2).That must come to TLE.

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

    You must calculate the TIME COMPLEXITY before submitting.

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

      Thank you very much for replying Actually I didn't submit this solution in contest in fact I couldn't solve this. Now when I am upsolving it this is the only solution I can come up with. I wanted to know the actual approach or solution that is why I asked and I also gave my approach I can come up with. I know that is O(n^2).

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

        check editorial. It explains quite clearly.

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

Will this contest be rated for me? this is my first ever codeforces contest ? Any information on this will be really helpfull. Thank you!

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

    It is rated for you

    Regardless of whether you are a trusted participant of the third division or not, if your rating is less than 1600, then the round will be rated for you.

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

is there anyone whose rating has been updated yet? I am still unrated, so I was wondering if I had to do something more in order to get a rating..

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

Editorial? doreshnikov

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

    Sorry, wasn't feeling well. I promised the previous time that editorial will come out sooner, but couldn't finish it faster this time :(

    ETA: half an hour probably, I hope...

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

All problems in this round is with multi testcase. Interesting.

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

Sorry, but when is the editorial available? Because last 2 problems I can't solve it T_T

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

What's the meaning of the memory limit of Problem F...

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

I think A-E are good problems in div3,but F is obviously harder than E,it leads to the speed of solving the first five problems is particularly important.But anyway, I think it is a good round!

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

n

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

The test data for Problem H is not strong enough. After taste, for the $$$i$$$-th dish, $$$a'_i$$$ should be in $$$[\max(0, a_i - m_i), a_i - \max(0, m_i - b_i)]$$$; In my first submission, I wrote it as $$$[\max(0, a_i - m_i), a_i]$$$. It's wrong because I ignored this type of situation: when $$$m_i > b_i$$$, taster must eat some of $$$a_i$$$. But it got Accepted.

Upd: It seems this bug surprisingly can't be hacked, none business of the strength of the test data, sry.

»
3 years ago, # |
  Vote: I like it -22 Vote: I do not like it

比赛结束了吗,难度咋样

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

    What'are you saying?Which language?Chinese or Japanese?Please use English(recommended) or Russian.

»
3 years ago, # |
  Vote: I like it -18 Vote: I do not like it

if you like codeforces.com? then put +

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

    OK. We know there are 18 people here who don't like it, or just don't like you.

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

Good luck to everyone!

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

Hi