### witua's blog

By witua, 7 years ago, CodeChef invites you to participate in the March Cook-off 2015 at http://www.codechef.com/COOK56.

Time: 22nd March 2015 (2130 hrs) to 23rd March 2015 (0000 hrs). (Indian Standard Time — +5:30 GMT) — Check your timezone.

Details: http://www.codechef.com/COOK56/

Registration: Just need to have a CodeChef user id to participate.

- Problem Setter : Vitaliy Herasymiv
- Editorialist: Amit Pandey
- Problem Tester: Istvan Nagy
- Russian Translator : Sergey Kulik
- Mandarin Translator: Gedi Zheng

It promises to deliver on an interesting set of algorithmic problems with something for all.
The contest is open for all and those, who are interested, are requested to have a CodeChef userid, in order to participate. By witua, 7 years ago, translation, CodeChef invites you to participate in the August Cook-off 2014 at http://www.codechef.com/COOK49.

Time: 24th August 2014 (2130 hrs) to 25th August 2014 (0000 hrs). (Indian Standard Time — +5:30 GMT) — Check your timezone.

Details: http://www.codechef.com/COOK49/

Registration: Just need to have a CodeChef user id to participate.

- Problem Setter : Vitaliy Herasymiv
- Problem Tester and Russian Translator : Sergey Kulik
- Editorialist: Constantin Sokol
- Mandarin Translator: Gedi Zheng & Minako Kojima

It promises to deliver on an interesting set of algorithmic problems with something for all.
The contest is open for all and those, who are interested, are requested to have a CodeChef userid, in order to participate. By witua, 9 years ago, translation, Hi!

##### 289A - Polo the Penguin and Segments

Solution. First of all, we need to count, how many integers are inside given segments at the beginning. Since they don't intersect and even touch, no integer point can belong to more than one segment at the same time. This mans that starting value of segments is .

If k divides p, then answer is 0 — we don't need to do anything, it's already done. But if it's not true, we need to know the minimal number of turns to make k divisor of p. Since we can in single turn increase p by 1 (by decreasing the left point of the leftmost segment), this number is equal to .

Note. Note that just output is not enough: you need to pay attention for case when , or just output .

##### 289B - Polo the Penguin and Matrix

Solution. First of all, we need to know when the answer is -1. For that you should notice that after any operation on number z, value doesn't change. Indeed, . This means that there is not answer if there are two different points for which is diffrent.

Now we can transform our problem a bit. We can just write down all integers from matrix n × m to one array b of size k = n × m and sort them all in non-decreasing order. It is not hard to notice that in some of the optimal solutions, all number are at the end equal to one of the number for starting array. But also, it is optimal to make all number equal to (median element). Why to median? Suppose that we make all numbers equal to non-median element with index x. Then if |x - (k - x)| > 1 (i. e. from one side there are more elements than from another + 1). So, by moving out element more to median, we can make result better.

After we know, to which number we should bring all, the answer is just , divided by d.

Note. There is also full solution with complexity O(n2m2).

##### 288A - Polo the Penguin and Strings

Solution. To solve this problem we need to find out some contruction of resulting string. But first of all, we need find out when there is no result. Obviously, if k > n, there is not result — you cannot build string of length n with more than n characters. Another one case is when k = 1 and n > 1 — there is no answer in that case also.

Consider that k = 2. It's really easy to see that answer for such case is a string of form abababab.... To construct string for k > 2 you need to add some extra characters — c, d, e.... To make string lexicographically smallest, you need to add that characters as close to the end as we can. And the best bet here is abbabab...abacdefgh.... So, we need just to add characters c, d, e, f... (i. e. k - 2 characters from c) to the end of the string.

##### 288B - Polo the Penguin and Houses

Solution. Since k ≤ 8 you can solve this problem using brute force. This means that you can recursively construct all possible kk possibilities of first k assignments. (For k = 8 this is equal to 16 777 216.) For each of that assignments you need to check whether it is correct or not (by problem statement). Ths can be simply done using loops.

When you know the number of assignment for the first k tables (let it be f(k)), all you need to do is to count the number of assignment for the rest n - k plaques. Since there should bo no path to 1, there should be no path to any of first k houses, so at each plaque for houses from k + 1 to n there can be any number from k + 1 to n, inclusive. There are (n - k)n - k such possibilities. And hence the total answer is f(k)(n - k)n - k.

Note. There also exists solution with dynamic programming, and also there exists formula for f(x). You can read about it more here, here и here.

##### 288C - Polo the Penguin and XOR operation

Solution. Since we need to maximize the result, we need to find such permutation, for which the least number of bit disappear. (We consider bit disappeared if it was 1 both in i and pi, so in it is 0). It turns out that for each n there is such permutation that no bit disappear. How to build it? We will be solving problem by iterations while n > 0. On each iteration, we need to find the biggest (the leftmost in binary representation) bit which is not 0 in binary representation of n and denote it position (bits are numbered from 0) by b. Now we need to find integer m — minimal integer from 0 to n, inclusive, such that b-th bit is also 1 in it. After that you can see (look image below), that at no bit disappear, at no bit disappear, ..., at no bit disappear. So, it is good to assign exactly that integers to our permutation, i. e. pm = m - 1 and pm - 1 = m, pm + 1 = m - 2 and pm - 2 = m + 1 and so on. After that assign value m - (n - m + 1) - 1 to n and go to next iteration. Now when we know how to build permutation and that no bit disappear, the value of the answer is equal to .

##### 288D - Polo the Penguin and Trees

Solution. As always in such problems, root our tree at some vertex, for example vertex with number 1. We need to find out, what will happen when we have already chosen one path. Obviously, after deleting all vertices and their edges from that path, tree will disintegrate in some set of trees. Denote their sizes by c1, c2, ..., ck, where k is the number of trees. Then the number of ways to choose the second path is equal to . This gives us O(n2) solution — just to brute force all pathes and count the number of second paths by this formula. We need to do it in O(n). To do so, dfs our graph and fix some vertex during dfs, we will consider this vertex as the last vertex in the first path. Now we need to find the sum of above formula for the rest of the vertex. Here you can separately solve this problem for all vertex inside subtree of current vertex and for the rest of the vertices. For subtree vertices, you can, after finding the answers for all vertices of subtree, find the answer for root of subtree. To do so, you need to iterate all edges from current vertex and sum up results for that vetices. Also you need to add the sum of values multiplied by the number of vertices in subtree, where di are all sizes of subtrees of vertices from current vertex, not including from current edge). You can use some partial sums of something like that to make it linear. For the rest of the vertices (not in subtree) it is actually similar, but a bit harder. Here you need to keep current result as a parameter of dfs and when you entering some vertex you should add some additional counts to the current sum (similarly as in first case).

