Invitation for IOI Training Camp (IOITC) Replay Contest #1

general
, ,
1

Competitive Programming is all about the thrill of pitting yourselves against other coders and seeing who comes out on top. And in general, there’s nothing quite as fun for our community as putting on our coding hats and flexing our fingers over our keyboards and getting down to solve an interesting problem.

But competitive programming, like every sport, also has its World Cups. And for the CP community, the International Olympiad in Informatics is one such event that we all look forward to, not only as players but also as spectators. An annual competition that began in 1989 in Bulgaria, the IOI has risen from its humble beginnings to become one of the largest worldwide competitions for school students that tests their skills in programming and problem solving.

Only the very best make it to the IOI Training Camps and eventually, the finals. Many of us have always wanted to see what the competition is like but the chance is given only to a select and deserving few. Fortunately for the entire community, CodeChef is bringing the Indian IOI Training Camp experience to you on our platform.

So what is an Indian IOI Training Camp? The Training Camp is probably one of the most enriching experiences any competitive programmer can have. The camp has two aims : it narrows down the pool of participants from a country from around 30 to 4 final participants, and it also trains and tests the participants so that they are ready for the big stage.

And it is this test that CodeChef is bringing to you. We are conducting a replay of the Indian IOI Training Camp, in the same format. There will be three challenging problems and a five-hour time limit for solving them. Three Team Selection Tests were conducted in May for the selection of Indian IOI team. This contest is the first among the three replays that we plan to conduct.

We’re sure you’re as hyped about this contest as we are. How do you take part? It’s simple, just register at CodeChef if you haven’t done so already, and check out the details below! We’re looking forward to seeing you all experience the thrill of the Training Camp selection tests.

The authors of the round are:

  • Arjun Arul (arjunarul), Praveen Dhinwa (dpraveen), and Sidhant Bansal (sidhant007)

The testers panel consists of:

  • Rajat De (rajat1603), Sampriti Panda (sampriti), Kushagra Juneja (kushagra1729), Swapnil Gupta (born2rule), Sreejata Kishor Bhattacharya (AnonymousBunny), Animesh Fatehpuria (animesh_f), and Arjun P (Superty)

Duration: 5 hours
Start Date: Friday, 22nd June, 2018 at 19:00 HRS (IST)
End Date: Saturday, 23rd June, 2018 at 00:00 HRS (IST)
You may check your timezone here.

Contest Link: https://www.codechef.com/IOITC181

Good luck!

Cheers,

Team CodeChef

6 Likes
2

Gentle Reminder: The contest starts under 30 minutes.

3

Will you move problems to practice?

4

When will you update ratings?

5

Where is editorial?

1 Like
6

These are brief solution ideas.

CYCLECOL

Take a spanning tree. The remaining graph must be bipartite, so color the tree and the remaining graph independently and let color of v be (color in bipartite graph, color in tree)

KPERFMAT

First you start out by finding a matching M. Then you check in O(m) time whether there is another matching M’ in this same graph (we’ll see how to do this later). Then, you call two recursive problems on G(V, E forced e) and G(V, E - e), where e is an edge which is present in M but not in M’.
By “E forced e” we mean force e = (u, v) to be in all the matchings in this recursive subproblem. So that’s basically deleting both u and v from the graph.
By “E - e” we mean force e = (u, v) to not be in any of the matchings in this recursive subproblem. So that’s basically deleting e from the graph.

So this way, every recursive call (except the very first one), is a graph and a perfect matching M already present in it.
So now the sub problem is to find another perfect matching M’, given a matching M. Or report that M is the only perfect matching in this graph.
We do this using alternating cycles. We call a cycle in the graph as alternating, if the edges of the cycle are alternatingly (in M), (not in M), (in M), (not in M), etc
We claim that M’ exists if and only if such an alternating cycle exists. The proof is very similar to the usual augmenting path proof. That is, if such a cycle exists, consider M’ to be symmetric difference of the cycle and M.
And if M’ exists, then the cycle would be the symmetric difference of M and M’.

So, given this claim, to solve the subproblem, you only need to search for an alternating cycle. This can be done in O(m) time. An easy way to think of this is to direct the matched edges one way, and the unmatched edges in another way and find a directed cycle in this directed graph,

