NALP's blog

Codeforces Round #106 (Div. 2) Tutorial
By NALP, 13 years ago, translation, In English

149A - Business trip

First, it is clear that if the sum of all numbers ai is less than k, then Peter in any case will not be able to grow a flower to the desired height, and you should output <<-1>>.

Secondly, it is easy to see that if we want to choose a one month of two, in which we watered the flower, it is better to choose one where the number of ai is more. Thus, the solution is very simple: let's take months in descending order of numbers ai and in these months water flowers. As soon as the sum of the accumulated ai becomes greater than or equal to k — should stop the process, the answer is found.

149B - Martian Clock

In this task required only the ability to work with different numeral systems. Let's try to go through numeral bases, each base to check whether it is permissible, as well as convert hours and minutes to the decimal system and compared with 24 and 60, respectively.

What is maximal base, that we need to check? In fact, it is enough to 60, because 60 — upper limit on the allowable number. It follows from the fact that if the number in an unknown number system consists of one digit, then its value in decimal not ever change, otherwise its value is not less than the base.

It is also worth to consider the case with the response <<-1>>, for this example, you can check a big base, such as 100, and even if the time for him correct, then for all large, it is also correct and the answer is <<-1>>.

149C - Division into Teams

Sort all the boys on playing skill. Then, if we send in the first team all the boys standing in a sorted array for odd places, and the second — even standing on the ground, then all requirements for division executed.

The first two requirements are obviously satisfied.

To prove the third we consider the geometric representation: Let each child designated point on the X axis with a value equal his playing skill. Connect the points with segments numbered 1 and 2, 3 and 4, and so on. If n is odd, then join the last point with the nearest the previous one.

Obviously, all these segments don't intersect in pairs, except at the points, and their total length is equal to the difference amounts to play boys' skills contained into the first team and second team. It is also clear that all of these segments completely contained in the interval [0, max(ai)], as well as the pairs are a length of zero crossing, the third requirement is satisfied, which we proved.

149D - Coloring Brackets

We introduce the notation of colors: 0 — black, 1 — red, 2 — blue. Note that a single pair of brackets has 4 different coloring: 0-1, 1-0, 0-2, 2-0.

Consider the dynamic programming, where the state is (l, r, cl, cr), where the pair (l, r) defines a pair of brackets, and cl and cr denote a fixed color for them. The value of the dynamic is a number of ways to paint all the parenthesis brackets inside the interval (l, r) in compliance with all conditions.

We write down all the pairs of brackets that are directly placed into a pair of (l, r), let k of their pieces. Moreover, we consider only the first level of nesting, it is directly attached.

In order to calculate the value of the dynamics for the state, within this state shall calculate the another dynamic, where the state is a pair (i, c) which means the number of correct colorings of the first i directly nested parentheses, and all inside them, if the latter closing bracket has a color c. Calcing the values of this dynamic is very simple, let's try to paint a (i + 1)-th parenthesis in one of four variants, but you should keep in mind possible conflicts. In such dynamics the initial state is a pair (0, cl), and the final result is sum over the states of the form (k, c), where c must not conflict with the cr.

The answer to the whole problem may be calced as the internal dynamic. Time of solution — O(n2) by a factor of about 12.

149E - Martian Strings

We will solve the problem separately for each m strings. Thus, suppose we have a string p, its length is l, and we need to check whether the Martian be seen.

We introduce additional arrays: let pref[i] is minimal position in the s of the begin of occurrence p with length exactly i, and let suff[j] is the maximum position in the s of the end of occurrence p with length exactly j

It is easy to understand that a Martian could see the p, if there exists an i, that suff[l - i] ≥ pref[i] + l - 1.

How to calculate the arrays? For pref array is sufficient to find Z-function p#s, but for an array of suff — Z-function r(p)#r(s), where r(t) means the reversed string t. Using an array of Z-functions calcing of arrays suff and pref is trivial.

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

Comments Comments (23)
| Write comment?
»
13 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Lot of people have used kmp for problem E , I actually came up with same idea , But I thought it can not fit into time , because it's time complexity was 100 * 100 * 10^5 = 10^9 , I could not satisfy myself that it will work . Can anybody suggest me something regarding the solution ?

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

    complexity of kmp is O(length(str1)+length(str2)) i.e. 100000+1000 for every string ,and multiply this by 100 (number of strings) so you get about 10 million operation which is pretty fast to pass

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

