ilya_the_lamer's blog

By ilya_the_lamer, history, 6 months ago, In English,
Tutorial is loading...

Author: s17b2_voroneckij Development: s17b2_voroneckij

Tutorial is loading...

Author: akvasha Development: akvasha

Tutorial is loading...

Author: akvasha Development: akvasha , ilya_the_lamer

Tutorial is loading...

Author: ilya_the_lamer Development: ilya_the_lamer , akvasha

Tutorial is loading...

Author: platypus179 Development: platypus179

Tutorial is loading...

Author: platypus179 Development: platypus179

Tutorial is loading...

Author: KAN Development: platypus179 , ilya_the_lamer , akvasha

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

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

can someone please explain the problem statement of DIV 2 C more precisely?

  • »
    »
    6 months ago, # ^ |
    Rev. 2   Vote: I like it +22 Vote: I do not like it

    I have a simpler solution. Take all edges that connect vertices of different colors. If all these edges have one common vertex — this vertex is the answer. Otherwise the answer is NO.

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

      I'll definately look into your approach, but the problem itself is not clear to me. explanation to the sample inputs will do fine.

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

        You have a tree and you must find such vertex v, that when you root the tree at the v, each subtree below v has one color (all vertices of subtree has the same color). Number of subtrees is equal to degree of v. The color of v doesn't matter at all.

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

          The word "move down" is quite hard to understand in problem C div 2.

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

      Ok I got it now. Actually I missed the part "He doesn't consider the whole tree as a subtree since he can't see the color of the root vertex." :( and your approach is the simplest one I found so far. thanks

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

      Your method is much simpler renadeen. Thoughtful insight.

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

      See moejy0viiiiiv's solution.

      You can check that by counting the number of edges with vertices of different colours. Also, count for each vertex how many such edges it is connected to. Since we must choose a vertex connected to all such edges, we just need to check whether there is some vertex that is connected a number of edges equal to the total number of such edges.

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

        Wow! Very simple to understand. I just read and got Accepted. Thank you!

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

      I solved it that way. In addition, if there is only one edge (u, v), the vertices of which are of different colors, then the answer can be either u or v

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

      thnkss.. rendeen.. for the simple and effective idea

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

    we have to find whether it is possible at any vertex that each subtree origining from it have same colour for all it's vertices.

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

Editorial for Div.2 D???

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

Thanks for such great problems, I enjoyed from solving them :)

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

Can anybody expalin Div2 D please...

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

    We may assume that our rectangles are drawn on an infinite sheet of squared paper. Divide it into squares 2 × 2 and mark the cells in each square by 1, 2, 3, 4 clockwise starting from the upper left corner. Since both sides of each rectangle are of odd length, its corner cells are marked by the same number. Let us number four different colors by 1, 2, 3, 4 and paint each rectangle with the color whose number marks the corner cells. It is readily seen that the numbers in the corners of any two adjacent rectangles are distinct.

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

      the best

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

      Better than editorial!

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

      I got your solution but can you please explain the intuition behind it? This may seem silly but I really can't understand how did you come up with idea of making 2*2 square which is filled with 4 different colors?

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

        This is not his idea.
        In 2008 there was a mathematics olympiad: problems. The problem 5 from the olympiad is the same as problem Div2D.
        He has copied the text from this editorial.

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

        I tried to reverse engineer the possible thought process and I think it may have started from an observation of a simpler 1D problem.

        Observation 1. Rectangles of sizes 1, 3, 5, 7 that start with a red square always end on the red square.

        Observation 2. After that you start to notice that the same is true for the rectangles that start with a white square.

        Observation 3. The 3rd observation is that all the possible rectangles are of these 2 types (i.e. there is no 3rd type of rectangle).

        Observation 4. The last observation for 1D problem is that adjacent rectangles cannot be of the same type (i.e. they have to be of different types).


        After that, probably, we could have generalized to 2D case, by seeing that in addition to already discovered 2 horizontal types (we were looking at horizontal line), there are now 2 more vertical types of rectangles. So, overall, there are 4 different types of rectangles and rectangles of the same type cannot be adjacent.

