Eran's blog

By Eran, 8 years ago, translation, In English

703A — Mishka and Game

In this problem you had to do use the following algo. If Mishka wins Chris in the current round, then increase variable countM by 1. Otherwise (if Chris wins Mishka) increase variable countC. After that you had to compare this values and print the answer.

703B — Mishka and trip

Let's look at the first capital. Note that the total cost of the outgoing roads is c[id1] · (sum - c[id1]), where sum — summary beauty of all cities. Thus iterating through the capitals we can count the summary cost of roads between capitals and all the other cities. But don't forget that in this case we count the roads between pairs of capitals twice. To avoid this on each step we should update sum = sum - c[idcur] , where idcur is the position of current capital. In the end we should add to the answer the cost of roads between "non-capital" neighbour cities.

Complexity — O(n).

703C — Chris and Road

Imagine that the bus stands still and we move "to the right" with a constant speed v. Then it's not hard to see that movement along the line y = (u / v) · (x  -  v · t0) is optimal, where t0 — time in which we begin our movement. In this way answer is t = t0 + (w / u).

If t0 = 0, then we start our movement immediately. In this case we need to check that our line doesn't intersect polygon (either we can cross the road in front of a bus, or the bus is gone).

Otherwise we need to find such minimal t0 that our line is tangent to the polygon. It can be done with binary search.

Complexity — O(nlogn).

Exercise: Solve this problem in O(n).

703D — Mishka and Interesting sum

Easy to see, that the answer for query is XOR-sum of all elements in the segment xored with XOR-sum of distinct elements in the segment. XOR-sum of all numbers we can find in O(1) using partial sums. As for the XOR-sum of distinct numbers... Let's solve easier problem.

Let the queries be like "find the number of distinct values in a segment". Let's sort all the queries according to their right bounds and iterate through all elements of our array. We also need to make a list last, where last[value] is the last position of value on the processed prefix of array. Assume we are at position r. Then the answer for the query in the segment [l,  r] (l ≤ r) is , where cnt[i] = 1 if last[ai] = i and 0 otherwise. It's easy to store and update such values in cnt. When moving to the next position we have to make the following assignments: cnt[last[ai]] = 0, cnt[i] = 1, last[ai] = i. To get described sum in O(logn) we can use segment tree (or Fenwick tree) instead of standard array.

Now let's turn back to our problem. Everything we have to do is to change assignment cnt[i] = 1 to cnt[i] = ai and count XOR-sum instead of sum. Now we can solve this problem in O(nlogn).

Solution (with Fenwick)

P.S.: Also there is a solution with O(nsqrtn) complexity (using Mo's algo), but we tried to kill it :D

703E — Мишка и делители

Let's use dp to solve this problem.

Suppose dp[i][d] is the minimal number of elements on prefix of size i, that their product is divisible by d. It's easy to see that dp[i][d] = min(dp[i  -  1][d],  dp[i  -  1][d  /  gcd(d,  ai)]  +  1). That is so because it's optimal to take as much divisors of ai as possible. Answer — dp[n][k].

Let's imrove our solution. Notice, that as d we should use only divisors of k (which in the worst case would be 6720). As for gcd, we can easily find it in O(primes(k)), where primes(k) — number of primes in decomposition of k. We also need to renumber our divisors according to their prime decomposition.

To get AC in this problem you had to optimize described dp and add minimization of used elements' sum. Final complexity — O(n · divs(k) · primes(k)).

Solution

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

| Write comment?
»
8 years ago, # |
  Vote: I like it +4 Vote: I do not like it

My take on 703C - Chris and Road:

For each vertex of the polygon, consider its y coordinate and the point in time where it crosses the path of the pedestrian (which may be negative). There are two possibilites:

a) We can cross before the bus reaches us. Whether this is possible can be easily checked by checking if for each vertex of the polygon, that the pedestrian can be at 0,y earlier than when the point of the polygon crosses the path. In this case the answer is simply w / u.

b) In the other case, we have to go behind the bus. In this case, for each vertex, calculate ti = (w - yi) / u + xi / v. This is the time the pedestrian would need to reach the other side if the she started from each vertex of the bus right when it crosses the path. Because the polygon is convex, we know that this is the optimal valid path behind the bus iff we pick i such that ti is maximal. The only exception is when we actually cannot reach the required yi at least as fast as the bus. So the answer is max(t1, t2, ..., tn, w / u).

