athin's blog

Invitation to TOKI OSN Open Contest 2018
By athin, history, 6 years ago, In English

Hi Codeforces community! :D

We're excited to invite you to TOKI OSN Open Contest 2018 -- 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, subtasked) 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 a provided timer button.

All three contests are now available on TLX (https://tlx.toki.id/competition). Please register in those contests. You may need to register for a TLX account if you do not have one already. (Note the new url -- we've got a brand new revamped UI for TLX!)

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

See you in the leaderboard! ;)

// P.S.: link to the previous year's contest blogpost can be found here.

UPD: The post-contest information is available here.

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

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

Heads up, especially for red coders:

This is actually our very first selection contest for Indonesian IOI 2019 team. On the same days, around 90 students will compete and the medalists (top 30 students) will advance to a long series of national training camps. Therefore, the problems will be easier -- but still challenging and fun to be solved. :D

As a comparison, it will be simpler than our last contest, TOKI Open 2018.

→ Reply
»
6 years ago, # |
  Vote: I like it +24 Vote: I do not like it

A friendly BUMP!

The trial session will be started in about 1 hour and 45 minutes. You may use this session to familiarize with the contest environment and all possible problem types. :)

→ Reply
»
6 years ago, # |
  Vote: I like it +17 Vote: I do not like it

Bump~ TOKI OSN Open Contest 2018 Day 1 will be officially opened in less than 20 minutes!

Good luck and have fun, :3

→ Reply
»
6 years ago, # |
  Vote: I like it +17 Vote: I do not like it

So how was the first day? ^^

Get ready for the last bump: TOKI OSN Open Contest 2018 Day 2 can be accessed in 1 hour! GLHF~ ;)

→ Reply
»
6 years ago, # |
  Vote: I like it +11 Vote: I do not like it

How to solve Day1 B?

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

    Pretty much the same as this problem : link

    → Reply
    • »
      »
      »
      6 years ago, # ^ |
      ← Rev. 2   Vote: I like it +16 Vote: I do not like it

      Thank you very much. I have only one more question. Is it true that for every pair (A, B) there exist only one correct string (if it even exists)?

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

        I think so, since we are forced to start with 1 and each step is forced (for a valid string, we won't ever reach a pair (x, x) with x > 1 and the initial state is (1, 1) (assuming the empty string is counted)).

        → Reply
        • »
          »
          »
          »
          »
          6 years ago, # ^ |
          ← Rev. 2   Vote: I like it 0 Vote: I do not like it

          Great, thank you. And I think the problematic state is (x + 1, x) because odd length adds x additional sequences (length more than 1) + start a new one (length 1).

          → Reply
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

TOKI OSN Open Contest 2018 has officially ended! Thanks everyone for your participation! :D

The post-contest will be posted soon along with the full result, the stats, etc. The problems are available for upsolving here.

Feel free to discuss the problems too! :)

→ Reply
»
6 years ago, # |
  Vote: I like it +11 Vote: I do not like it

How to solve Day 1 C ?

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

    One possible solution is to use dijkstra with state <city, excess distance from current ojek> of size O(VM). It will TLE though since the number of transitions is O(EM2) (Where M is the max distance of ojeks) resulting in an dijkstra.

    We can speed up the transitions if we consider both kind of roads separately:

    • Roads controlled by local ojeks

      In this case, we can either use the excess distance or discard the excess distance (allowing us to use online ojeks from a city).

      The former case is easy, as we can only use online ojek to get to the other end of the road.

      For the latter, note that we will need to try all possible distances to be covered by online ojeks (since we can use one from the starting city). However, observe that we only need to do this once for every city (just take the lowest cost to the city, which we can obtain from keeping track of when the cities first get popped from our dijkstra heap).

      The total transition for this case is O(EcontrolledM).

    • Roads not controlled by local ojeks

      In this case, Md (maximum distance of online ojeks) become irrelevant. Hence, there are two kinds of steps that we can do along the road only:

      a. Step of length one, cost = Cd (cost of online ojek)
      b. Step of length Mp, cost =

      Now, observe that we only need to do the first kind at most Mp - 1 times (and use the second kind for the rest of the steps, some details need to be taken care of though). One idea to implement this more efficiently is to also push the states (including the extra length-one steps, which I will refer to as temporary state) into our dijkstra heap and have another table to record the temporary states.

      The total transition for this case is O(EuncontrolledM)

    The total run time complexity is then .

    → Reply
»
6 years ago, # |
  Vote: I like it +28 Vote: I do not like it

Enjoyed solving problems, especially, Day2C took my all time for the contest but it worth I think.

How to get good mark from Day2B (Is it even possible to get 110)?

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

    What did you do and how much did you get? :D

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

      In the trial I got 270.

      Day1 I solved the first problem and the

      lights went off :P

      Day2 I solved the third problem.

      → Reply
  • »
    »
    6 years ago, # ^ |
    ← Rev. 2   Vote: I like it +17 Vote: I do not like it

    Some hints:

    • it may be impossible to get 11 points per tc, because:
    • there exists (unproven?) deterministic algorithm to solve the problem and get 10 points per tc with complexity of O(N2).

    Observations:

    Spoiler
    Spoiler
    Spoiler
    Spoiler
    → Reply
»
6 years ago, # |
  Vote: I like it +4 Vote: I do not like it

When will the scoreboard be published?

→ Reply
»
6 years ago, # |
  Vote: I like it +17 Vote: I do not like it

The results are avaible here https://osn2018.toki.id/open-results.html

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

    Thanks! Actually, there is already a post-contest infos for TOKI OSN Open Contest 2018 here (updated on the post too).

    Not only the results, you may also find the test data, the team, and other stats there. :D

    → Reply