So the total complexity is (number of nodes in the search tree * m) + time to find the very first perfect matching. You can see that we look at most 2k nodes in the search tree.
So it’s 2km + nm.
So total complexity is O(m(n+k))

CIRCINTE

We have intervals [l1,r1], [l2,r2],…[lm,rm] in clockwise order.
Now, binary search for the answer, and suppose the value is d.

Assume S1 = r1.
If r1+d < l2, then S2 = l2. Break (will explain this later).

if l2 <= r1+d <= r2, then S2 = r1+d. Continue.

If r1+d > r2, then we need to move our starting point anti-clockwise.
Let x1 = r1+d - r2. So, S1 now should become r1-x1.

So we keep doing this. Whenever the last selected point + d overshoots the next interval, we move our starting point anti-clockwise by that much.
But doing so, might fuck up some interval in the middle. ie. suppose I need to move the starting point by some x. But for some i, for which I had already found Si, Si - x might be < li. In which case this is invalid.

So, what we do, is keep track of minimum(Si - li) among all the Si that we have fixed so far.
This can be maintained easily in constant time.

So we just keep doing this.

If we end up setting till Sn, then we just check whether the distance between Sn and S1 is >= d. If yes, then we’ve found a soln with d. If not, d is not possible. That’s because you can only move S1 counter-clockwise, and assuming that it doesn’t ‘break’ any other Si, Sn will move the exact same distance counter clockwise, and hence the dist(Sn,S1) cannot be increased.

Now, if at any point, S(i-1) + d < li, then we break, because we claim that now, we can be sure that Si = li.
More precisely, if there is a solution using d, then there is a solution where Si = li.

Why is this true? Consider where S1 is, right now. We know that if the starting point in [l1,r1] is anywhere in (S1, r1], then it is invalid. Because we had started out with S1=r1, and brought it anti-clockwise till the current S1, and hence all of those in between values are invalid.
Now, for any starting point between l1 and S1, the greedy algo is going to place Si at li. So I might as well place it there.

So, once we have fixed Si, we just do the normal greedy from there. No need to worry about moving this starting point anymore. Just forget what we had done till now, and start a new greedy from Si = li
Manage

2 Likes
7

I have added some hints of the solution in an answer below.

8

The problems are moved to practice.

9

The ratings have been updated.

10

Can you elaborate a bit on the CYCLECOL solution please?

11

Assume the following property holds for a graph.

 For all the odd cycles in the graph if you remove, the graph is disconnected.

You can prove that such a graph will be 4 colorable. The idea is to take any spanning tree of the graph. Notice that the graph after removing the edges of this spanning tree will be a bipartite graph.

Proof: Assume the contrary, i.e. the remaining graph is not bipartite, i.e. it contains an odd cycle. Now, in the original graph, if you remove this cycle, the remaining graph is still connected, which violates the above-stated property of the graph.

Suppose, if you could partition a graph into two separate bipartite graphs (Note that a spanning tree is also a bipartite graph), then you can also get a 4 coloring in the graph. The idea is as follows. We know that a bipartite graph is bicolorable. Here we will color these two bipartite graphs separately and merge their colorings to get a 4 coloring. This is because a pair of (color1, color2) (where color1 and color2 are either 0 or 1) can be mapped to a single color in the range {0, 3}).

So, the final algorithm is as follows.

  • Find a spanning tree in the graph (you can always find because the graph is connected).
  • Consider the residual graph.
    • If the graph is bipartite, output the 4 coloring by using the above method.
    • Otherwise, there will be an odd cycle in the remaining graph. You output that odd cycle.
2 Likes
12

@abdullah768, I have explained the solution in bit more details. See my answer

1 Like
13

Also for k matchings problem the test cases weren’t in a very good way. since the output was either yes or no many people found out the test cases by submitting many solutions and binary searching the test cases based on verdict. And then they submitted the solution that would pass all the given testcases but wasn’t a solution by any means.
sol: https://www.codechef.com/viewsolution/18965740
It was a very bad idea to have 1 test case per file in a problem where the ans was yes or no.

1 Like
14

Where is the editorial?