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

Автор athin, история, 6 лет назад, По-английски

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.

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

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

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.

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

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. :)

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

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

Good luck and have fun, :3

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

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~ ;)

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

How to solve Day1 B?

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

    Pretty much the same as this problem : link

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

      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)?

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

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

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

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

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

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! :)

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

How to solve Day 1 C ?

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

    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 .

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

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)?

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

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

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

      In the trial I got 270.

      Day1 I solved the first problem and the

      lights went off :P

      Day2 I solved the third problem.

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

    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
»
6 лет назад, # |
  Проголосовать: нравится +4 Проголосовать: не нравится

When will the scoreboard be published?

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

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

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

    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