prabowo's blog

By prabowo, history, 4 years ago, In English

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!

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

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

Inb4 0A is Hello World

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

Never mind, saw past problems

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

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

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

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

    Will there be editorials available after the contest ?

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

      Yes

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

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

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

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

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

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

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

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

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

Why I can not register in TLX?

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

    If you were trying to register for the day 1 contest, unfortunately, the registration is already closed. Only day 2 is currently available.

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

      I mean I can not create an account in TLX.

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

        Could I have more details on this? What error did you encounter when registering?

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

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

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

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

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

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

    Problem link

    First step
    Next step
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Can anyone give me a hint on problem 1A?

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

    I think you have to solve them all individually

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

      With some kind of brute force in the bigger ones?

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

        This is how I did it:

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

Will problems be available for upsolving?

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

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

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

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

    I did the same and got accepted. But i made the upgrade cost of f equal to zero. This way the answer is the shortest path between H(s) and H(f). This is my code: https://pastebin.com/PjJquisX

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

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