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

Автор prabowo, история, 4 года назад, По-английски

Hello Codeforces community,

Similar to last year, we are excited to invite you to TOKI KSN Open Contest 2020 -- an online mirror contest for Indonesia national olympiad in informatics. This national olympiad is one of the stages required for our students to qualify to represent Indonesia in the International Olympiad in Informatics (IOI).

The contest is similar to IOI: 2 competition days (+ 1 trial session), each consisting of 3 IOI-style (partial, subtasks) problems to be solved in 5 hours. The schedule is as follows:

Each contestant can select any 5-hour window within the time range to do the contest for each competition day. Each contestant may start the contest any time within the time range, by clicking the "start" button.

All three contests are now available on TLX. Please register in those contests. You may need to register for a TLX account if you do not have one.

For more detailed information and rules, see our official website.

See you on the leaderboard!

UPD Thanks to everyone who participated! Our top 3:

  1. rama_pang (564 points)
  2. wiwitrifai (559 points)
  3. Meijer (556 points)

The rest of the scores can be found here.

You can upsolve the problems here.

We thank everyone who are involved:

We hope we can conduct the open contest again, and see you next year!

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

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

Inb4 0A is Hello World

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

Never mind, saw past problems

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

    As this is an early stage of our IOI selection, the tasks are expected to be simpler from IOI. This round will select around 30 people to advance to the next stage of the selection.

    And as of other OI type contests, it is intended to participate in the contest as an individual.

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

A friendly reminder that you can already start your 5-hour virtual of the Day 1 competition

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

    Will there be editorials available after the contest ?

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

      Yes

      You can also discuss the problems after each day of the contest is over

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

        When exactly will the editorial become available? I want to ensure that I'm not going to miss it, as everything else is already published.

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

          prabowo Is it only me who can't see the editorial or has it either not been created or not been uploaded yet? From what I have just noticed, there was no editorial last year whatsoever despite it being promised. I hope it won't be the case this year.

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

            There was an editorial for last year's contest, here is the link.

            Sadly, it's written in Indonesian and there are no translations of it AFAIK.

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

      There is no official editorial yet, sadly. However, we decided to make our own unofficial version, read more about it here.

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

The second day of the contest will be available in 30 minutes

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

Why I can not register in TLX?

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

Any ideas/hints on how to solve Problem 3 (Maintaining Distance) from Day 1 for max constraints ?

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

      This is my first time encountering a DP problem with backtracking , can you explain a little more or if its a common technique/optimization could you link to some resource.

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

      This is also my first time encountering a pure DP problem that doesn't need to output the backtrack but using backtracking observation.

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

    Problem link

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

Can anyone give me a hint on problem 1A?

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

    I think you have to solve them all individually

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

      With some kind of brute force in the bigger ones?

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

        This is how I did it:

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

Will problems be available for upsolving?

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

    Yes, all open contest results will also be available once our closing ceremony is over tomorrow

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

Can anyone check my solution to 2B? I messed up my implementation during the contest.

We can think of start and finishing point as pillars too, with an upgrade cost of infinity.
First we only think about horizontal movement. Suppose from a pillar $$$p_1$$$ we can reach $$$p_2, p_3, ...$$$. Then from there we reach some other nodes. If we keep doing this then we will visit a 'Horizontal Slice' of points. After processing all points, we will end up with some Slices, which are disjoint.

Screenshot-from-2020-10-15-11-54-20

We also do this for vertical movement, and create our 'Vertical Slices'.
Now we create 2 nodes for each pillar, a horizontal and a vertical one. Suppose a point $$$p$$$'s horizontal node is $$$H(p)$$$ and vertical node is $$$V(p)$$$.
For a horizontal node, We look at its horizontal slice, let the pillars be $$$p_1, p_2, ... p_c$$$. We add edges of weight 0 between every $$$H(p_i), H(p_{i + 1})$$$. Also do the same for every vertical nodes in their corresponding vertical slices.
Finally add edges $$$H(p), V(p)$$$ with the weight equal to the cost of that pillar. Now answer is shortest path between $$$H(s)$$$ and $$$H(f)$$$ or $$$V(f)$$$.

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

Auto comment: topic has been updated by prabowo (previous revision, new revision, compare).