Note. Also, you can find the number of bad pairs of pathes and subtract it from the total number. Also some divide and coquer solution exists, you can think about it.

##### 288E - Polo the Penguin and Lucky Numbers

Solution. In this problem there are a lot of different formulas, most of them are for optimizing solution and making it lenear. Editorial shows just a general idea because it's pretty hard to explain all of them and good for you to derive it by yourself. If you have any questions — write them all in comments.

Denote by a1, a2, ..., an all lucky number from segment. First of all, we need to do reduce the problem a bit. Let we have some fixed digit (pos, d), i. e. position of this digit is pos (from 0 from right to left) and value is d (4 or 7). Then, for all ai (1 ≤ i < n) such that pos-th digit of ai is equal to d, we need to add ai + 1 × d × 10pos to the answer. Now we can see that problem can be reduced to the following. For each fixed digit (pos, d) find the sum of all ai such that ai + 1 on the pos-th position has digit d. Obviously, we can solve the problem for 1..l and 1..r separately and then subtract the first from the second — that will be the answer.

How to find such sum among all lucky numbers of some length but less than some lucky number x? We will describe the general idea. Any lucky number, less than x has some common prefix with x, then one digit is less than the corresponing in x (i. e. it is 7 in x and 4 in another integer) and the rest of the digits are arbitrary. So, by iterating all such positions where is the first digit less than in x, we can, using the fact that the rest of the digits are arbitrary and some formulas and precomputations, compute the results for each position and digit. Tutorial of Codeforces Round #177 (Div. 1) Tutorial of Codeforces Round #177 (Div. 2) By witua, 9 years ago, translation, Greetings!

Codeforces Round #177 takes place tomorrow at 19:30 by Moscow. I hope you all will take part and enjoy the problems.

Gerald, as usually, helps in preparings, Delinur translates all the problems for you. Thanks to them.

Good Luck!

Points distribution is standard:

Div1: 500 1000 1500 2000 2500

Div2: 500 1000 1500 2000 2500

Here are today's winners:

Div1:

Div2: Announcement of Codeforces Round #177 (Div. 1) Announcement of Codeforces Round #177 (Div. 2) By witua, 9 years ago, translation, Is starting right now. tc, srm,
By witua, 9 years ago, translation, ### 259A - Little Elephant and Chess

Obviously, the only correct rows are rows WBWBWBWB and BWBWBWBW. Only thing you need to do is to check whether each string is one of these. If yes then print YES, else print NO.

### 259B - Little Elephant and Magic Square

Since each number is less than or equal to 105, you can loop all possible a1, 1 values, the rest of cells can be calculated from this.

### 258A - Little Elephant and Bits

It's pretty easy to notice that you need to delete the first (from the left) 0-digit. The only catchy case is 111...111 — here you need to delete any of 1-digits.

### 258B - Little Elephant and Elections

First of all, lets think about the problem of finding array ci — the number of integers from 1 to m such, that the number of lucky digits is equal to i. It's pretty standart dynamic programminc problem, which can be solved with state [position][less][count].

It can be solved directly using DP, but to simplify a bit you can use brute force (recursion) to brute all possible assignments of numbers of lucky digits in for all paries (up to 9 digits). Now you can divide all parties in several indepentent groups, each of which should contain the same number of lucky digits. Consider that the party of Litte Elephant is with number 1. Than assignment for the first position should have more digits than the sum of the rest (because of the statement). Since all groups are indepented (because there is no number that can have different number of lucky digits, obviously) you can find the number of resulting assignments for each group and find the final result by multiplying these all numbers and taking modulo 109 + 7.

Consider that you have group of size t, each number of which should contain l lucky digits. That it's pretty easy to understand that the number of assignment is equal to (cl) * (cl - 1) * (cl - 2) * ... * (cl - t + 1).

### 258C - Little Elephant and LCM

The complexity of the possible solution is O(n * sqrt(n) * log(n)). You can see that statement lcm(b1, b2, ..., bn) = max(b1, b2, ..., bn) is equal to statement "All the numbers b1, b2, ..., bn must divide max(b1, b2, ..., bn)". You can iterate that max(b1, b2, ..., bn), let it be equal to m. Find all divisors of m and sort them — p1, p2, ..., pk. For each i between 1 and k you can find (using simple DP) the number of numbers aj that pi ≤ aj < pi + 1 (if i = k than pi + 1 = max(a1, a2, ..., an) + 1), denote it as qi. Then the reuslt is equal to 1q1 * 2q2 * 3q3 * ... * pqp, because for each of the q1 numbers there is 1 way to assign, for each of q2 numbers there is 2 ways of assignments, and so on. But you should notice that if doing this problem in such way, you need to garantee that there is some i such bi = m. Hance you need from the last multiplier (pqp) subtract (p - 1)qp — all the ways that there is no number equal to m.

### 258E - Little Elephant and Tree

Very useful thing in this problem is ordering all vertices in DFS order (preorped). After that any subtree can be represented as a some sequence of continuous vertices. Consider that we have some fixed vertex v. Which vertices should be included in cv? Obviously, if in the path from the root to v is some non-empty vertex (i. e. such that has at least one integer in its list) than each vertex from substree v should be included in ci, but since we now working with preorder traversal of the tree, we consider that every vertex from some segment [lv, rv] must be included to ci. More generally, let for each vertex keep some set of segments (lk;rk). If on the i-th operation we have two vertices a and b, we add segment (lb;rb) to vertex a, and (la;ra) to vertex b. Also for each vertex i (i = 1..n) we add segment (li;ri), where (li;ri) is a segment in our preored traversal for subtree i. After that, you can see that, if we unite all segments from all vertices on the path from the root to some vertex v, we find the result for v, which will be the size of the resulting set.

