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:
- Day 0: 2 July 2018 08:35 — 23:05 UTC (trial session)
- Day 1: 3 July 2018 02:35 — 23:05 UTC
- Day 2: 4 July 2018 02:35 — 23:05 UTC
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.
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.
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. :)
Bump~ TOKI OSN Open Contest 2018 Day 1 will be officially opened in less than 20 minutes!
Good luck and have fun, :3
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~ ;)
How to solve Day1 B?
Pretty much the same as this problem : link
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)?
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)).
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).
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! :)
How to solve Day 1 C ?
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
.
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)?
What did you do and how much did you get? :D
In the trial I got 270.
Day1 I solved the first problem and the
(here we have serious problems with electricity for two days and even on Tuesday 1AM all of the country didn't have electric).
Day2 I solved the third problem.
Some hints:
Observations:
Take an example of a clue 15M. You may color the first 14 cells with Black and the 15th one with Maroon. After doing this for all clues (clue 0 means to color all black on that row/column), we then may color the white (unblackened) ones with Maroon or Blue to connect the colored ones (Blue/Maroon from the clues).
We may solve independently the "areas" which are separated by black cells. Observe that each colored cell is adjacent to black cells, meaning they are on the edges of the areas.
Up to this point, we may color connected white cells on an area, with one of the color that minimize the number of the regions. This solution may give us about 60 points. The next small step is the most crucial part to give us the 100.
Since all colored cells are on the edges of the areas, we may first connect two same colored cells along the edges of the areas. In other words, if we go in a circle along the edges of the area and only observe the colored ones, color the path between the two same colored cells. You may see the following illustration.
The rests are done by coloring connected white cells on an area like before. (Well, there maybe some technical issues on this algorithm e.g. conflicts when coloring between two same colored cells. The current solution is to pick the one which makes the overall number of regions fewer).
When will the scoreboard be published?
As mentioned via email (I hope it's received by all participants), the score and rank will be announced on OSN 2018 official website on July, 8th 2018 11:00 UTC.
The results are avaible here https://osn2018.toki.id/open-results.html
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