Gassa's blog

By Gassa, history, 4 months ago, translation, In English

Hi.

In Spring semester, I conducted a short course titled “Dynamic Programming” in SPbSU. To complete the course, the students solved many training problems, and also prepared their own problem in Polygon.

For the majority of the students, it was the first problem they authored. Nevertheless, the result looks cute. A couple problems went to local contests. From the remaining ones, I composed two trainings and put them on Codeforces. The trainings are set at the following time:

Each training contains both easy and hard problems. The majority of the problems are intended for training. I think orange participants and below will have enough problems for the duration. The problems go in randomized order.

Good luck!  

Update 1: a short text tutorial will be available after the second training. The tutorial for the first training is not ready yet, but will also appear at some point.

Update 2: thanks to the problem authors!

  • Marat Agranovskiy
  • Pavel Balay
  • Nikolay Berezikov
  • Alena Cherepanova (Monic)
  • Alexandra Durneva
  • Timur Garaev (the_timur)
  • Ivan Kazmenko (Gassa)
  • Igor Kiselev
  • Sofya Kopeykina (30SK5)
  • Igor Korkin
  • Maria Kozlovtseva
  • Anton Kuznets (Astronomax)
  • Maxim Milshin
  • Daniil Pavlenko
  • Sergei Petrov (psn2706)
  • Makar Selivanov (mselivanov)
  • Aleksandr Tulchinskij (TulchinskijA)
  • Ilya Tyuryaev

Update 3: tutorial for the first training is ready.

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

»
4 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Is the contest open to everyone?

If yes Contest Link is not working. May be uploading an invitation link or group link will work.

  • »
    »
    4 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Looks like the links start working when the gym starts.

    • »
      »
      »
      4 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Still, there is no option to submit as I haven't registered for the contest. (┬┬﹏┬┬)

      • »
        »
        »
        »
        4 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        But you can register now, right?..

        Sorry, I am setting a public gym for the first time. Not used to all the quirks.

»
4 months ago, # |
  Vote: I like it 0 Vote: I do not like it

What is the estimated rating for the problems ? or they're just educational problems ?

»
4 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Can anyone help what is wrong with my submission here for Problem G of Day-2, it gives WA on tc-3?

Spoiler
»
4 months ago, # |
  Vote: I like it 0 Vote: I do not like it

In H it's pretty obvious how to write the code, but when to logically decide when vasya wins or peter?

  • »
    »
    4 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    The tutorial is now available (see links in the post and in the gym).

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

271027559 Hey can any one check the issue in my code. I think it aligns with the intended solution but WAs on test case 5. Since the cases aren't visible I'm not exactly sure of the issue. Can one of the authors/managers please clarify?

Spoiler

Edit: Never mind got it. I was having a take not take style rec which was causing WA.Just removing that and iterating over the array fixed it

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

    Consider this line:

    ll res = max(1LL, rec(pos + 1, N, diff, ok));

    This assumes we can just skip an element of the array, and move on. In doing so, however, we lose the information about the previous element taken.

    details
    • »
      »
      »
      4 months ago, # ^ |
        Vote: I like it -11 Vote: I do not like it

      Thanks for looking into my submission. So I just removed the skip case and iterated over the whole array to find max length. That made it AC.

      I'll just post my AC code for anyone who might be facing a similar type WA.

      AC Code
»
4 months ago, # |
  Vote: I like it 0 Vote: I do not like it

I was solving problem I. Path and K Vertices. My solution is pretty much same as the editorial. I am maintaining two sets for finding k larger elements while using dfs. But this gives me wrong answer. can somebody tell me what is wrong in my solution.

Solution
  • »
    »
    4 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    The solution seems to assume root is the first vertex. This need not be true.

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

      Thanks for the help.
      I should have read the problem more carefully.