All of this can be computed in O(n).

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

    Hi, can you please explain how the optimal path would be the one for which t is maximum in case (b)

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

      http://codeforces.com/contest/703/submission/19666971

      Just sort the points by increasing y, and check for the events which happens later: The point (x,y) passing through point (0,y) or the time required for Chris to reach (0,y) from the previous y position.

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

      Consider all possible paths behind the bus. We can always improve the time we need to reach the other side by starting earlier, i.e. moving out path to the left in the projected interpretation of the problem. If we start with a path which does not touch the bus at all, we can keep starting earlier until we touch the bus somewhere (or until we don't wait at all and still reach the other side behind the bus). We don't want to start earlier once we exactly touch some vertex i, since that would mean that we hit the bus at yi. The time we coincide with i is xi / v. From there, we need (w - yi) / u more seconds to finish crossing the street. The sum of these two times is ti. Since we continually improve our time by starting earlier as described above and we picked the first possible ti, we have picked the maximum ti. Picking any tj other than the maximum ti would describe a path that hits the bus at yi.

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

        Great solution! I love it. I have a question. Since we are picking the leftmost path which doesn't collide with the bus, does it make sense to just look for the point which has the highest x-coordinate and calculate the t = (w-y)/u + x/v for this coordinate alone?

        Since this should be the maximum t anyway, it will produce the same answer as yours. If I am mistaken, could you provide me with a counter example? Thanks!

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

          Here is a counterexample:

          4 1 2 1
          0 0
          1 0
          2 1
          0 1
          

          The vertex with maximum t is 1 0.

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

When will practice be opened? It still shows system test is pending and I can't submit my code. :(

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

can't understand problem D. Please provide source code on it.

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

    My solution

    I used Fenwick tree (ll bit[N]) and did a coordinate compression (int b[N] — since values are very big, but we have at most 1^6 different values).

    The ideia is that to calculate XOR of elements that appear even times is the same as the XOR between the XOR of elements that appear odd times (and that's the same as the XOR of the whole subsegment, because if some element appear twice it will cancel in XOR) and the XOR of unique elements in the subsegment. It can be a little hard to understand, but write on paper and go testing small numbers to see that this is true.

    The XOR of the whole segment can be easily calculated using partial sum (in this case partial XOR: pre[i] = pre[i-1]^a[i]).

    The XOR of unique elements can be found using a range query/point update data structure (Fenwick tree or Segment Tree) and iterating in each element of the array. Since you want only unique elements, you store the rightmost/last appearance of some element (because you will query from the element you are to the left, so storing the rightmost appearance assures the element you be contained in every segment that begins before the last appearance). To do this you iterate from i = 1 to n, if element already inserted (last[element[i]] != 0) you remove the element from this position (using the point update of the data structure). After that you update the last position of this element and add the element in this new position. For every query that right end is equal to i you query in your data structure for the query range (XOR of unique elements in range) and XOR with the whole segment (pre[r]^pre[l-1] — XOR of elements that appear odd times), and that's the answer of the given query.

    Hope this helps. Any doubts be free to reply.

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

      hello my solution got wrong answer on test 14. My idea is similar to above. i used segment tree. Please check it and i don't know where i made mistake. http://codeforces.com/contest/703/submission/19666191

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

        I've being testing many things in your code. Found a small issue but was not the main problem... After 1h or more I decided to change your defines...

        The first problem is the long long instead of int. Since the numbers can be bigger as 10^9, the XOR can be bigger than int limit. You can use unsigned int, but long long is the safer way.

        The other issue (the hard to find one) is with defines... Try to use const instead of defines for constant numbers. You used #define _N (int)1e6+5, and declaring the variables you did tree[_N * 10]. Resolving the define will result in tree[(int)1e6 + 5*10]. You see the issue, right? Defines are bad in many ways, so use defines only if you can't use other things (use typedef to create new types, as typedef long long ll; to shorten long long, and const to constant values, as const int _N = 1e6+5;).

        Your solution with modifications

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

          Yes. Thank you very much. I'm very glad to understand my mistake.

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

          Can you please explain how the xor can exceed the int limit? According to my calculations ceil(lg(1o^9) = 30. So the maximum xor will have at most 30 bits set which is 2^30-1 and is less than 2^31-1 (int limit).

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

            You're right, xor won't exceed int limit. I saw this after posting and decided not to edit. Anyway using long long won't do bad, but is not necessary in this case, thanks for replying!

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

      In case if anyone still gets TLE in this task, using un-tied cin & cout is not good enough this time. Better rewrite your code with scanf printf.

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

      Good Job kogyblack! Good Explanation :)

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

In problem E, why can't we use the euclidean algorithm to find the gcd between d and a[i]?

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

How do I know when to use Mo's algorithm for such questions? I have done similar problems with similar constraints or even higher constraints using Mo's Algorithm. In contest I tried optimizing Mo's algorithm several times and as a result got 5 TLEs on case 14 :(

So please tell me if is there is a way I can identify if O(n*sqrt(n)) will work for a problem with primary constraint N lying around 10^6. If not,then for what values of N should I go for Mo's algo.

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

    O(N * sqrt(N)) doesn't work here.
    Intended solution is O(N * log(N))
    here N  =  106
    so O(N * sqrt(N)) would be of order 109, which is hard to pass even though you make good I/O optimisation.
    Use MO's Algorithm for N  =  105 order.

    • »
      »
      »
      8 years ago, # ^ |
      Rev. 4   Vote: I like it +9 Vote: I do not like it

      I wouldn't say that 109 is "hard to pass". 10^9 simple operations' time is close to one second (See this: 19666793)

      Mo is known to have VERY small constant factor, so it might pass in 3.5 seconds.

      However this guy didn't manage to pass, even though his constant factor seems to be really small.

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

        Even this guy didn't manage to pass :)

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

          But this guy managed to pass :)

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

            But passing in 3.5s with Mo isn't only possible in CF? I mean CF judge looks so fast than any other judges.

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

Yay! I have the same solution for C. Here is some explanations from me with easy checking whether line intersect with rectangle:

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

In problem C, how to determine that a line intersects the polygon?

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

    Line intersects polygon if it intersects any of it's edges.

    Simply iterate through all edges and check if they intersect with line or not.

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

    You just need to check the set of signs of values calculated for each polygon point by the line equation Ax + By + C. If there are not both 1 and  - 1 simultaneously, all points lie from the only side of the line, and it does not cross the polygon.

»
8 years ago, # |
  Vote: I like it +1 Vote: I do not like it

Can someone please elaborate the solution to E? I don't understand the dp relation. Thanks!

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

    The point is to find the minimum step of reaching d by taking the prefix array of i. You either take the previous prefix value, or track it from the previous point, where taking a[i] will transfer to the state lcm(d,a[i]) (while only considering the prime components of k since other doesn't matter)

    I am quite lost in the implementation of the optimization though, so I can't help you out in that part. :/

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

Has anyone solved Div2D with persistent segment tree . My submission is giving Runtime Error on TestCase 14.I don't have any clue of the reason and have allocated more than enough memory (I think). The idea of pst's root[i] is to store xor of distinct numbers which are as close to it as possible.

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

    I'm not sure. Our solution with persistent segment tree works even slower, than our solution with Mo's algo.

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

      Can you share your persistent segment tree solution. My solution answers queries in O(logn) online.

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

        I think you didn't apply for enough space...You applied 2111111 * 8 == 1700000 Nodes , but you need at least 1000000 * log( 1000000 ) = 20000000 Nodes...

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

I am confused...the man's speed can be always changing, for example ,v=2t^2,then may be less time?? i mean ,how to prove y = (u / v) · (x  -  t0) can create the minimum answer?

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

Hi everyone.. I am trying to understand the solution of problem D . I am not able to figure out what does moving to next position in line "When moving to the next position we have to make the following assignments: " mean. Also while taking the sum if last position of ai is not I shouldn't we subtract 1 from the sum as 1 has been added before for a repeating element. That is with my assumption that count array shows number of times ith element is present.. Thanks.

»
8 years ago, # |
  Vote: I like it +12 Vote: I do not like it

IN 703C,the equation you wrote, dimensions does not match, one is time, another is distance.. The correct equation is y = (u/v)(x-v*t)

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

What is the variable 'd' in problem 703E — Мишка и делители tutorial?

Can someone please explain.

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

    Fixed. There should be "Suppose dp[i][d] is the minimal number of elements on prefix of size i, that their product is divisible by d".

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

Anyone solved D using segment tree because I have no idea about Fenwick tree?

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

    Don't know if you are still alive :P but here you go 92688725

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

      This is My Submission for problem D can you tell why this submission is showing TLE. I have used segment tree.

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

        Sorry I got the mistake ;).

        sort(all(Q), [](vll& a, vll& b){return a[1] < b[1];});
        

        Earlier I was passing a and b as value.

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

I am not able to pass problem E with the same complexity mentioned in the editorial. I think the time limit is too tight. Please check the solution.

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

    I tried similar solution as yours and got TLE too. the function gcd is log(k), whick is bigger than prime(k), and that's why the tutorial use some other method to calculate gcd.

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

Since k can be 10^12 ,how to get the prime factors of k ?

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

Time limit on E is very tight. I had to hard code cases.

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

Problem E: "We also need to renumber our divisors according to their prime decomposition."

What does it exactly mean? Why do we even have to decompose the divisors?

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

For problem Div2D, i have used MO's algorithm.But my code got TLE in case number 15!Is there any way to solve this problem using MO ?Please,help me then! 32085407

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

    You need:

    • fastest IO (fread / fwrite)

    • compress coordinates

    • rearrange the coordinates in the original order of given array from left to right

    • use optimized Mo's compare function

    sgtlaugh solution

    my solution

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

I think problem E it is not very difficult, but it has a very adjusted TL, IMO autors should have proposed a more comfortable TL.

My submission 34821624

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

Perhaps the problem E's time limit is too harsh. Now Codeforces has removed C++11,and the fastest solution of C++14 is 600+ms,but the limit is only 1s.

So could you plz expand it to 2s or more?

thx