»
6 months ago, # |
  Vote: I like it +2 Vote: I do not like it

problem E can be solved in as well with MO's Algorithm + DSU with rollbacks and adding the border edges by brute.

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

    I tried hard but couldn't fit the time limit no matter what 24386929.

    My complexity was .

    Could you elaborate how do I go down to your complexity?

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

      sort the edges according to min of the two end points , now each query consists of edges from a range(all edges whose min endpoint is from to ) along with some edges whose endpoints are in the range to . you can get the answer for the edges in that range using MO's algo and add those few extra edges one by one and roll them back in the dsu later.

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

        Oh.... So do you mean the Mo which never deletes anything and only adds new elements and rollbacks added?

        Thank you

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

    We didn't want this solution to pass and made special anti-Mo cases, and as we see, no one who wrote Mo passed systest.

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

      Forgive me if I misunderstand the whole situation, but for instance is the solution of socketnaut not using Mo's algorithm? In fact his code even has comment // mo's algorithm, and he did indeed pass system tests. Or are you referring to something else?

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

763C — Тимофей и перемодулирование Sorry for stupid question,

How it calculated??

This is right: x % k mod (m) == x*k1 mod m, where k1*k == 1 mod m ==> k1 == k^(m-2) mod m??

»
6 months ago, # |
  Vote: I like it +1 Vote: I do not like it

Please give some more explanation for Div-2 D.

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

    Since sides of all rectangles are parallel to x and y axis only there can not be 4 or more rectangles which touch each other therefore solution always exists. Now since side lengths are odd therefore one of x1 or x2 is odd and other is even same goes for y (one can check by drawing in x,y plane) . For rectangles with x1 odd, since its x2(end) is even its neighbors will always have there x1(start) as even (they cannot have same color) and the same goes for y.Therefore 4 possible combinations are possible for x,y -> odd,odd even,odd odd,even and even,even. Hence the solution.

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

      Thanks bro. Got it. Nice Explanation.

»
6 months ago, # |
Rev. 2   Vote: I like it -7 Vote: I do not like it

Good set of problems.I especially liked the third one. Just thought this would help someone. For the first one simply find lcm of n,m and divide z with it.(Think why?)

For the third one simply check the pair of vertices as given in the input with different set of colours.All such vertex pairs should have atleast one common vertex which is the answer.Otherwise the answer is NO.

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

for div 2 C , wont the given editorial give a time complexity of O(n^2).... if each vertice is coloured differently, then it will do dfs from each of the vertice ...? or i understood the solution incorrectly.. B-)

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

    No, the answer will have complexity of O(n).

    1. We iterate over all edges to find one edge that connects different colored nodes — O(n).
    2. We check if one of those nodes can be the answer. How do we check it? We use DFS — O(n). So we end up with O(n) + O(n) + O(n) = O(n) complexity.
    • »
      »
      »
      6 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      There can be more than one edge connecting different coloured vertices eg. 1->2->3 and c[i] is same as vertices number , then we can hold by two...similarly if there were many coloured vertices ,I would have to dfs it those many times according to the editorial....atleast that's what I understood ☺☺

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

        You only need to check the two end vertices from one such edge. If non of these vertices is the solution, then no solution exists and you can abort.

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

      I can't understand how to promise that a subtree doesn't annoy him if there are vertices of same color in it, please explain this sample: 4 1 2 2 4 4 3 1 1 3 2 YES 4 But in 4's subtree, the color of 3 and the color of 1 or 2 are different

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

        Take a look at this  Problem says that root node doesn't belong to any subtree.

        Also subtrees that are going from root node can have different colors.

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

problem C Does it really necessary to solve it in two case? when we choose some element y,then we check if y-d,y-2d,...,y-kd belongs to A until it not or k=n-1.Then,the same,check y+d,y+2d,....,y+kd.Because what we check is continous,it's "safe" and easy to find the value of the first element.

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

    Can you explain how to choose the value of y and d? Thank you.

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

      well,just as the solution above said,choose some two elements a and b,assume x=a-b,and count the number of such pair which has the same difference value,assume it's k(including (a,b)),then we get d=x/(n-k).

