ipaljak's blog

By ipaljak, history, 2 weeks ago, In English,

Hi all,

Croatian Olympiad in Informatics (COI) represents the first major step towards forming the Croatian IOI team. This year's edition will take place on Sunday, April 14th at 15:00 UTC. As usual, we will host an online mirror of the contest for which you can register here.

The contest format is similar to IOI — it lasts for 5 hours and will contain 3 to 5 problems. The test cases for each problem are divided into subtasks of varying difficulties so it is possible to receive partial score. The contestants will be able to receive full feedback on a limited number of submissions per task.

The contest is organized by Mr. Malnar and the problemset was prepared by satja, DBradac, mislav_bradac, tonkosi and myself. We hope you'll enjoy the contest.

See you on Sunday!

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

»
2 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

"The contestants will be able to receive full feedback on a limited number of submissions per task."

Can you give more details about this? Sounds like a new feature. How many submissions are allowed per task, and how many of those can get full feedback?

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

    Most likely, each contestant will be able to submit at most 10 submissions for each task and will receive full feedback for all of those. The submission which received the highest score is the one that counts.

    The exact details will be visible in the judging system before the start of the contest and may differ slightly from the information above, so take that with a grain of salt.

»
2 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

I think the registration link is not correct.

»
2 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by ipaljak (previous revision, new revision, compare).

»
13 days ago, # |
  Vote: I like it +16 Vote: I do not like it

It's April 14th, right?

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

    Yeah, don't know how I messed that up, thanks :)

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

Auto comment: topic has been updated by ipaljak (previous revision, new revision, compare).

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

Reminder: less than 50 minutes to start

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

Is it open to discussion now?

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

Can anyone explain me the solution of problem "Tenis" ? :((

»
11 days ago, # |
  Vote: I like it +2 Vote: I do not like it

Would any kind user mind posting 2-3 sentences / code for their solutions? It would be very much appreciated, thank you!

»
11 days ago, # |
  Vote: I like it +59 Vote: I do not like it

Hi all, here are brief descriptions of the solutions.

Segway (author: satja)

Let's call any moment when a racer reaches an accelerator (using it or not) an event. We will process events in chronological order using a set. For every accelerator we store the number of racers who have already passed its beginning. Total complexity $$$O(NM \log(NM))$$$

Ljepotica (author: ipaljak)

Let $$$f(X)$$$ denote the sum for all valid sequences less than or equal to $$$X$$$. We need to calculate $$$f(B) - f(A-1)$$$. We will calculate $$$f(X)$$$ using dynamic programming. Our state is the following $$$(i, k, smaller, last)$$$ with the following meaning: the current position (i.e. depth in the tree), the number of times Ena changed her opinion about what left means, whether the constructed prefix is already smaller than $$$X$$$ and current Ena's opinion on what left means. Total complexity $$$O(NK)$$$.

Izlet (author DBradac)

Let $$$f(u, v)$$$ denote the number of different colors on the path from $$$u$$$ to $$$v$$$. Clearly $$$f(u, u) = 1$$$ and $$$f(u, v) = f(v, u)$$$. Let 1-comp denote a maximum (i.e. cannot be extended) set of nodes which all have $$$f(u, v) = 1$$$. These can be found using a dfs and they surely form a connected subtree of the original tree. For every 1-comp we will choose one node, connect all the others directly to it and ignore them from now.

Suppose now that for every $$$u \neq v$$$ we have $$$f(u, v) \geq 2$$$. Define a 2-comp as a maximum set of nodes which all have $$$f(u, v) = 2$$$ for $$$u \neq v$$$. These can be found quickly in the following manner. Find a pair of nodes $$$(a, b)$$$ such that $$$f(a, b) = 2$$$ and there is no 2-comp already found containing both of them. Add to the 2-comp all nodes $$$c$$$ such that $$$f(a, c) = f(b, c) = 2$$$. It's easy to see this is a maximum 2-comp. Also, note that a 2-comp forms a connected subtree of the original tree.

Any two different 2-comps can have at most one node in common. Suppose the contrary, since they are both connected subtrees, they must share an edge and therefore have the same two colors. So, they are actually the same 2-comp.

Now we can connect the nodes in each 2-comp arbitrarily as long as they form a connected subtree.

Once we have constructed the tree, finding a valid coloring is easy. Run a dfs/bfs. When choosing the color of a new node $$$v$$$, run dfs from it through all the nodes colored so far. When the number of distinct colors doesn't increase, we have found a node with the same color as $$$v$$$. If we haven't found any, color $$$v$$$ with a new color. Total complexity $$$O(n^2)$$$.

Using induction we can prove the correctness of the algorithm, i.e. that we can connect every 1-comp and every 2-comp arbitrarily.

Tenis DBradac

Claim 1: It's easy to see that if $$$x$$$ can win a tournament and $$$y$$$ can beat $$$x$$$, then $$$y$$$ can also win a tournament.

Let $$$S$$$ denote the set of players that can win a tournament. Also let $$$T$$$ denote the minimum nonempty set of players such that no player not in $$$T$$$ can beat a player in $$$T$$$. We claim that $$$S = T$$$.

First we show that $$$S \subseteq T$$$. By definition of $$$T$$$, no player outside $$$T$$$ can win the tournament.

By claim 1 we have that no player outside $$$S$$$ can beat a player in $$$S$$$. By definition of $$$T$$$ we have $$$|T| \leq |S|$$$. Suppose that there exists $$$x \in T, x \not\in S$$$. Since $$$|T| \leq |S|$$$, there is $$$y \in S, y \not\in T$$$. By defintion of $$$T$$$, $$$y$$$ can not beat $$$x$$$, so $$$x$$$ can beat $$$y$$$. But then by Claim 1, $$$x \in S$$$ which is a contradiction. We have $$$T \subseteq S$$$ and therefore $$$S = T$$$.

Let $$$M(p)$$$ be the maximum rank of a player $$$p$$$ among all surfaces. Let $$$C(k)$$$ be the number of players $$$p$$$ with $$$M(p) \leq k$$$. It's easy to see that $$$C(k) \leq k$$$. Let $$$t$$$ be the minimum number such that $$$C(k) = k$$$. Then $$$T$$$ is the set of all players $$$p$$$ with $$$M(p) \leq t$$$. Let $$$D(k) := k - C(k)$$$. Finding $$$t$$$ corresponds to finding the first zero value in a nonnegative array of values $$$D$$$. Each update changes only two values of $$$M(p)$$$ so we can use a segment tree to manage these updates efficiently. Total complexity $$$O(N + Q \log N)$$$.