Prabowo's blog

By Prabowo, history, 12 days 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. MarcoMeijer (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
  • +125
  • Vote: I do not like it

»
12 days ago, # |
  Vote: I like it +7 Vote: I do not like it

Inb4 0A is Hello World

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

Never mind, saw past problems

  • »
    »
    12 days 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.

»
9 days 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

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

    Will there be editorials available after the contest ?

    • »
      »
      »
      8 days 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 days 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.

»
8 days ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
8 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Why I can not register in TLX?

  • »
    »
    8 days 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.

    • »
      »
      »
      8 days ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      I mean I can not create an account in TLX.

      • »
        »
        »
        »
        8 days 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?

»
8 days 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 ?

  • »
    »
    8 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    Hint
    • »
      »
      »
      8 days 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.

    • »
      »
      »
      8 days 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.

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

    Problem link

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

Can anyone give me a hint on problem 1A?

  • »
    »
    7 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I think you have to solve them all individually

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

      With some kind of brute force in the bigger ones?

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

        This is how I did it:

        Solutions
»
7 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Will problems be available for upsolving?

  • »
    »
    7 days 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

»
7 days 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 days 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).