Invitation to ICO Prep Contest 4 + Exun 2017 Prelims

Greetings everyone! I would like to invite you to the 4th Contest of the ICO Preparatory Series. The 4th Contest of the ICO Preparatory Series has been preponed to Monday, 20th November 2017 from 18:00 - 21:00 IST. The contest has been combined with the Exun 2017 Programming Prelims as described below.

Problem Setter: Shashwat Goel

Problem Tester: Aulene De

Editorialists: Shashwat Goel, Aulene De

Contest Link: www.codechef.com/ICOP1804 .

The contest will be unrated. The contest will consist of 5 problems, with difficulty ranging from Easy to Medium-Hard. (It will be much tougher than contest 3 as it was targetted at ZCO). A rough idea of the topics covered can be obtained from the Advanced CodeChef Scholarship Syllabus. While the contest is aimed at school students, it has a lot to offer for students preparing for the ICPC as well.

Update: The problems are ready and I am happy to inform you that we were able to cover a different classic concept in each problem and the contest will be great for educational purposes!

We are glad to announce that the 4th Preparatory Contest will be held in conjunction with the Programming Prelims of Exun 2017, the 22nd iteration of the annual interschool IT Fest held by Delhi Public School, R.K. Puram. As a result, some participating handles will consist of teams of 2 attempting to qualify for the finals to be held on Saturday, 25th November. The qualification for the finals is open to all school students in Delhi NCR provided they register here.

We hope you find the problems interesting and enjoy the contest!

alt text

4 Likes

The contest link is up and working! For contest reminders and updates follow the FB page.

@harrycoda Just curious to know if solutions and the problems will be made public or not ?, when the editorial will get published ?

P1:

Many alternate solutions exist to this problem. We will list one of them.
One can simply observe that if we divide a number repetitively by a number > 1, it will reduce to 0 in O(LogN) steps. Thus, we can simply store at each index the index of the next element that has value > 1 in the array. We jump over these from L to R and divide k, thus answering queries in LogK time after an O(N) Precomputation step.

P2:
The problem is simply a 3D extension of the classic Prefix Sum problem.
We can determine the sum for any cube with Top-Left-Out corner as
[x1, x2) x [y1, y2) x [z1, z2)

Px2, y2, z2 - Px1, y2, z2 - Px2, y1, z2 - Px2, y2, z1 + Px1, y1, z2 + Px2, y1, z1 + Px1, y2, z1 - Px1, y1, z1

P3:
A careful interpretation of the problem statement reduces it to a Longest Common Subsequence problem. Suppose a set of moves on any tree forms a string, we want to maximize the LCS for the 2 strings obtained. Now, since the trees are directed and rooted, we can obtain a fixed value for the subtree of any pairs of nodes (a, b) if a is in tree 1 and b in tree 2 starting at node a, b. If we take all children of a and b and make pairs out of them (ca, cb), the maximum starting at (a,b) will be the max of these (ca, cb) pairs and +1 if the value at a is equal to the value of b. We can do this with simultaneous DFS of the 2 trees with memoization…

P4:
The problem can be reduced to the following:
Since there are M employees and each have to be given some equal amount, with X < M remaining, we just need to find the number of integers y such that y mod M = X. This can be done using the following algorithm:
Denote the answer to the problem f(A, B). Note that f(A, B) = f(0, B) - f(0, A - 1) or what is the same f(A, B) = f(0, B) - f(0, A) + g(A), where g(A) equals to one if A is a possible value, otherwise g(A) equals to zero. Let’s solve the problem for the segment [0, n].
Here is described the standard technique for this kind of problems, sometimes it is called ‘dynamic programming by digits’. It can be realized in a two ways. The first way is to iterate over the length of the common prefix with number n. Next digit should be less than corresponding digit in n and other digits can be arbitrary. Below is the description of the second approach.
Let Zijk be the number of magic prefixes of length i with remainder j modulo m. If k = 0 then the prefix should be less than the corresponding prefix in n and if k = 1 than the prefix should be equal to the prefix of n (it can not be greater). Let’s do ‘dynamic programming’. Let’s iterate over digit in position i. Also we should check for k = 1 p should be not greater than corresponding digit in n. Now let’s see what will be the next state. Of course i’ = i + 1. j’ = (10j + p) mod m. Easy to see that . To update the next state we should increase it: Zi’j’k’ +  = Zijk. Of course all calculations should be done modulo 10^9 + 7. Finally we need the value with i = number of digits in the number, j = X and k = 0 or 1

P5:
The problem statement reduces to the following:
We have a directed rooted tree and at each node we have an array. Each node has an effective range Li to Ri and its value is defined as the maximum element value in the Range Li to Ri. We can do this easily using a Segment Tree at each node for Range Max Query. We can perform Update 1 on the arrays using Lazy Propagation on a segment tree and each time we perform this update, we have to reset the value for a node. If we can do this, all we need to do is find the subtree sum at node X, this can be done with Tree Flattening using a Segment Tree. We can do the whole problem with 2 segment trees, lets call one subtreesum[] and one nodesegtree[i] (segment tree at ith node for range max query). After each addition update or change in effective range update on nodesegtree[i], we make a point update on the subtreesum array to reset the nodes value to the new value after the update. A simple range query for subtreesum on the flattened tree can get us the answer.
You can find algorithms for RMQ, Lazy Propagation, Tree Flattening etc. easily on the internet. The problem required just interpret the statement and implement 2 segment trees efficiently. The complexity per query is logN. An alternate solution with Log^2N would have given TLE if one used a direct 2D segment tree implementation.