witua's blog

Codeforces Round #129 — Editorial
By witua, 12 years ago, translation, In English

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

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

Comments Comments (17)
| Write comment?
»
12 years ago, # |
  Vote: I like it +2 Vote: I do not like it

In "250A Little Elephant and Rozdil", It's no need to sort the distance.Just find ont the min_element and then check if it is unique, and the complexity is O(N) After all, it's such an easy problem that it is very easy solve. The O(N lg N) algorithm will not waste too much time, too.

→ Reply
  • »
    »
    12 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Yep, I agree. I did the O(N) solution but in retrospect the O(Nlog(N)) solution would have been much quicker to code. (Not that the O(N) solution took that long).

    → Reply
»
12 years ago, # |
  Vote: I like it 0 Vote: I do not like it

I am a beginner. Can anyone explain in a greater detail the problem "205C — Little Elephant and Interval".? While solving the problem during the contest, I worked it out that between 10^i and 10^(i+1), there are 9*10^(i+1-2) desired numbers. But, I could not translate it into solving it for any l<r. It would be a great help if you can explain both F(r)-F(l-1) and DP approach to solve this problem.

→ Reply
  • »
    »
    12 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    It's not easy to code but a little difficult to understand.And please be patient to my poor English, thanks.
    As this issue said " F(x) which solves the problem for the interval 0..x" and the problem is how to cauculate F(x)
    let x = k * x1 + x2, x1 = 10 ^ n, ~/A means any number 1...9
    For example , x = 3534 and x1 = 1000 x2 = 534
    A~A, AA, A are allowed(as you know) (t1)
    and 1~~1, 2~~2 are allowed too (t2)
    At last, to the most difficult part, 3003 ... 3533 are allowed so (3534 — 3003) / 10 + 1 is the answer of the last part( 00...53 ) (t3)

    Sum (t1), (t2), (t3), and you will get the answer.
    I think my method is the same to the author, but it seems that we're describing it in different ways.

    Thanks for your patience to my English(I seemed to say it twice)

    → Reply
    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      I understand your explanation before i grasp editorial =)) It helps me a lot

      → Reply
»
12 years ago, # |
  Vote: I like it +1 Vote: I do not like it

Can you please explain the DP solution of 205C — Little Elephant and Interval

→ Reply
  • »
    »
    12 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    To answer F(x), in my DP the state is D[i][j][k], 0 <= i <= 9, 1 <= j <= digits of max number, 0 <= k <= 1, is the total amount of this numbers which I can build, remaining j digits to fill and with the first non-zero digit i. The variable k tells if the numbers I have chosen are the same in x, for example if x = 3553 and I have chosen 30-- then k = 0 and the third number can be [0,9] but if I have chosen 35-- then k = 1 and I can only choose [0,5]. Then F(x) = D[0][digits of x][1].

    → Reply
    • »
      »
      »
      12 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      I couldn't understand properly..it would be very nice of you ...if you could elaborate a bit

      → Reply
      • »
        »
        »
        »
        12 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        The base cases are when j = 1, i.e i only have to fill one digit, in case i = 0 and k = 1 it means all the digits I have filled are 0 and I have to build a number with only a digit, in that case the answer is the last digit of x, there are to more base cases, when i != 0 and k is 0 or 1, in the first case D[i][1][0] = (i <= last digit of x), and the second D[i][1][1] = 1. The k = 0indicates that no matter what digit I choose now the number will be lower than x, and if k = 1 I can only use digits which are lower to the last digit of x.

        In the recursive case, I have to iterate through all possible digits I can use, in case k = 0 I can use whichever and otherwise I cant.

        Here is my code:

        ll D[10][20][2];
string w;

long long d(int i, int j, int k) {
    if (D[i][j][k] != -1) return D[i][j][k];
    if (j == 1) {
        if (i == 0 and k == 0) return 9;
        if (i == 0 and k == 1) return w[w.size() - 1] - '0';
        else if (k == 1) return i <= w[w.size() - 1] - '0';
        else return 1;
    }
    long long cont = 0;
    for (int e = 0; e < ((k == 0)?10:w[w.size() - j] - '0' + 1); ++e)
      cont += d((i == 0)?e:i, j-1, (k == 0)?0:e == w[w.size() - j] - '0');
    return D[i][j][k] = cont;
}

long long F(long long x) {
    memset(D,-1,sizeof(D));
    stringstream l; l << x;
    l >> w;
    return d(0,w.size(),1);    
}
        → Reply
    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Basically 'k' is a restriction on the current digit right? if k = 0, then we can fill the current digit from 0 to 9 if k = 1, then we can fill the current digit from 0 to digit[digit.length() — j] where digit is an array containing the individual digits of "R"

      → Reply
»
11 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Can someone explain the logic of probelm Little Elephant and Interval m not gettin it ??

→ Reply
»
11 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

My Dp solution for "C. Little Elephant and Interval" is similar to idea in this topic http://stackoverflow.com/questions/22394257/how-to-count-find-integers-between-large-a-and-b-with-a-certain-property

My code here : http://codeforces.net/contest/204/submission/6435651 But i get WA on Test 18, i test several times on my PC or some online IDE, the output should be 100000000000000008, but the judge output isn't it . Someone can help me determine the bug in my code ? Thanks in advance :).

P/s : I have found the bug, array dp must be dp[21][21][21] instead of dp[20][20][20] @@.

→ Reply
»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

actually there is a O(NlogN) solution for 204E — Little Elephant and Strings.

→ Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

If someone interested in DP solution for Div2 C, here it is: https://codeforces.net/contest/204/submission/86109648.

We need to calculate dp[len][first_dig][last_dig] — count of numbers length of len with first digit = first_dig, last digit = last_dig. After that we can calculate get(R) — cnt of numbers with first digit equal to last digit from 1..R. Be careful then num.size() == R.size()!

→ Reply
»
19 months ago, # |
  Vote: I like it 0 Vote: I do not like it

If anyone is interested in the maths / greedy approach for C. Here it is Submission.

I don't know why everyone is solving by dp when it can be solved with more ease.

→ Reply
»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Can anyone tell me why my approach isn't working for 129A? ~~~~~~~~ //this is code public static void main(String[] args) { try { FastReader in = new FastReader(); FastWriter out = new FastWriter();

long n = in.nextLong();
        long min = Long.MAX_VALUE;
        long idx = -1;
        Set<Long> set = new HashSet<>();
        boolean flag = false;
        for(int i=0;i<n;i++){
            long val = in.nextLong();
            if(set.contains(val))
                flag = true;
            if(val<min) {
                min = val;
                idx = i;
            }
            set.add(val);
        }
        out.println((flag)?"Still Rozdil":idx+1);

        out.close();
    } catch (Exception e) {
        e.printStackTrace();
    }
}

~~~~~~

→ Reply