So now we need some data structure that would support three operations: add(l, r), subtract(l, r), count(). The first one should add 1 to all positions from l to r, inclusive. The second should subtract 1 from all positions from l to r, inclusive. The last should count the number of non-zero element. This all can be done either with segment tree or sqrt-decomposition. Tutorial of Codeforces Round #157 (Div. 1) Tutorial of Codeforces Round #157 (Div. 2) By witua, 9 years ago, translation, Hi all,

Next Codeforces Round, which is with number 157, will take place tomorrow. I'm an author of it, it is my 7th round at CF. Thanks alot to Gerald for helping in preparings.

Scores distribution in both divisions is 500-1000-1500-2000-2500.

Good Luck!

Top-7 Div1:

Top-4 Div2:

Thanks!

Editorial (currently only for Div2). Announcement of Codeforces Round #157 (Div. 1) Announcement of Codeforces Round #157 (Div. 2) By witua, 9 years ago, Hi!

I'm glad to invite you to my short contest on codechef.com on Sunday, 18th. (Check your time zone here.) I also want to note that Anton_Lunyov help my a lot in preparing of the contest, thanks to him.

In order to take part in the contest you should be registrated on the site, you don't need a separate registration for the contest. The competition will consist of 5 problems for 2.5 hours, using the standard ACM-ICPC rules.

After the contest you can discuss problems here and public all your wishes for the next contests.

Good Luck!

P. S. Please also note that CodeChef is now using much faster judging server! 2012,
By witua, 9 years ago, ### 221A - Little Elephant and Function

In this problems you should notice that the answer for the problem is always of the following form: n, 1, 2, 3, ..., n-1. In such case array will be always sorted after the end of the algorithm.

### 221B - Little Elephant and Numbers

Here you just need to find all divisors of n. This can be done using standart algorithm with iterating from 1 to sqrt(n). After that you need to write some function that checks whether two numbers has same digits. This also can be done using simple loops.

### 220A - Little Elephant and Problem

There are multiple possible solutions for this problem. For example, the following. Find the last index x such that there exists some y (y < x) (minimal possible) that Ax < Ay. Then you just need to try two possibilities — either swap Ax and Ay, or don't change anything.

### 220B - Little Elephant and Array

This problem can be solve in simpler O(NsqrtN) solution, but I will describe O(NlogN) one.

We will solve this problem in offline. For each x (0 ≤ x < n) we should keep all the queries that end in x. Iterate that x from 0 to n - 1. Also we need to keep some array D such that for current x Dl + Dl + 1 + ... + Dx will be the answer for query [l;x]. To keep D correct, before the processing all queries that end in x, we need to update D. Let t be the current integer in A, i. e. Ax, and vector P be the list of indices of previous occurences of t (0-based numeration of vector). Then, if |P| ≥ t, you need to add 1 to DP[|P| - t], because this position is now the first (from right) that contains exactly t occurences of t. After that, if |P| > t, you need to subtract 2 from DP[|P| - t - 1], in order to close current interval and cancel previous. Finally, if |P| > t + 1, then you need additionally add 1 to DP[|P| - t - 2] to cancel previous close of the interval.

### 220C - Little Elephant and Shifts

Each of the shifts can be divided into two parts — the right (the one that starts from occurrence 1) and the left (the rest of the elements). If we could keep minimal distance for each part, the minimal of these numbers will be the answers for the corresponding shift. Lets solve the problems of the right part, the left will be almost the same.

Let we have some shift, for example 34567 and the permutation A is 4312765 and B is 2145673, then shifted B is 4567321. Let we keep two sets (S1 and S2). The first will keep all the distances from integers in current left part to the corresponding positions in A (for the example above, it is \texttt{2, 4}). When you come to the next shift, all integers in S1 should be decreased by 1 (that is because all distances are also decreased by 1). But now some integers in set may be negative, when any negative integer occures (it always will be -1) you need to delete it from S1 and put 1 to the S2. Also after shifting to the next shifts, all integers in S2 must be increase by 1. After that, for any shift, the answer will be minimum from the smallest numbers in S1 and S2.

It was very useful to use standart "set" in C++.

### 220D - Little Elephant and Triangle

Let iterate all possible points that, as we consider, must be the first point. Let it be (x;y). Let the second and the third points be (x1;y1) and (x2;y2). Then the doubled area is |(x1 - x)(y2 - y) - (x2 - x)(y1 - y)|. We need this number to be even and nonzero. For first we will find the number of groups of points that are even, after that just subtract the number of groups with area equal to zero.

For the first subproblem, we need to rewrite our formula. It is equal to |x(y1 - y2) + y(x2 - x1)|. Since we know x and y and we just need to check parity, we can try all possible 24 values of parity of x1, y1, x2 and y2 (let it be d0, d1, d2 and d3, respectively). And check whether they will form a 0 after multiplications and taking modulo 2. If it froms a 0, then add to the answer value cxd0cyd1cxd2cyd3, where cxd is equal to the number of integers between 0 and n, inclusve, that modulo 2 are equal d. cyd is the same but in range [0..m].

Now we need to subtract bad groups — the ones that has the area equal to zero. This means that they will either form a dot or a segment. If it is segment, we can just iterate dx = |x1 - x2| and dy = |y1 - y2| instead of all 4 coordinates. Then the number of such segments on the plane will be (n - dx + 1)(m - dy + 1). Also for counting the number of triples of points on the segment you need to find the number of integer coordinates on the segment. It is well-know problem, and the answer is gcd(dx, dy) + 1.

This gives us, with some simple optimizations, and O(nm) solution.

### 220E - Little Elephant and Inversions

In this problems you can use a method of two pointers. Also some RMQ are required. If you do not know about RMQ, please, read about it in the Internet before solving this problem.

Firstly, map all the elements in the input array. After that all of them will be in range [0..n - 1]. We need to keep two RMQs, both of size n. Let the first RMQ be Q1 and the second Q2. Q1i will contain the number of numbers i in current left subarray. Q2i will contain the number of numbers i in the left subarray. Firstly, add all n number to the Q2. After that iterate some pointer r from n - 1 downto 1, by the way keeping point l (which, at the beggining, is equal to n - 1) Using RMQs, you can keep the number of inversions when you decrease r or l (using "sum on the range" operation). While the current number of inversions is more then k and l ≥ 0, decrease l. Then for each r the answer of correct l will be l + 1 (considering 0-based numeration).

