witua's blog

By witua, 6 years ago, In English,

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

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

»
6 years ago, # |
  Vote: I like it +7 Vote: I do not like it

I can't understand why doubled area is:|(x1 - x)(y2 - y) - (x2 - x)(y1 - y)|...can any one tell me why?

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

    cross product?

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

      Thank you...I am just on thinking about the meaning of this formula in classical geometry...a silly question...

»
6 years ago, # |
  Vote: I like it +3 Vote: I do not like it

In Div 1, Problem B, what is O(NsqrtN) solution?

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

    For each two queries [l1, r1] and [l2, r2] we can easily change the first query to the second in no more than |l1 - l2| + |r1 - r2| operates.(adding or deleting the leftmost and rightmost elements and counting the number of times that each number appears)

    Sort all the queries by as primary sort key, and ri as secondary sort key. Now we can get a offline solution.

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

      Why do you sort the queries by l/sqrt(n)

      • »
        »
        »
        »
        6 years ago, # ^ |
        Rev. 2   Vote: I like it 0 Vote: I do not like it

        Split l into groups. We can ensure that if i, j are belong to the same group.

        So we can calculate the complexity as follow:

        1. = * m queries

        2. = O(n) * groups =

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

    There is a much easier one. Just considering number x that occurs at least x times in sequence a. It's not hard to prove that there are at most 2*sqrt(N) numbers to be considered.

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

      Can Anybody explain me , why are there at most 2*sqrt(N) of such numbers?. Thanks in advance.

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

        (C[x] means the times that x occurs in sequence a) if C[x]>=sqrt(N), the number of this kind x is no more than sqrt(N). otherwise the number of elements in sequence a is greater than sqrt(N)*sqrt(N)=N if C[x]<sqrt(N), 1<=x<=C[x]<sqrt(N)

»
6 years ago, # |
  Vote: I like it +14 Vote: I do not like it

220E — we use RSQ, not RMQ

»
6 years ago, # |
  Vote: I like it +4 Vote: I do not like it

220B: why has the proposed solution nlogn complexity? I mean, if for each x I need to sum up D_l, D_l+1 etc to answer to the queries (that in worst case start from 0 and end to x for each x), isn't it N^2?

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

    you can use segment tree to query 0 to x....

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

In explanation of 220C, what does this mean " (for the example above, it is texttt{2, 4}) " ? Does it mean that left set has a minimum distance of 2 and right set a minimum of 4?

  • »
    »
    6 years ago, # ^ |
    Rev. 3   Vote: I like it +3 Vote: I do not like it

    \texttt was a tag, now it's fixed.

    [2, 4] is the set of distances in right part, i. e. distance from 1 in sifted B to 1 in A (it is equal to 4) and distance from 2 in shifted B to 1 in A (it is 2).

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

    Got it

»
4 years ago, # |
Rev. 2   Vote: I like it -8 Vote: I do not like it

In problem A, for example, n = 3, if the init array is (3, 1, 2) (author's solution), isn't the sorted array is (3, 1, 2) -> (3, 2, 1) -> (2, 3, 1)? Did I mis-understand something?

PS: I know it's weird for a purple to stuck at Div2-A, but this one confused me a lot...

Edit: I got it, the sort happened after we enter function f[x-1], so it should be (3, 1, 2) -> (1, 3, 2) -> (1, 2, 3). I don't know what happened with my brain today...

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

220B — Little Elephant and Array, can anybody explain me how the update (add 1 to D[|p| — t], add -2 to D[|p| — t — 1], and add 1 to D[|p| — t — 2]) work?

  • »
    »
    3 years ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    I had a different approach

    first of all count the numbers an remove numbers like x which occurred less than x times at all now you have at most O( sqrt(n) ) numbers.

    for each of these store the indexes. for example store the indexes in which x occurred in vector[x].

    now for each query(x,y) all you need to do is to binary search in each vector and find lower bound of x and upper bound of y( lets name them lbx and uby ) now we easily find out that x occurred ( uby-lbx ) times in [x...y]

    it will solve the problem in O( N*sqrt(n) + Q*sqrt(n)* log( vector size ) )

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

220B — Little Elephant and Array this question can be solved by MO's Algorithm

»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

I was trying to solve 221B using query square root decomposition.

I tried the following solution which was getting TLE, while this similar solution passed.

The only difference between the 2 solutions is the extra use of containsKey in the TLE solution. From my understanding containsKey has constant time complexity, so it shouldn't really be decisive for the acceptance or not of the solution. Am I missing something here?

»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

In case if anyone finds the explanation for Div2D/Div1B confusing, just Google "MO's algorithm". Can't believe this magic man...

»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Little Elephant and Array can be solved with hashing. Since n*(n+1)/2<=100000, therefore n<=450, which is the condition for tightest constraints i.e. n=10000 and all numbers 'a[i]' are distinct and appear 'a[i]' times.

Solution: http://codeforces.com/contest/220/submission/20777330

»
23 months ago, # |
  Vote: I like it 0 Vote: I do not like it

how for for problem D complexity can be achieved O(mn)

»
5 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Witua is known to set beautiful problems and this contest was fantastic !

Here are my solutions to the Div 2 problems of this contest.

In Div 2, problem D captured my imagination. So, I wrote an editorial about it here that explains both the approaches.

  • »
    »
    4 months ago, # ^ |
      Vote: I like it -8 Vote: I do not like it

    I love your editorial. its very comprehensive

»
3 months ago, # |
  Vote: I like it -8 Vote: I do not like it

Can anyone tell me why this code wrong : http://codeforces.com/contest/220/submission/41300881

»
3 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Shouldn't sqrt root decomposition work for 220B? Where am i going wrong? https://codeforces.com/contest/220/submission/41652936 Thanks in advance!

»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

could someone explain 220C. Little Elephant and Shifts bit more