map's blog

Analysis Codeforces Beta Round #63 (Div. 2)
By map, 14 years ago, translation, In English

Problem A.

In this task all you had to do was to make sure that the sum of all Σxi is 0, the sum of all Σyi is 0 and that the sum of all Σzi - 0 .
We have not written that condition evidently in order that participants will have a chance to break a solution.

 

Problem B.

In this problem, in fact, you should find a winner at every section. For each section, you must do a full search of all competitors to find a competitor with a minimum section time, which ran that section. Asymptotic of the solution is O(nm).

 

Problem C.

In this task, you had to update the collection of artifacts, which belong to Kostya’s friends, after each purchase . You had to set  a matrix c[i][j] - number of the j-th basic artifact that is required in order to collect the i-th component artifact. Further, one can make a matrix of composite artifacts, where a[i][j] is number of the j-th basic artifact of the i-th friend and a similar matrix b of composite artifacts, and  check whether i-th friend has any a composite artifact of O (MN) after each  i-th friend’s  purchase. Check whether one component of the artifact assembles for O (N): while checking whether the i-th friend is able to collect the j-th artifact you have to check, if there is such u, that c[j [u]> a[i][u], if so, the j-th artefact will not be collected, if not, then you have to increase the b[i][j] and update the values in a[i]).

So.the asymptotics of the processing of all purchases will be O (NQM). Then, we need  to make a list of artifacts for each person, keeping their quantity(a total of O (KN + KM), and sort it (a total of O (QlogQ)).

 

Problem D.

This game is over, because except for a finite number (2) of reflections about the line y = x,the coordinates are changed to non-negative integer (and at least one coordinate is changed to a positive number).

Algorithm for solving this problem  is DFS / BFS (states) where the state is a pair of coordinates, and two logical variables, which denote if the 1 (2) player had reflected a point about the line y = x.

Total number of states is obtained by S <= 4D^2 (pairs of coordinates) * 4 (Boolean variables).

Processing of one state takes O (N) actions (do not forget to try to reflect the point about the line y = x, if the player had not made it earlier in the game). Thereby, we have the overall asymptotic O (ND^2), which works on C + + in less than 200ms.

 

 

Problem E

To solve this problem you have to do a "move" subsegment and know :

 1. The set B of numbers, meeting once, with the function of extracting the maximum for O (logN)

2.The set of numbers appearing on this subsegments with keeping the number of times,that this number is found on this subsegments, with function of verifying how many times the number in this subsegments for O (logN).

 

While moving a segment from (a[i] .. a[i + k - 1]) for 1 item left (a[I + 1] .. a[I + k]) you have to:

1) Check whether a[i] with a[I + k]. If yes, then there is no need to modify the set, otherwise proceed to item 2 and 3.

2) Check how many times we have a[i] in the set A: if 2, then add a[i] to B, if 1, then remove it from  A and B. Do not forget to reduce the corresponding number of occurrences of a[i] in the current segment 1.

3) Check, how many times we have a[I + k] in the set A: if 0, then add a[i] in the B and A, if 1, then remove it from B. Do not forget to increase the corresponding number of occurrences of a[i] the current interval to 1.

 

After that, if the set is not empty, we should take peak from it.

 

So the asymptotics of this process will be O(NlogN).

 

As such data structures  set / map(for those who use C + +) and the Cartesian tree are suitable.

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

Comments Comments (20)
| Write comment?
14 years ago, # |
  Vote: I like it +4 Vote: I do not like it
You don't have to check reflections at all in task D. If player is in loosing position he can reflect coordinates, but the opponent (who had winnig strategy, so didn't use the reflection) also reflects.
→ Reply
  • 14 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    Can you please explain this?
    → Reply
    • 14 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it
      Lets see on game without reflects. Somebody have win strategy.

      So, in this game he should use it only after opp's reflection ad win
      → Reply
    • 14 years ago, # ^ |
      ← Rev. 2   Vote: I like it +8 Vote: I do not like it
      Suppose that we can't make reflections, so for each reachable position you can determine whether player who starts at this position has a winning strategy (no matter what his opponent does) or he must lose no matter what he does. Suppose that the player starts in losing position, so the only rescue for him is to reflect coordinates and then his opponent starts at losing position (if a position is losing/winning, then reflected position has the same state). But since his opponent has a winning strategy without using reflections, you know that he didn't need to use reflection and can use this reflection now to make his opponent start in losing position again.
      → Reply