This makes the algorithm working in O(NlogN) time with correct realisation. Tutorial of Codeforces Round #136 (Div. 1) Tutorial of Codeforces Round #136 (Div. 2) By witua, 9 years ago, translation,  Tomorrow, in 4 and half hours before the end of the summer (check your zone), Codeforces Round #136 will take place. I am the author of this round, it's my 6th contest on CF.

Gerlad Agapov (Gerald) is helping me in preparing the problems. Translations will be done by Maria Belova (Delinur). Thanks to them.

I hope you will like this round. The points distribution will be standart. Thanks!

7 user in the first division solved all 5 problems, here they are:

Meanwhile, in second division, Top-4 looks like this:

You can find the editorial of the contest here. Announcement of Codeforces Round #136 (Div. 1) Announcement of Codeforces Round #136 (Div. 2) By witua, 9 years ago, translation, ### 205A - Little Elephant and Rozdil

This problem was the simplest in the problemset. All you need to do is just to sort all distances (keeping track on all indices). If the first two distances are equal, just output "Still Rozdil", otherwise output the index of the first element of the array.

The complexity is O(NlogN).

### 205B - Little Elephant and Sorting

In this problem you need to notice the fact (which can be proven, but it is almost obvious) that if you are doing some operation for interval from l to r (inclusive), r must be equal to n. This is becuase when you add something to all right part the answer can't be worse. After that you need to go from left to right and greedly add appropriate number of turns.

The complexity is O(N).

### 205C - Little Elephant and Interval

It is well-known that for such problem you need to write function F(x) which solves the problem for the interval 0..x, and the answer then is F(r) - F(l - 1).

Now you need to write F(x) function. If x < 10, then answer is, of course, equal to x. Otherwise, let len be the length of x, x' — the integer x but without first and last digits, xi — the i-th digit of integer x (from left to right, starting from 0). Interate through all possible first digit d (which is the last at the same time) and through the length i of the number. Then if i < len - 2 or (i = len - 2 and d < x0) you need to add 10i to the answer. Otherwise, if i = len - 2 and d = x0 you need to add x' to the answer. Finally, if i = len - 2 and d = x0 and xlen - 1 ≥ d add 1 to the answer.

This problems also can be solved using DP.

### 205D - Little Elephant and Cards

It is nice to use the map structure in this problem, but you can solve it without map (using sorting and binary serach). Lets iterate through all possible colors that we have and suppose that this currect color is the one that will make our set funny. The minimal number through all this will be the answer. To find the minimal number of turns to make our set funny using current color we need to know two numbers: the number of cards with current color on the front side and the number of cards with the current color on back side (but not at the same time). Let it be integers a and b. Let m = (n + 1) / 2 — the minimal number of the same cards required to get the funny set. Then if a + b < m it is impossible to make set funny using current color at all. If a ≥ m then the answer is 0, otherwise the answer is m - a.

### 205E - Little Elephant and Furik and Rubik

This problem is to find the expected value. Important fact here is the linearity of the expected value. This means that we can for each element of the first strings find the probability that exactly this element will me matched with some other (but, of course, equal) from the second string. The answer will be the sum of all such probabilities.

Let the current character of the first string be the i-th character (1-based numeration). Firstly we try to solve problem in O(N2) time. Namely, as it was said above, we need to find the number of such pairs of substrings that i-th character (which is on probably some other position in substring) is the same as the corresponding character of the second substring. Iterate through all j (j ≤ i) such that Ai = Bj. The number of such pairs of substrings that have match in that characters is j(n - i + 1) (considering 1-based numeration). This is O(N2). And because we need to find the sum of such values for all possible j, we can rewrite it as Si(n - i + 1), where Si equals to the sum of all integers j (j ≤ i) that Ai = Bi. Array S can be simply computed in a linear time. Analogically you should process all indices to the right from i.

After we know the number of pairs of substrings with the match with the i-th character (let it be count), the probability is count / total, where total is the total number of pair of substrings (it can be found by loop or with some simple formula).

The comlexity is O(N).

### 204D - Little Elephant and Retro Strings

Firstly we should solve following subproblem: for each prefix find the number of it's fillings such that there is no consecutive block of k characters B. Let it be F(x), where x is the index in of the last character if the prefix. Assing F(x) = F(x - 1) * cnt, where cnt = 2 if Sx = 'X' and 1 otherwise. After such assing there may be some bad filling included to F(x). Since we suppouse that F(x - 1) is caclulated correctly, all bad filling must contain blocks of k charcters B only at the end of the prefix (they may be included only if substring Sx - k + 1..x doesn't contain characters W and character Sx - k is not B). So, if it's possible, we must subtract from F(x) value F(x - k - 1), because it's exactly the number of bad fillings.

With the same DP you should you calc the same values for suffixes (but this time changing B by W and vice versa).

Now we should carefully calculate the result in such way that now repeatings occur. Let iterate (from right to left) through all possible positions of the first blocks of k characters B (this means that we suppose that no block occur to the left). Using our DP we can simply find the number of fillings of all characters to the left from that block in such way that no another blocks of k characters B occur. Considering O(N2) solutions, we can iterate through all possible indexes of the begging of the last block of k characters W (again we suppose that this blocks must be the last and no another may occur to the right) and agin using our DP count the number of fillings to the right. We don't care what is between that blocks, so we just multiply answer by 2^(the number of characters X between blocks). But, since we are going from right to the left, we can just keep tracking on all possible last blocks and get O(N) solution.

### 204E - Little Elephant and Strings

To solve this problems we can use suffix array. More information about suffix arrays you can find in the Internet.

Firstly, concatenate all strings into the one separating consecutive strings by some unique characters (it was also useful to not use strings, but arrays of integers). For example, three strings abc, a, ab may be concatenated in the following way: abc#a@ab. Now we should build suffix array using this total string, this allows to us to sort all cyclic shifts of the string. After that each cyclic shift will either begin with additional character or the character from the input strings.