»
6 months ago, # |
Rev. 3   Vote: I like it +5 Vote: I do not like it

Edit: got it!

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

    Hello!I have replied the question in the first page,I hope you can have a look at it please.

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

      Sorry to bother you, but I wanna know why the 2D structure like this, please explain it, thank you.

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

        Consider a rectangle,we have know that rectangles cannot intersect,and all sides of the rectangles have odd length.As we all know,the Four color theorem,so it must have a solution.What we need to do is to find a solution to give a color to every rectangle.If the lower left quarter of the rectangle,(x1,y1),so that we can know the situation of (x1+odd,x2+odd),we can confirm that we just need to color the rectangle according to its x1 and y1's parity.

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

        I hope my solution and explanation would help you!

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

Can someone explain 763C more elaborately? I am unable to understand it.

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

Div1.C Please explain why we consider the case 2*n>m? I don't understand

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

    Note that an arithmetic progression of m terms are all distinct mod m if we have (d,m)=1. So if the given set forms an arithmetic progression, so does the complement of it.

    • »
      »
      »
      6 months ago, # ^ |
      Rev. 2   Vote: I like it +8 Vote: I do not like it

      But why the method when 2n<m can't be used when 2n>m?

      Edit:Nevermind, I figured it out when I started writing the code.

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

    I noticed that I misunderstood your point, thanks to Ismll. :) So let me answer your question again: If we do not consider the case when 2*n>m, the following statement is not true.

    On the other hand, x must be difference of exactly n - k + 1 pairs of elements of A. (Actually, I think that this should be n-k)

    This is due to somewhat number theoretic reason. It is like, let me say, an overflow mod m. For example, let x = 3*d (i.e. k=3), n = m-2. The pair (s, s+(n-1)d) should not be counted, but it is counted since s = s+(n+2)d mod m. However if 2*n<m, this does not happen.

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

    More precisely, we should consider the size relation between 2n-3 and m, rather than 2n. As topology put it above, overflow mod m may happen in some situation. In fact, the boundary condition is that the sum of the two largest differences(in absolute value) of element pairs equals to m*d. That is pairs (s,s+(n-1)d) and (s,s+(n-2)d), whose sum of differences is (2n-3)d.So we should consider the size relation between 2n-3 and m. Once 2n-3<m, the insecurity, namely overflow mod m won't happen.

    In short, when 2n-1=m, the case must be safe.In practice, whether 2n or 2n-3, both of them can get accepted.

    Ps: My AC code with 2n 24488586 and 2n-3 24491759.

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

My algorithm for Div. 2 C was exactly the same.

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

codeforces comment system are implented by tree data structure , i think .

»
6 months ago, # |
Rev. 2   Vote: I like it +6 Vote: I do not like it

Can anyone give an easier-to-understand explanation for Div1-C? I still don't understand how to deal with modulo m operation.

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

Weak cases in Div2C

4

1 2

2 3

3 4

5 3 2 4

My AC code gives YES but correct one is NO

»
6 months ago, # |
  Vote: I like it +26 Vote: I do not like it

From a problemsetting perspective, I'd like to ask ilya_the_lamer about how you wrote a checker for this problem, and how this affected the system testing.

By the way, writing the checker surely seems harder than the original problem, and I'm assuming you wrote a n log n (take all the rectangles of some color, do horizontal/vertical segments independently, check for overlap). I wonder how running O(n log n) for n=500000 on ~50 test cases for a bunch of programs affected this system testing. It seemed pretty fast to me, just curious how it ran so fast in this way!

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

    We used 2 scanlines to build graph, and then just simply checked, that there is no edges with same-colored vertexes. As you correctly mentioned, this works in .

    I can share you checker, if you are really interested in it.

    What about fast working, most of the solutions, that used wrong idea, didn't pass small pretests (n near 100), so testing on big tests didn't even start in most cases.

