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.

New users please register here

- Problem Setter : Vitaliy Herasymiv
- Editorialist: Amit Pandey
- Problem Tester: Istvan Nagy
- Contest Admin: Praveen Dhinwa
- 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.

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.

New users please register here

- 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.

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(n²m²).

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 k^k 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 p_i, 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. p_m = m - 1 and p_m - 1 = m, p_m + 1 = m - 2 and p_m - 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 c₁, c₂, ..., c_k, where k is the number of trees. Then the number of ways to choose the second path is equal to . This gives us O(n²) 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 d_i 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 a₁, a₂, ..., a_n 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 a_i (1 ≤ i < n) such that pos-th digit of a_i is equal to d, we need to add a_i + 1 × d × 10^pos 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 a_i such that a_i + 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.

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:

1. wjmsbmr

2. peter50216

3. rng_58

4. XilinX

5. RAD

6. RomaWhite

7. eduardische

Div2:

1. alimiaomiao

2. yutaka1999

3. Alex.lap

4. zlqiszlq

Is starting right now.

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 10⁵, you can loop all possible a_1, 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 c_i — 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 10⁹ + 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 (c_l) * (c_l - 1) * (c_l - 2) * ... * (c_l - 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(b₁, b₂, ..., b_n) = max(b₁, b₂, ..., b_n) is equal to statement "All the numbers b₁, b₂, ..., b_n must divide max(b₁, b₂, ..., b_n)". You can iterate that max(b₁, b₂, ..., b_n), let it be equal to m. Find all divisors of m and sort them — p₁, p₂, ..., p_k. For each i between 1 and k you can find (using simple DP) the number of numbers a_j that p_i ≤ a_j < p_i + 1 (if i = k than p_i + 1 = max(a₁, a₂, ..., a_n) + 1), denote it as q_i. Then the reuslt is equal to 1^q₁ * 2^q₂ * 3^q₃ * ... * p^q_p, because for each of the q₁ numbers there is 1 way to assign, for each of q₂ 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 b_i = m. Hance you need from the last multiplier (p^q_p) subtract (p - 1)^q_p — all the ways that there is no number equal to m.

258D - Little Elephant and Broken Sorting

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 c_v? 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 c_i, but since we now working with preorder traversal of the tree, we consider that every vertex from some segment [l_v, r_v] must be included to c_i. More generally, let for each vertex keep some set of segments (l_k;r_k). If on the i-th operation we have two vertices a and b, we add segment (l_b;r_b) to vertex a, and (l_a;r_a) to vertex b. Also for each vertex i (i = 1..n) we add segment (l_i;r_i), where (l_i;r_i) 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.

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:

1. ftiasch
2. rng_58
3. shangjingbo
4. gawry
5. sandytea
6. Petr
7. peter50216

Top-4 Div2:

1. guliashvili
2. --Pavel--
3. HighFlow
4. mohammadrdeh

Thanks!

Editorial (currently only for Div2).

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!

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 A_x < A_y. Then you just need to try two possibilities — either swap A_x and A_y, 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 D_l + D_l + 1 + ... + D_x 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. A_x, 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 D_{P[|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 D_{P[|P| - t - 1]}, in order to close current interval and cancel previous. Finally, if |P| > t + 1, then you need additionally add 1 to D_{P[|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[12] 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 2⁴ 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 cx_d0cy_d1cx_d2cy_d3, where cx_d is equal to the number of integers between 0 and n, inclusve, that modulo 2 are equal d. cy_d 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. Q1_i will contain the number of numbers i in current left subarray. Q2_i 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.

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:

1. peter50216
2. yeputons
3. winger
4. rng_58
5. RAD
6. al13n
7. KADR

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

1. blue.boy
2. de_troit
3. lxyxynt
4. ilona

You can find the editorial of the contest here.

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, x_i — 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 < x₀) you need to add 10ⁱ to the answer. Otherwise, if i = len - 2 and d = x₀ you need to add x' to the answer. Finally, if i = len - 2 and d = x₀ and x_len - 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(N²) 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 A_i = B_j. 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(N²). And because we need to find the sum of such values for all possible j, we can rewrite it as S_i(n - i + 1), where S_i equals to the sum of all integers j (j ≤ i) that A_i = B_i. 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 S_x = '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 S_{x - k + 1..x} doesn't contain characters W and character S_x - 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(N²) 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(Nlog²N).

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
5. RAD
6. bmerry
7. Shik

Div2:

1. xiaoshua2
2. ahm.kam_92
3. HanzhongBall_Quanling
4. daidailanlan

You can read editorials here.

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!

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. 

DIV2-B Lucky Mask:

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 a_i = 4 and b_i = 7) and c74 (number of such positions that a_i = 7 and b_i = 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 |a₃ - a₄| > 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 a₃ = a₄, then root must be 47474747...474 or 747474...747. If a₃ < a₄, then root is 74747474....74. If a₃ > a₄, then root is 474747...47. Length of the root must be such that it fulfill a₃ and a₄.

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 a₁ 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 a₁ or more 7 than a₂.

DIV2-E DIV1-C Lucky Different: 

As you probably know, the number of lucky numbers in range [1;10⁹] 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(count_unlucky, k - i) (bin. coefficient), where count_unlucky - 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)

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:

1. tourist
2. dzhulgakov
3. PavelKunyavskiy
4. wuzhengkai
5. shangjingbo
6. ilyakor
7. Gerald

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:

1. tourist
2. 2222
3. PavelKunyavskiy
4. Petr
5. vepifanov
6. dzhulgakov
7. e-maxx

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

Read Div.2 – B

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

Traditionally I remain that answer is Result(0..R) – Result(0..L-1).

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)).

Solution #4 (by RAD)

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.