Notice now that to find the result we need to find for each cyclic shift (begging of which doesn't contain additional character) the largest size of it's prefix such that this prefix is substring of at least k different input strings. This value can be found by binary search, but for this we need some function F(x, len) which can answer the questions: how many input strings contain prefix of size len of x cyclic shift as a substring.

How to make F(x, len)? Look at all cyclic shifts, prefix of size len of which is equal to preifx of size len of x-th shift. Since all shifts are sorted lexicoraphically, this set of shifts can be represented as integral [l;r] of indices of shifts (1 ≤ l ≤ x ≤ r). How to find l and r? For each pair of consecutive shifts we can find it's greatest common prefix (using properties of suffix array). Than l and r can be found using RMQ. For l we need to know the rigthmost pair of shift (but to the left from x) that their greatest common prefix is less than len. Analogically we can find r. After that we have interval [l;r] and we need to find the number of different input strings that belongs to the shifts from l-th to r-th (actually, we need to find the number of different integer on interval). But, notice that we dont need the exactly number of different integers, we need to know just it is at least k or not. So let L[i] equals to the greatest j (j ≤ i) such that the number of different integers on interval [j;i] is equal to k. Then if L[r] ≥ l, obiously, interval [l;r] will also contains at least k different. So F(x, len) is done.

The only thing to done is to fill array L. This is pretty simple using set (but it is possible without it but using RMQ). We will go from left to righ at keep the indices of the last (the rightmost) k different integers in the set. If some integer comes, then (if it was earlier) we need to erase this previous index from set (if it was still in) and insert new current. While the size of set is greater than k, we should erase the minimal number from it. Then if in some position i the size of the set (after above changings) is equal to k, than L[i] is equal to the minimal number in set.

Since we O(N) times use binary search, and function F(x, len) works in O(logN) time, the total complexity is O(Nlog2N). Tutorial of Codeforces Round #129 (Div. 1) 129,
By witua, 9 years ago, translation, Hi!

Time brings to you next Codeforces round, this time it is with number 129. It will take place in 11.07.2012 at 19:30 (Moscow time). This time the problems are authored by me, Vitaliy Herasymiv. Long time ago I was the author of 4 Codeforces rounds, they were about lucky numbers. But, unfortunately, nothing is constant, so this time there will be no problems about lucky numbers.

A lot of help in preparing of the problems was from Gerald Agapov (Gerald), Alexander Kouprin (Alex_KPR), Vitaly Aksenov (Aksenov239), The problems were translated to English by Maria Belova (Delinur). Thanks to all of them.

I hope you will like this all.

Good Luck!

Div1:

Thanks all! The results are the following:

1. tourist (now tourist become first Codeforces target, congratulations to him)
2. winger
3. RAVEman
4. rng_58
6. bmerry
7. Shik

Div2: Announcement of Codeforces Beta Round #92 (Div. 2 Only) Announcement of Codeforces Round #129 (Div. 1) Announcement of Codeforces Round #129 (Div. 2) By witua, 10 years ago, translation, Hi!

I'm glad to invite you to my first short contest on codechef.com on Sunday, 20th. (Check your time zone here.) I should also note that Anton_Lunyov help my a lot in preparing of the contest, thanks to him.

In order to take part in the contest you should be registrated on the site, you don't need separate registration for the contest. The competition will consist of 5 problems for 2.5 hours, by the standard ACM-ICPC rules.

After the contest you can discuss problems here and public all your wishes for the next contests.

Good Luck! all, take,
By witua, 10 years ago, translation, DIV2-A Lucky Ticket:

In this problem everything is obvious: if all digits are lucky and sum of the digits of the first half equals to the sum of the digits of the second half, then answer is YES, in other case - NO. All this can be checked by single loop through all the digits.

You can see that, in worst case, the answer will be equal to 177777. It can't be greater. So, only thing you need is to write some function F(x) which will return mask of the x. After that you need to write such kind of code:

x = a + 1;

while (F(x) is not equal to b)

increase x;

and x will contain the answer.

DIV2-C DIV1-A Lucky Transformation:

You need to find two numbers: c47 (number of such positions i, that ai = 4 and bi = 7) and c74 (number of such positions that ai = 7 and bi = 4). After that the result will be max(c47, c74) (because you need to obtain min(c47, c74) swaps, the rest max(c47, c74) - min(c47, c74) are editings of digits).

DIV2-D DIV1-B Lucky Number 2:

Let we have some string result s. Let then delete all repititions, i. e. while we have some pair adjacent equal digits, we delete one of them. Let call formed string a root. In root there will be no adjacent equal digits, so |cnt(47) - cnt(74)| ≤ 1. So, if |a3 - a4| > 1, then answer is "-1". Now, if we would know the root, that will be used in our result, we can create result.

You can see, that if a3 = a4, then root must be 47474747...474 or 747474...747. If a3 < a4, then root is 74747474....74. If a3 > a4, then root is 474747...47. Length of the root must be such that it fulfill a3 and a4.

Now, when you have a root, you can build result. You just need to find first occurrence of 4 in root and insert the rest of 4 from a1 right next to that digit. To add the rest of 7, you need to find last occurrence of 7 in root.

The answer does not exits if, after constructing the root, you have used more 4 than a1 or more 7 than a2.

DIV2-E DIV1-C Lucky Different:

As you probably know, the number of lucky numbers in range [1;109] is 1022. We use this fact to solve problem. Let C[i] - number of occurrences of i-th lucky number in array a. Now we schould calculate DP with parameters DP[pos][cnt] - what is the number of subsequences that we use lucky numbers up to pos-th and our subsequence contains exactly cnt lucky number. If we are on state DP[pos][cnt] we can do two things: do not use pos-th lucky number (and do DP[pos+1][cnt] += DP[pos][cnt]) or use pos-th lucky (and do DP[pos+1][cnt+1] += DP[pos][cnt]*C[pos], because you have C[pos] of pos-th lucky number).

Now we need to find total result. To do that we iterate through the number of lucky numbers in our subsequence i. Then you need to multiple that number by C(countunlucky, k - i) (bin. coefficient), where countunlucky - number of unlucky numbers of sequence. Sum for all such i will be the total result.

DIV1-D Lucky Pair:

The main point of this problem is that number of lucky numbers in array is  ≤ 1000. Imagine that there is array of 1000 number in range [1;1000] each, and you want to find number of such pairs that there is no equal number in both segments. How to solve this problem? Let we have fixed left point of right segment, let it be i. The you should iterate through all j (i ≤ j) - right point of right segment. If you have some fixed right segment [i;j], then there is some set S of numbers that are in that right segment. So, segment [0;i - 1] will be divided in some subsegments that don't contain any number from S. For example, let S = {1, 2, 3} and segment [0;i - 1] is [2, 4, 2, 3, 6, 5, 7, 1], then there will be such subsegments (0-based numeration): [1;1], [4;6]. Of course, any subsegment of that subsegments will be good too: they dont contain any number from S, too. So, you can keep in set (or some structure like set) all good subsegments and keep number of all good subsegments in [0;i - 1]. When you iterate j from i to n - 1, you will add some numbers to S. When you add some number in S, you should add all occurrences of that number in subarray [0;i]. Notice, that when some number is already in S, you don't need to look at that numbers. So, for fixed i you should do O(n * logn) operations - any number from a[0;i - 1] will be added at most once to set

Now, we have not only lucky numbers. So, the problem is the same, but between number there are some "bad" numbers - in this case this are unlucky numbers. But, you can notice, that if we will fix only such i that a[i] is lucky and iterate j only such that a[j] is lucky then you can calculate result in the same way that in simpler problem. But that method allow you to only count such pairs that right one contains some lucky number. So you also need to count other ones. To do so you can fix some i - left point of right segment, such that a[i] is unlucky. Let F(i) equals to minimum such j (j > i) that a[i] is lucky. Then there are F(i) - i ways to expand right segment. All such right segments doesn't contain any lucky number. So any left segment will be good. And there are i * (i + 1) / 2 of such left segments (0-based).

DIV1-E Lucky Switch:

(with help of sjtu_pigoneand)

To solve this problem you need to handle segment tree with following information:

n4: number of 4-digits in node range.
n7: number of 7-digits in node range.
n47: maximum non-decreasing subsequence in range.
n74: maximum non-increasing subsequence in range.

When we reverse digits in some node we just swap(n4, n7), swap(n47, n74). When we update node we keep n4(father) = n4(left_son) + n4(right_son), n47(father) = max(n47(left_son) + n7(right_son), n4(left_son) + n47(right_son), n4(left_son) + n7(right_son)). Then for each count query result is n47. Tutorial of Codeforces Round #104 (Div. 1) Tutorial of Codeforces Round #104 (Div. 2) 104,
By witua, 10 years ago, translation, Hi!

Tomorrow, January, 22-nd at 11:00 o'clock (Moscow timezone), will have place Codeforces Round #104! The problemsetter will be me, Herasymiv Vitaliy (witua). Thanks a lot to Artem Rakhov (RAD) for help in praparing the problems and Maria Belova (Delinur) for problems translation.

I hope you will like this round.

See you tomorrow!

Points destribution today is:

DIV1: 500-1000-1500-2500-2500

DIV2: 500-1000-1500-2000-2500

Thanks to all, and here are the results:

Division 1:

Division 2:

Here is an editorial. Announcement of Codeforces Round #104 (Div. 1) Announcement of Codeforces Round #104 (Div. 2) By witua, 10 years ago, translation, In this problem you just need to loop through the integers i from 1 to n determine, is i lucky, if yes, then try, if n mod i = 0, then answer is "YES". If there are no such i, answer is "NO".

Notice, that answer is either one digit or -1. So, if there are no 4 and 7 digits, then answer is -1. Else, if there is more or equel number of digits 4, then answer is 4, else answer is 7.

Let generate all lucky number between 1 and 1010. Consider all segment [1;L0], [L0 + 1;L1], [L1 + 1;L2] ... Then the result equals to product of intersection of segments [1;L0] and [1;n] by L0 plus size of intersection of [L0 + 1;L1] and  [1;n] multiplied by L1 and so on.

Notice, that if there exits such i that i mod 2 = 0 and di = 4 and di + 1 = 7 and di - 1 = 4 then after that operation there will be a loop. So, let we simple do all operation from left ro right, and, when we will win our loop, just return a rusult (which variates by k mod 2 (k is one that leaves after operation from left side).

If n ≤ 14 let find out, is k more than n! or not? If yes, then return -1. Then, notice, that since k ≤ 109, then at most 13 elements from right (suffix) will change. So, element from left of this part (prefix) will not change (then we can just find a number of lucky numbers on than range). To find result for the rest of the permutation (suffix) we need to find k-th permutation of number from 1 to t (t is maximun integer, such that t! ≤ k). After we find that permutation, we can just loop through that permutation and count result.

Lei calculate arrays L and R. Let for all lucky i, L[i] = number of operation needed to move every segment, which's right end is to left from i to i. R[i] = number of operation needed to move every segment which left end is to right to i. How to calculate such array? Just use a sorting. Let arrange array A of pairs of integers, first - number, second equals to 0, if that number end of some segment, 1 if that number is lucky. Then, iterate from left to right, counting number of segment end we counted and si, si = si - 1 + (Ai - Ai - 1) * ci. The same way you can use to R. Now, to find the answer we must find (using method of two pointers of binary search) pair of indexes x and y, such that  i ≤ j, Lj + Ri ≤ k, Luckyj - Luckyi + 1 ≤  min_size_of_input_segment. Also, is this problem you should arrange function Mul(a, b), which return min(a * b, INF). Since simple multiplication overflows, then you can use multipling modulo 264 or double or min-long-arithmetic.

In this problem you can use many different algorithms, here is one of them. Obviously, number of different lucky number is 30, because Ai always is  ≤ 10000. Let Di - difference between minimum lucky number which is greater than or equal to Ai and Ai. Now, we need to have 5 (but you can use less number) of operation on D: Subtract(l, r, d) - subtract number d from all Ai (l ≤ i ≤ r), Minimum(l, r) - minumum number of all Di (l ≤ i ≤ r), Count(l, r) - how many times that minimum occared in that interval, Left(l, r) = leftmost occarence of that minimum, Set(i, d) - assign d to Di (Di = d). Now, we can do our operations. If our operation is "count", then we need to find minimum number d (d =  Minimum(l, r)), if it is equal to 0, then answer is Count(l, r, 0), otherwise, answer is 0. If out operation is "add", then we need to Subtract(l, r, d), but now some Di might be less than 0. So, while, Minimum(l, r)  ≤ 0, let j = Left(l, r), assign Dj new value (use Set(j, Dj')), which can be calculated with complaxity O(1).

Complexity of this algorithm is O(m * log(n) + n * log(n) * C), where C is equal to 30. Tutorial of Codeforces Beta Round #91 (Div. 1 Only) Tutorial of Codeforces Beta Round #91 (Div. 2 Only) 91,
By witua, 10 years ago, translation, Hello!

Wellcome to Codeforces Beta Round #91! This time, the author of the round will be me, Herasymiv Vitaliy (witua). Thanks a lot to Artem Rakhov (RAD) for helping in round preparing and Maria Belova for problems translation. I hope you will like problems.

Good luck!

Thanks all! And here are the winners:

Division 1:

Division 2:
Here is an editorial. Announcement of Codeforces Beta Round #91 (Div. 1 Only) Announcement of Codeforces Beta Round #91 (Div. 2 Only) 91, beta,
By witua, 10 years ago, translation, 1. Lucky Number (Div2 A)

In this problem you just need to find a number of lucky digits in n and output YES if it number is equal to 4 or 7, NO otherwise.

2. Lucky String (Div2 B)

To solve this problem you need to notice that result is a prefix of string abcdabcdabcd...abcd and output first n characters of this string.

3. Lucky Sum of Digits (Div1 A, Div2 C)

Let result number contains a digits 4 and b digits 7. Obviously, that a * 4 + b * 7 = n. Loop through all values of b. If we know b, we can calculate a, . Among all pairs (a;b) we need to choose one with a + b minimum. Among all that pairs we need to choose one with b minimum. Output will be an integer 444...444777...777, here number of digits 4 equal to a, number of digits 7 equal to b.

4. Lucky Probability (Div1 B, Div2 D)

Let L[i] - i-th lucky number, starting from 1 (L = 0, L = 4, L = 7...). At first choose first k lucky number, then second k numbers and so on. For each of that group lets find answer, result will be a sum of each of this probabilities. Let index of current first number if i, last - j (j = i + k - 1). Then we need to find intersection of intervals [pl;pr] and (L[i - 1];L[i]], and also [vl;vr] and [L[j];L[j + 1]), product of that values will be a number of ways in which p < v, similarly for p > v. Sum of all that values for each group will be a total number of ways, then result = total number of ways / ((pr - pl + 1) * (vr - vl + 1)).

5. Lucky Tree (Div1 C, Div2 E)

Solve this problem using dynamic programming. Consider that root of a tree is vertex with number 1. Let F(x) - number of vertex in subtree of vertex x for which there is a path containing lucky edge. We will calculate F(x) using recursion. If x is a leaf, than F(x) = 0. Else, if there is an edge from x that leads to y and this edge is lucky, then to F(x) we need to add C(y), otherwise we add F(y), here C(y) - number of vertex in subtree of y, including y. But, to solve this problem we need to know also F'(x) - number of vertex which are not in subtree of x and there exits a path from x to that vertex that contains lucky edge. For a root of tree, F'(x) equals to 0. We should go recursive from root, and if we are in vertex x now, we suppose that F'(x) is already calculated. If from x we can directly go to y and that edge is lucky, then F'(y) = C(0) - C(y), otherwise F'(y) = F'(x) + F(x) - F(y).

After that, result equals to .

6. Lucky Sorting (Div1 D)

At first, if our array is already sorted, just return 0. Otherwise, if there is no lucky number in A, then output  - 1. Otherwise, let B is sorted A (array from input). Now, for all numbers in A we know a final position in B. Let k is an index of minimal lucky number in A. If we want to place integer from position i to j, we need A[j] to be lucky number. If is not so, we just Swap(A[j], A[k]), then A[j] contains lucky number. After that we can Swap(A[i], A[j]) and number A[i] is on position j. So, to place one number to it's position in B, we need at most two operations and total number that replacements will be not more than n, so answer'll contain at most 2n operations.

7. Lucky Interval (Div1 E)

That is only onw variation of solution, there are diffrent other, which uses same thinking.

With constraints for a and b to 107 problem can be solved using KMP algorithm: consider a string F(1)F(2)F(3)F(4)...F(3 * 107). We need to find first occurrence after index a of string F(a)F(a + 1)F(a + 2)...F(a + l - 1). Complexity of that algorithm is O(a + l), obviously, that fails on time and memory. Lets try to optimize this algorithm using some facts from "Lucky numbers theory".

Split all number interval on block with sizes 100: [0;99], [100;199] and so on. Introduce a concept "class of block". Class number of a block equals to F(i / 100), where i - any number from that block. There are 8 different block classes. There are at most 6 consecutive blocks with same class. All that can be seen using brute force.

Note #1: if l ≥ 1000, then .

Proof: consider a string F(100 * k)F(100 * k + 1)...F(100 * k + 99). Number of different that strings is equal to number of different classes. For example, for first class that string looks like this:

00001001000000100100000010010000001001001111211211000010010000001001001111211211
00001001000000100100

for second:

11112112111111211211111121121111112112112222322322111121121111112112112222322322
11112112111111211211

and so on. According to the structure of that strings, different block (by classes) can't intersect (there'll be no match). Hence, any sequence of of consecutive blocks which contain at least two blocks of different classes will match only with the same sequence, so shift will be multiple of 100. Since there is no more than 6 consecutive blocks with the same classes, if l ≥ 1000 then, obviously, this interval will contain at least two blocks with different classes.

So, problem with l ≥ 1000 can be solved using KMP with complexity O((a + l) / C), where C equals 100, let function that do that is named Solve(l, r).

Now we need to solve problem for l < 1000. At first, let a' is minimal number that F(a') = F(a), F(a' + 1) = F(a + 1), ..., F(a' + l - 1) = F(a + l - 1), a' / 100 = a / 100, that can be done using brute force. Then result is the minimum of next numbers:

- r = Solve(a', a' + l - 1);
- Minimum r', for which r - r' <  = 1000, r' > a, F(r') = F(a), F(r' + 1) = F(a + 1), ..., F(r' + l - 1) = F(a + l - 1).
- Minimum a'' for which a'' > a, a'' - a ≤ 1000 and F(a'') = F(a), F(a'' + 1) = F(a + 1), ..., F(a'' + l - 1) = F(a + l - 1).

That solves the problem of some non-100-multiple shifts, but that may be a doubt. Consider input interval is in just one block with class C. Then, probably, it is better to go to block with class C + 1, for example (397;1) → (400;1). Actually, second point solves that problem, because if block with class C + 1 is before C (and only in that case we will choose C + 1), then next block after current have class C + 1. To proof this we can use this note (which can be proofed using brute forces):

Note #2: if there is two consecutive block, then absolute difference between they classes is not more then 1.

Hence, if after block C (in which input interval is) goes block with class C - 1, then we will go to block C before C + 1, otherwise we will choose it (C or C + 1).

Thus, problems solves by accurate analysis all moments. Complexity of solution is O((A + L) / 100), my solution works 1.5 sec. and use 250 mega bytes of memory.

There are also solution which decompose of blocks with sizes depentding on l, that one work faster. Tutorial of Codeforces Beta Round #84 (Div. 2 Only) Tutorial of Codeforces Beta Round #84 (Div. 1 Only) 84, beta,
By witua, 10 years ago, translation, Hello!

Welcome to Codeforces Beta Round #84I am Vitaliy Herasimov (witua) and I am an author of today's problems. Thanks to Artem Rakhov (RAD) and Pavel Kuznetsov (it4.kpfor the help and advices in preparing of the rounds, Maria Belova (Delinur) for the statements translation.

Good luck!

Contest is over! Congratulation to winners!

Division 1:
Division 2:
Here is an editorial. Announcement of Codeforces Beta Round #84 (Div. 1 Only) Announcement of Codeforces Beta Round #84 (Div. 2 Only) 84,
By witua, 10 years ago, translation, Div.2 – A Football

In this problem you must find longest substring consisting of equal characters and compare it with 7.

Div.2 – B Lucky Numbers - 2

If the length of input number |N| is odd, then, obviously, resulting number will have length |N|+1 and will be like this: 4444…7777, at first (|N|+1)/2 digits 4, then the same number of 7’s. If the number has even length, then, probably, resulting number will have size |N|, or |N|+2. So, length of the resulting number will have not more than 10 digits. So, we can recursive generate lucky numbers with size <= 10, take the smallest super lucky number which is greater than or equal to N.

Div.1 – A, Div. 2 – C – Hockey

Let B[i] = true, if character in position i is in some substring of W which is in dictionary. For each B[i] = true, do next:

·         If S[i] = letter and letter = ‘a’, then S[i] = ‘b’,

·         If S[i] = letter and letter != ‘a’ then S[i] = ‘a’;

·         If S[i] != letter, then S[i] = letter.

Div.1  - B. – Lucky Number

Notice, that answer will looks like this: to some position result will be equal with input string (that part must be lucky), next digit well be greater, the rest of digits are not important. That guarantees us that result will be greater than or equal to N. As rightest this position will be as number will be lesser. Some of the positions may not be ok to us. Let chosen position is i. Left part must be lucky. If S[i] < ‘4’, we can assign S[i] = ‘4’, then fill minimally right part. If S[i] < ‘7’, we can assign ‘7’ to it, like in prevision case. Call position i ok, if absolute different between number of ‘4’ and ‘7’ in part from 0 to i, inclusive is not more than n-i-1. If we chose some rightmost position, which is ok, now we must fill right part. How to do it? If we can assign to some position (we will fill them from left to right) ‘4’ and this position is still ok, then we place ‘4’,  else we assign ‘7’. If there is no ok positions at all, resulting number will looks like this: 4444…7777, when number of digits 4 = number of digits 7 = (|N|+2)/2.

Div.1 - C, Div.2 - D – Volleyball

At first in this simple problem you need to find shortest path between all pair of junctions. That can’t be done using O(N^3) algorithms, so you must use Dijkstra algorithm to find this in O(N*N*logN) time. Next part of this problem is to create new matrix, G[i][j] = C[i], if D[i][j] <= R[i], else G[i][j] = INF. Here D[i][j] – length of shortest path between I and j. So, result is shortest path between X and Y using matrix G. That can be done using simple Dijkstra algorithm.

Div.1 – D, Div.2 – E. Horse Races

Let we have array DP[x][y][z] – number of x-digits number if last lucky digit was on position y, bool z (0 or 1) – was the pair of lucky digits with less than or equal distance then K (call it lucky pair)? Now, let S – string which represent number N. Let F(x, y, z) – result for substring of first x digits, y – position of last lucky digit, z – (0 or 1) – was the lucky pair before? Try to assign some digits on position x. If this digit is less than S[i], then add to result for F(x, y, z) DP[n-x-1][yy][zz] (yy – updated position of last lucky digit, zz – updated bool for lucky pairs). If this digit is equal to S[i], add F(x+1, yy, zz). DP can be calculated simply. Let from state (x, y, z) we place some digit d on position x. Then, we can go to state (x+1, yy, zz). Again, yy and zz – updated parameters.

Complexity – O(T * |N}).