Can someone tell me how does the solution for E handles cases like this: ABCBA 1 ABA The solution should be AB [0, 1] and then A [4, 4] or A[0, 0] and A[3, 4] The problem is you will not be able to make the suffix A because u can make AB (Z function takes longest) and same applies to prefix A. Am I missing something?

→ Reply
  • »
    »
    13 years ago, # ^ |
    ← Rev. 2   Vote: I like it +5 Vote: I do not like it

    You must normalize pref array like this way: for(int i = pref.length - 2; i >= 0; i--) pref[i] = min(pref[i], pref[i + 1]);

    You must do the same for suff array.

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

How to solve problem E using KMP? It seems that rng_58 did it.

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

It's the bug? about problem B test 1.lots of guys get stucks

my code running in locate machine, the answer of test 1 is 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22.

but the online test show my answer is 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23

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

    You can run your code on the server-side. Use "custom test" tab in the contest dashboard.

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

Can someone explain what a Z-function is?

→ Reply
  • »
    »
    13 years ago, # ^ |
      Vote: I like it +6 Vote: I do not like it

    You can go to e-maxx.ru ,, 1. although the site is russian , google translate will do a good job ,you can find code for z function etc.

    2."http://codeforces.net/blog/entry/3107" , post by paladin8

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

If you don't like 10^7 operations ;) then see here for an O(n log n) solution to E.

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

    Hi, I will try to understand your solution, is it n*logn for each of the m strings? I tried a n*logw*m solution here, but got TLE :(, my submission: http://codeforces.net/contest/149/submission/1176274 , I generated some random big cases and they ran around 0.5 secs here :x

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

      Hi, it's O((n + L) log n) overall, where L is the sum of lengths of the short strings. What you submitted is slower than the O(nm) solution.

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

        Thank you :), I was hoping that it would pass the time.. but it doesnt :(

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

          Can anyone explain about the difference between qsort and sort? In problem C, I used qsort and got TLE. But in the same code using sort function I got AC.

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

            qsort is O(N^2) in worst case, sort uses introsort which has worst case O(NlogN).

            → Reply
            • »
              »
              »
              »
              »
              »
              »
              13 years ago, # ^ |
                Vote: I like it +2 Vote: I do not like it

              Thanks.

              → Reply
              • »
                »
                »
                »
                »
                »
                »
                »
                13 years ago, # ^ |
                  Vote: I like it -30 Vote: I do not like it

                ็็็็็็็็็็็็็็ส็็็็็็็็็็็็็็็็็็็็็็็็็ส็็็็็็็็็็็็็็็็็็็็็็็็็ส็็็็็็็็็็็็็็็็็็็็็็็็็ส็็็็็็็็็็็็็็็็็็็็็็็็็ส็็็็็็็็็็็็็็็็็็็็็็็็็ส็็็็็็็็็็็็็็็็็็็็็็็็็ส็็็็็็็็็็็็็็็็็็็็็็็็็ส็็็็็็็็็็็็็็็็็็็็็็็็็ส็็็็็็็็็็็็็็็็็็็็็็็็็็็็็็็็็็็็็็็ส็็็็็็็็็็็็็็็็็็็็็็็็็ส็็็็็็็็็็็็็็็็็็็็็็็็็ส็็็็็็็็็็็็็็็็็็็็็็็็็ส็็็็็็็็็็็็็็็็็็็็็็็็็ส็็็็็็็็็็็็็็็็็็็็็็็็็ส็็็็็็็็็็็็็็็็็็็็็็็็็ส็็็็็็็็็็็็็็็็็็็็็็็็็ส็็็็็็็็็็็็็็็็็็็็็็็็็ส็็็็็็็็็็็็็็็็็็็็็็็็็

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

I am trying to solve Problem 149E - Martian Strings with Suffix automaton . But always it gives me wrong ans at 14 no. testcase . Can Someone tell me where I do wrong ? Thanks in advance .

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

For problem D, you can transform the string into a tree, and you can solve it in O(n).

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

Can someone explain proof for condition 3 in problem C more clearly?

→ Reply
  • »
    »
    4 years ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it 
    /*
* Say n is even: The sum of nums at odd indices will be more(0 based) (obviously)
* The sum of elements at even indices therefore will be less than SUM/2 (It can be equal too)
* Now if we remove the last element. n will get odd and SUM will become
* SUM-amax. So now when the n is odd the sum of elements at even indices
* will be more. ie it'll be more than (SUM-amax)/2. Which satisfies our
* inequality.

* Similar proof when n is odd.

* So one group has elements at odd indices and one elements at even.
*/
    → Reply