14 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it
→ Reply
14 years ago, # |
  Vote: I like it 0 Vote: I do not like it
Yes, of course. You are absolutely right.
→ Reply
14 years ago, # |
  Vote: I like it +5 Vote: I do not like it
For problem E , if my solution was O(n2) then it would have led to TLE?
→ Reply
  • 14 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    Yes.
    → Reply
  • 14 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    n=10^5,so n^2 will certainly lead to TLE.
    Here is my approach:

    Process first K numbers at once. Store frequencies of each number in hash table and maintain a set which contain values which occurred only once. then process rest of the numbers while taking input. reduce frequency of i-K th number, modify the set according to frequency.

    Suppose input is:
    6 3
    1
    1
    2
    6
    6
    First i will process first 3 numbers. so the set will be {2} and map will be freq[1]=2,freq[2]=1.
    When i get 4th number 6,i will reduce freq of 1st number. freq[1] will become 1 from 2. as it has become 1,the set will be {1,2,6}(as i got 6 for the first time).

    Then i get 5th number 6,i will reduce freq of 2nd number. freq[1] is now 0. as it went 0 from 1, i need to remove it from set too. so the set becomes{2}(i will remove 6 too as i got it 2 times now).

    Every time print the largest number from set. If the set is empty print "nothing". i've used c++ stl <set>.
    → Reply
14 years ago, # |
  Vote: I like it 0 Vote: I do not like it
please check my submission for problem C id: 350527 it says answer mismatch in line 2 but it does not...
→ Reply
14 years ago, # |
  Vote: I like it 0 Vote: I do not like it
About D:
"Thereby, we have the overall asymptotic O (ND^2), which works on C + + in less than 600ms"

My solution used the same complexity, but ran in 80ms. Reason (I think) is that once I find a move to a losing position, I declare current position as winning and return (i.e. no need to look at other moves).
This is trivial optimization, but I think an important one, because some Java solutions with O(ND^2) failed due to TLE. (600ms in C++ does not leave a good margin)

→ Reply
  • 14 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    200ms. Typing error. We have same correct JAVA solution.
    → Reply
14 years ago, # |
← Rev. 3   Vote: I like it 0 Vote: I do not like it

When I changed "double" to "int" in task E, I've got AC (with double - WA). But I can't find any words in problem statement about representation of numbers in answer. Also I can't find nothing in problem statement to determine if numbers are integers or not...

→ Reply
  • 14 years ago, # ^ |
      Vote: I like it -11 Vote: I do not like it

    ATTENTION! THIS CONTEST SHOULD BE UNRATED!

    Maybe now you will read my message carefully :) I think that Corny is right. His solution works just after replacing "double" to "int".

    → Reply
    • 14 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it
      I've found problem. It with presentation, but it's my fault. When answer is 994790178 I write 9.9479e+008. I should be more careful next time.
      → Reply
      • 14 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Really? Ok, try to output floating-point numbers with 1e-10 precision.

        I think result would be the same :) 

        → Reply
        • 14 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it
          I've tried to output correct floating-point numbers. It got WA. So maybe statement should be more precise.
          → Reply
14 years ago, # |
  Vote: I like it 0 Vote: I do not like it
About Task C 
for this input 
1 1 2 2
a
b: a 2
c: a 1
1 a
1 a                                                                                                    

I am printing 

1

b 1

while the answer is

1

c 2

I can't see why my output is wrong (I think both outputs are correct in this case)
→ Reply
  • 14 years ago, # ^ |
      Vote: I like it +1 Vote: I do not like it
    "It is guaranteed that after the i-th purchase no more than one opportunity to collect the composite artifact appears. If such an opportunity arose, the hero must take advantage of it."
    So your solution is wrong. After buyin first 'a' artifact player has oportunity to build artifact 'c' but in your solution he didn't take advantage of it, he waited for the second 'a' to compose 'b'
    → Reply