»
6 months ago, # |
Rev. 2   Vote: I like it +10 Vote: I do not like it

Although I couldn't submit it during the competition (and honestly it took to long to code to be practical for myself), I have a very different number theoretical approach to 763C - Timofey and remoduling. The problem is effectively to find x and d such that {a[0],a[1],...a[n-1]} = {x,x+d,...x+(n-1)d} (mod m). We solve this using the sum and sum of squares to create a quadratic equation of either x or d, confirm the existence of a solution with the Legendre symbol and use Cipolla's algorithm to find the solutions if they exist. There are at most two, which we can confirm in O(n log n).

In order to meet the conditions for which this algorithm can work, we consider only m which is odd and n<m-1. While there is no deterministic way for solving an arbitrary quadratic equation, it can easily be transformed into y^2 = k (mod m) where the Cipolla algorithm allows us to solve with approximately 1/2 probability for each random number. So, the expected value is 2. The overall complexity is O(n log n + k log m), where k is the number of tries in the Cipolla algorithm. It can be quite high for the problem conditions, so although there is a probability for failure, it is very small.

Submission: 24420260

  • »
    »
    6 months ago, # ^ |
    Rev. 2   Vote: I like it +8 Vote: I do not like it

    Nice solution! And in fact, you can simply try all a[i]-a[1] as d and find x with x+(x+d)+...+(x+(n-1)d) equals to the sum of the elements. As you have said, there are at most two pairs (x,d) which satisfy x^2+(x+d)^2+...+(x+(n-1)d)^2 equals to the sum of square. So we can check these two pairs by brute force.

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

      Wow. I actually realized we can easily reduce the candidates for d to n-1 candidates without additional calculations but I didn't think to use that in conjunction to this approach. This approach has a far simpler implementation.

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

Can somebody please explain Div 1C? I am unable to understand the solution.

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

Regarding Div1 B about coloring rectangles: is there any reasonable way to solve the problem just by looking at the connectivity graph and not by taking advantage of odd side lengths?

Btw. this problem is genius IMO, thanks ilya_the_lamer!

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

    I'm almost sure there should be one. Indeed, four color theorem guarantees that the solution exists. Moreover, I remember that the only case that needs 4 colors is kind of pathological, so for this case you only need 3 colors. Finally, what I think can be done is go line per line (in the sense x-coordinate by x-coordinate) and color all the rectangles that pass through this x-coordinate alternatively.

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

      so for this case you only need 3 colors

      Actually you do need 4 colors here :) Counter-example with 6 rectangles: 1 rectangle in the center 5 other rectangles linked in a cycle (of odd=5 length) each of which touches center rectangle

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

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

763E — Timofey and our friends animals

aren't we storing O(N) values?

hoping not to say something stupid: let be f(n) the number of node needed by a segment tree with lenght n f(1) is clearly 1; //himself f(n) = 1 + f(floor(n/2)) + f(ceil(n/2)); //himself + left son + right son

we can simply prove that this lead us to f(n) = 2n-1;

if i didn't understand, can you please explain me why? thanks

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

Model solution provided in editorial gets AC; at the same time it is not clear to me how segment gluing is being done there, and for example on test

16 4
6
8 9
8 10
9 11
11 13
10 12
12 13
1
8 13

it says 0 :)

P.S. And I also started to believe that a nice O(N*K*K) solution works here as well (like 24603977), but this one gives 2 for

5 5
5
1 4
5 4
2 3
3 5
4 2
1 
3 5
»
5 months ago, # |
  Vote: I like it 0 Vote: I do not like it

In Div2E/Div1C, I don't understand the following statement:

"On the other hand, we have that n is less then m/2, so x must be difference of exactly n - k + 1 pairs of elements of A."

Formally, why the following holds?

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

Can someone please look into issue for Div1 E Timofey and our friends animals: http://codeforces.com/blog/entry/52419