So, day 2 passed and the tasks were quite good again. I'm quite sad that I couldn't get the gold but it was a nice competition.
Problem 1 — Ephesus
You are given a string of N letters. Let's observe a k-partitioning of this string, that is we divide it in k parts (numbered 1, 2, ... k), and each of those parts is a substring of the string. The first part starts from the beginning of the string, the second starts immediately after the end of the first and so on. Every letter of the text is in exactly one of those parts and each part has at least one letter, that is the parts are non-intersecting, not empty and all of them together exhaust the given string.
Now you are asking the question "How many are the different k-partitions such that the k parts are strictly increasing in lexicographical order", that is the parts are such that the first is the smallest lexicographically, the second is the next smallest and so on. Let Xk be the answer for k. This problem is even harder : you must calculate the sum k*Xk with k being the values 1,2..N. That is you must calculate — (1*X1)+(2*X2)+...+(N*XN).
Let the string be mcyyak.
Then for k=1, xk=1; for k=2, xk=2 (_mc yyak_ and mcy yak); for k=3, xk=1 (_mc y yak_); for k=4, xk=0; for k=5,xk=0; for k=6,xk=0. So the answer is 1*1+2*2+3*1+4*0+5*0+6*0=8
Output the answer modulo 10^9+7.
Subtask 1 (5 points):
Subtask 2 (16 points):
Subtask 3 (36 points):
Subtask 4 (43 points):
Time Limit = 3s
Memory Limit = 1024MB
Sadly I thought this would be the hardest problem and left it last, having only like 40minutes for it. I ended up with just 5 points and didn't manage to get any better solution. The real solution is some kind of DP in O(N^2) that I believe uses LCP and some tricks for fast summing and calculations.
Problem 2 — Fairy Chimneys
There is a graph with N vertices. There are edges between some of the vertices. However, edges (bridges) are quite weak so once you go through an edge it is broken and can't be used further. The value of a vertex is the amount of vertices you can reach and go back to the initial vertex.
There are Q queries of two types:
Add "a x y" : Builds a bridge connecting x,y. Query "q x" : asks for the value of vertex x.
Given N and Q queries your task is to find the answers of all queries.
Let N=5. Suppose we have the following connections — "a 1 2" ; "a 1 3" ; "a 1 4" ; "a 2 4" ; "a 4 5". Then let's look at a few queries. Suppose we get "q 1". The answer would be 3, since the vertex 1 can reach vertices 1,2 and 4. The query "q 3" would be 1, since 3 can reach only itself (using no bridge). Then suppose we have "a 3 2". Now the query "q 3" would give us 4 since vertex 1 can now reach 1,2,3 and 4.
Subtask 1 (14 points):
Subtask 2 (18 points):
Subtask 3 (23 points):
Subtask 4 (10 points)
All queries of type "q" start after all bridges are built.
Subtask 5 (35 points)
Time Limit : 3s
Memory Limit : 256MB
a 1 2
a 1 3
a 1 4
a 2 4
a 4 5
a 3 2
It took my about 4 hours to solve this problem, my solution includes a few union finds, merging many vertices into one, keeping trees of connected components and my complexity is in total I believe a little bit better than O(NlogN), however in theoretical worst-case I think my solution may perform as O(N^2). During the competition I could make it worst-case O(NlogN), however I conjectured that it's really difficult to make such test that would make me solution perform badly, so I decided to try it and it got full score in 2~2.5s. I don't know the intended solution of the problem, however only me and one other person have full score on the problem.
Problem 3 — Mediterranean
The path between Antalya and Iskenderun is a long straight line with adjacent cities between 1km. There are N passengers and the i-th passenger wants to get on a bus at city Bi and get off the bus at city Ei. A bus travelling from city D to city A can take passenger i only and only if D<=Bi<Ei<=A.
You are given the cities N people will get on and get off the bus and the routes of M buses. Your task is to find the maximum number of people can each bus can take. The task is online. You are first given the pairs of cities of the N passengers. Then for each of the buses you are given two numbers d and a. The bus travels from city d+shift to a+shift. In the beginning shift is 0, and after each query shift takes the value of the answer of the query.
Take N=5. Let the pairs <Bi,Ei> of passengers are : <2, 8>, <4, 5>, <0, 6>, <1, 7>, <3, 9>. A bus travelling from city 3 to city 7 can take only one passenger (<4,5>), and a bus travelling from city 0 to city 6 can take two passengers. (<0,6>, <4,5>).
All Bi and Ei are unique.
Subtask 1 (9 points):
Subtask 2 (23 points) [not sure about this subtask]:
Subtask 3 (32 points):
Subtask 4 (36 points):
Time Limit = 3s Memory Limit = 256MB
In my opinion this was the easiest problem in BOI2014. It took me about 30-40 minutes to solve it and implement it. Let's imagine that we keep an array F, and when a passenger <B,E> comes we say that F[B]=E. Now suppose a bus from L to R comes. What we actually want to find is the amount of numbers in F on indices between L and R that have value equal or less than R. Obviously that would give us the correct answer. Now this observation is enough for all except the last subtask since there is a known tree solution that works in O(log^2 N) per query for the described types of queries. To improve it we can use the fact that we do not have updates. Suppose we have sorted all people in increasing end of their interval, that is in increasing E. Now instead of saying that F[B]=E, we will simply do F[B]++, that is increase F[B] by 1. However we will do that in a persistent segment tree that keeps sums of intervals. Now suppose a bus from L to R comes. Well then we will simply find the version of the persistent tree where only all passengers with ending less than or equal to R have been added (there will be such since we add them in increasing order of their end). We can do that by binary in O(logN). Now in that tree we will simply do a sum query in [L,R] and that is our answer. Complexity is O(logN) per query, so O(MlogN) in total. To avoid using 10^9 memory you have to either compress the input or use dynamic tree (create only vertices that you use). I used dynamic tree and passed in 247MB.
So I got a total of 205 points on the second day, but sadly I was about 50 points short from the golds, and will most likely be the first silver medalist.
P.S. They extended the golds and luckily I got gold.