Div.1 – E – Lucky Country.

Let A[i] - sorted array of sizes of different connection components, C[i] – number of connection components of size A[i]. Sum for all C[i]*A[i] is equal to N. Size of A will be O(sqrt(N)).

Coming soon…

Solution #7

Let all C[i] = (2^k)-1, i. e. C[i] = 1 + 2 + 4 + 8 + … + 2^(k-1). Obviously, that if chose some subset of this powers we can get any number from 0 to C[i], inclusive. So, the problem now is next: For each A[i] is log(C[i]) things (cost of this thing is size of subset that create it), each can be used at most once. This is standard “Knapsack” problem (read this). Complexity of this algorithm is O(N * S), when S is the sum for all log(C[i]). If C[i] is not power of 2, then we must find maximal k, which (2^k)-1 <= C[i] and add C[i]-((2^k)-1) to set.

Sorry for my poor English! If you do not understand something – write in comments, please. Tutorial of Codeforces Beta Round #77 (Div. 1 Only) Tutorial of Codeforces Beta Round #77 (Div. 2 Only) 77, beta,
By witua, 10 years ago, translation, Hello everyone!

Welcome to Codeforces Beta Round #77. I am Vitaliy Gerasimov (witua) and I am an author of today's problems. Thanks to Artem Rakhov (RAD) and Pavel Kuznetsov ( for the help and advices in preparing of the rounds, Maria Belova (Delinur) for the problem translation and Codeforces (CF) for being.

Good luck! Announcement of Codeforces Beta Round #77 (Div. 1 Only) Announcement of Codeforces Beta Round #77 (Div. 2 Only) 77, beta,