VladProg's blog

Codeforces Round #499 — editorial
By VladProg, 6 years ago, translation, In English

1011A - Stages

Author: Mike Mirzayanov (MikeMirzayanov).

Tutorial
Solution

1011B - Planning The Expedition

Author: Mike Mirzayanov (MikeMirzayanov).

Tutorial
Solution

1011C - Fly / 1010A - Fly

Author: Vladislav Zavodnik (VladProg).

Tutorial
Solution

1011D - Rocket / 1010B - Rocket

Author: Vladislav Zavodnik (VladProg).

Tutorial
Solution

1011E - Border / 1010C - Border

Author: Vladislav Zavodnik (VladProg).

Tutorial
Solution

1011F - Mars rover / 1010D - Mars rover

Author: Vladislav Zavodnik (VladProg).

Tutorial
Solution

1010E - Store

Author: Vladislav Zavodnik (VladProg).

Tutorial
Solution

1010F - Tree

Authors: Ildar Gainullin (300iq) and Dmitry Sayutin (cdkrot).

Tutorial
Solution
  • Vote: I like it
  • +109
  • Vote: I do not like it

Comments Comments (73)
| Write comment?
»
6 years ago, # |
  Vote: I like it +51 Vote: I do not like it

For Rocket bonus, you can check 1 then 2 then 3 etc. while recording p[] values. When you want to search for the answer do not include already searched values. which will turn 1073741853 to 1073741823. which can be done with 30 iteration.

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

I guess that solution to F is exactly the same as my one from this comment: http://codeforces.net/blog/entry/60806#comment-447283, but here author is just collecting and keeping polynomials from heavy path.

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

    Yup, it seems that my solution is exactly the same as yours :)

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

mlogm div2 B solution with data structures (probably not the mlogm the tutorial wants xD)

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

    Another O(mlogm) solution is to binary search the answer with lower bound of 0 and upper bound of m.

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

      Yeah that's what the tutorial wants, and what most people went for. I just decided to share some interesting alternative, even if not the best.

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

        I think you just want to show everyone that you did a badass code with segment tree, so everyone should think that you were cool

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

Many participants have solution on div1E based on finding the number of points inside a box in 3D space. How to do this effectively?

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

    Offline with scanline + 2d segment tree, for example

    → Reply
    • »
      »
      »
      6 years ago, # ^ |
      ← Rev. 2   Vote: I like it -11 Vote: I do not like it

      Could you please tell me if we can use three one-dimensional segment tree to solve Div1.E?

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

        No I doesn't work like that, because for 3D segtree (which you almost always never need because you can remove a dimension with sweep or something) you are querying for three constraints.

        So its something like Q(A and B and C) where A,B,C are [left,right] range query in some dimension.

        But using three one dimension is like Q(A) + Q(B) + Q(C).

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

The English is not very good. But thanks for the editorial, I managed to understand.

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

In problem E, we can eliminate another coordinate from the data structure by taking advantage of the fact that we can process queries offline, so we can sort them by 0-th coordinate. This results in a O(nlogn) solution that uses only simple 1D Fenwick tree with min operation as the data structure.

Not very readable code: http://codeforces.net/contest/1010/submission/40820468

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

I think that Div 1. E can be solved with a simple segment tree.

First, just as the tutorial says, we check the possibility of "INCORRECT". Then, each of the m moments can be treated as a open-ended 3D-box, i.e. denote the moment as (xi, yi, zi), if xi < xl, the restriction for knowing the moment (x, y, z) is "CLOSED" using this knowledge will be x ≤ xi, if xl ≤ xi ≤ xr, there will be no restriction for x, and if xi > xr, the restriction will be x ≥ xi. The same goes for yi and zi. Putting the 3 restrictions together gives you a open-ended 3D-box. The query is actually asking whether each point is in any of them.

This is not difficult as it seems to be. First, there are actually 8 kinds of different boxes, regarding the  ≥  or  ≤  sign. We can deal with them by mirroring the coordinate and do the same process 8 times, so we only need to focus on {(x, y, z)|x ≤ xi, y ≤ yi, z ≤ zi} situations. This is done by a scanning line trick. We sort both the queries and the boxes by descending x coordinate. Then each time we need to update something like {(y, z)|y ≤ yi, z ≤ zi} when we meet a box, which is simply done by a segment tree in the range of [1, ymax], maintaining the maximum value of zi on yi so that there is a box covering {(y, z)|y = yi, z ≤ zi}.

My code: 40807344

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

My 3D segment tree (aka octree) with some constant optimizations passed E.

http://codeforces.net/contest/1010/submission/40822866

The asymptomatic complexity is , I believe. This seems terrible but it works.

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

    Complexity of your solution is definitely not as you described. Even for 10000 queries on the test of type:

    2 100000 10000
2 2 2
3 3 3
100000 100000 1
100000 100000 2
...
100000 100000 100000
99999 99999 99999
99999 99999 99999
...
99999 99999 99999

    your solution works in more than 2s on CF. So for 100000 queries it works almost 30s. https://ideone.com/VnJcp3

    I looked through your code and complexity of your solution looks like O(m + log(x·y·z)) per query. These lines of code:

        if(tree->p.size()<=LEAF_SIZE||(tl.x==th.x&&tl.y==th.y&&tl.z==th.z)){
        for(Point &p:tree->p)
            if(in_box(ql,qh,p))return true;
        return false;
    }

    can check all m points through recursive call. I checked it for this test and your in_box(ql,qh,p) above was called 100000 times for 1 query. So your solution has complexity O(m·k).

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

    I'm guessing you have some implementation issue in your octree, but that a nice idea! I tried implementing it in Java, and it's the only 3d range query solution that passed the time limit (577 ms).

    Here is some of the other implementation:

    577 ms Oct3Tree (https://codeforces.net/contest/1010/submission/40861402)

    TLE RangeDTree (https://codeforces.net/contest/1010/submission/40860248)

    TLE KDtree (https://codeforces.net/contest/1010/submission/40860860)

    I even tried using persistence Kd-Tree, but this didn't quite work either.

    I'm interested why the range-tree (which is in the same complexity as the octTree), didn't pass the tests, maybe I'm missing a bug somewhere...

    Anyway cool question, I really enjoyed it :)

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

A round to test who type faster.

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

could somebody please explain the editorial explanation for div2 E? why we are we considering multiples of gcd only?

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

    Using Euclidean proof? I don't know what it is in English, but only the multiples of gcd make the equation has a solution

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

    For any integer a and b with gcd(a,b)=D, there always exists integers x and y, such that ax + by = D. And here we can use gcd, as D is also bounded by K,in other words (ax + by)mod K = D mod K, so there always exists non-negative x and y.

    If we take gcd(a1,a2,...,an,K)=S, we will get the smallest last digit(other than 0) which we can be obtained using the denominations ( K is also included in the gcd because we need the last digit which is bounded by K).

    So multiples of S less than K will be the answer because there are the number of denominations are infinite.

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

      Thankyou Hemant.

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

      How are they accomodating for negative coefficients?,like in this eqn a1*x1 + a2*x2 = c , if some xi is negative then?

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

        If you try to do extended euclidean algorithm by hand, you will see this works for negative coefficient.

        Simple case:

        ax + by = d, where d = gcd(a,b)

        In many euclidian algorithm you define gcd(a,b) recursively like: gcd(a,b) = gcd(b, a mod b) and base case gcd(a, 0) = a

        Well actually, we know already x and y values for

        ax + by = a (here x = 1, y = 0)

        and

        ax + by = b (here x = 0, y = 1)

        Now we can use these values to find (x,y) such that

        ax + by = (a mod b)

        How?

        Ok so now you can recursivley apply this logic until you find good coefficients x and y that make it so ax+by = gcd(a,b).

        Of course, try some examples and you will notice some of these coefficients are negative. (since a mod b is just a-kb, it's not surprising)

        Now you can extend this to more than 2 numbers because gcd(a,b,c) is just gcd(gcd(a,b),c) and so on.

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

          But... Why x_i < 0 does not affect the calculation to problem (Div. 2) — E, can you explain me.

          Tutorial: Here some xi<0, But Natasha can add for each par a sufficiently large number, multiple k, that xi became greater than zero, the balance from dividing the amount of tax on k from this will not change.

          what does it mean? add sufficiently large number, multiple k, that xi became greater than zero.

          I think that considering negative xi means that Natasha receives money from martians (she should only pay to visit Mars). Example 12x1 + 20x2 = gcd (12,20) = 4 where x1 = 2, x2 = -1. How is x2 made positive?

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

            Once you find one set of coefficient, actually you can find infinite amount (and you can adjust the coefficients to be positive one)

            for example:

            ax + by = c

            but also means

            a(x+b) + b(y-a) = c

            And you can "adjust" it.

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

Solution Link : http://codeforces.net/contest/1011/submission/40827796 What is the error in the above solution? I used binary search for problem Div2C. The solution gets accepted if my high for binary search is 10^9+1 but not for 10^9.

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

    Comparing double value with integer gives you 1000000000.0000000 > 1000000000. So 1000000000.0000000 is considered wrong(as it exceeds 10^9) which in fact is right. Did the same mistake

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

    It is because, your first binary search.

    if(check(mid))
  	{
  		if(check(mid-1))
  			r=mid-1;
  		else
  			break;
  	}

    Let's say that l=10^9 and r=10^9 -> mid=10^9. when you called check(mid) function it returns true. It is obviously if you called check(mid-1), it will also return true and now your r will become 10^9 — 1; That's why when your first binary search is done, it will produce -1 (l>r)

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

      when l=r=10^9 and if check(mid) return true then obviously check(mid-1) will return false.

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

    Using both mid+1 and mid-1 doesn't work in this problem because you are ignoring all the real values from (mid, mid+1) and (mid-1, mid) when you transition in your search. Eventually it means even when you convert it to doubles, you will not find an answer because the integer bounds were wrong.

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

      I didn't get. Int the second search, I am iterating 200 times from mid-1 tomid which covers all the real values.

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

        Yes but you still do some "cutting" in your integer solution, and the incorrect bounds can carry over to your floating-point search because doing +1 and -1. Maybe it would work with 1e9+1 or mid+1, because of the offset, but the integer binary search is unnecessary and fundamentally wrong. It would be better if you started with floating point in the first place and fixed the iterations.

        → Reply
»
6 years ago, # |
← Rev. 2   Vote: I like it -8 Vote: I do not like it

Can someone please let me know why was I getting Runtime Error in test case 8 on Div2 Problem C? Code

Update : Extremely sorry, my link to code went wrong. Here is the Code

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

    Because n is up to 1000, and you collect both b[i]'s and c[i]'s into a, the size of a must be at least 2n.

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

Can someone share some good practice questions similar to 1011F.

Thank you.

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

Hey guys, can anybody help me with this BS solution for div2 C ? code

It gives wrong answer on test case 58.. I know it is precision problem since an iterative BS solution works if I do like 50+ iterations. But how should I fix precision when I have this non-iterative code, should I just change EPS value ?

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

    The answer in this test case is 109.

    If you write hi=1e9+EPS, then your solution will be accepted.

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

      Oh, I see the problem.. Thanks!!

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

can someone explain me the Div2 D question, not getting what is being asked in the question.

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

    You want to write a program to "guess" a number chosen by the judge.

    You can print out a number y, to which the judge will return you some information about whether the actual number, x, is less than, greater than, or equal to y (your guessed number).

    But sometimes the judge will lie and tell you x is less than y when really its the other way around. But the judge lies in a specific pattern of length n.

    Your program has to determine this pattern by guessing in some strategy, and after knowing this sequence try to guess the number x.

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

1011C (FLY) Can someone please explain how we arrived at the equation s+x=tx

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

    total mass = mass that all fuel can transport

    total mass = mass of rocket with fuel that not used in this iteration + mass of fuel that used in this iteration = s + x

    mass that all fuel can transport = fuel coefficient * mass of fuel that used in this iteration = tx

    s + x = tx

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

For 1010E : Doesn't a 2 dimensional segment tree take m² of memory ? How can this solution work without MLE ?

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

    Editorial says: "let's create a compressed two-dimensional segment tree". It takes only memory.

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

    If you allocate nodes on demand its only qlogm (q is amount of queries)

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

Hey guys, In 1011C — fly can someone point out the error in my code. It fails for test case 58 and is accepted when I increase upper bound of BS from 10^9 to 10^9+1. The reasoning is as follows for test case 58. L will keep approaching 10^9(as check(l) is false) until r — l < eps. At which point it enters the block and check(r) must be true. code

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

    The answer in this test case is 109. When you call check(109), it returns false because of presicion error.

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

      Thanks for replying. If that's the case then check(10^9) should return false even if I increase my upper_limit by one. However, when r = 10^9+1, it gets accepted (my answer is 1000000000.0000009537.) More specifically, can you elaborate more on "precision error".

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

        Computer can't save all infinity digits of real number, because it hasn't infinity memory. So it rounds the number. If the program does many operations on real numbers, this error will increase.

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

why is it important to flush the output in C/C++. I know that printf() is line-buffered, so wouldn't '\n' flush the output anyway?

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

    No. You can submit this code and this solution will get Idleness limit exceeded:

    code

    This solution will be correct if you add flush.

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

      I've already got an Idleness limit exceeded without fflush(). I'm just wondering why doesn't it work with simple '\n'.

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

        \n is only character. It doesn't flushes output. I don't know why printf must flush output after \n.

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

          yes, '\n' does flush the output, but after searching, it turns out this only works when output is directed to the terminal, which is not the case with OJ. link

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

    I use endl with cout (C++ style). I learned this from a Chinese and its very helpful and ez to use than before, when I only knew about flush and when I forgot to write them, I got wa verdicts with lots of annoyance. Hope it will be useful to you. Happy coding!!!

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

this code have WA on test 1
problem div1. B 40930214
upd:another submission , now its WA

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

    try cout << i << endl; instead of cout << i;

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

    You forgot to print newline, problem requires that

    UPD: Oh, and if you use std::endl instead of '\n' then get rid of your flush, because then you flush twice (unecessary)

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

Can anyone explain Div2 E problem: Border. I am unable to understand from the tutorial.

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

nice problem F

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

Bro @vladProg i am not getting solution to 3 problem (FLY). Below line..

 then fuel can only take it to ourselves, and we need to take a rocket and a useful cargo (the mass of which is positive). That is, if t=1 at least for one t, it is necessary to deduce −1

Plzz help me. ThankYou!

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

    Let t = 1 at least for one t. If we will use x tons of fuel, it can lift or land only t·x = x tons of (fuel + rocket). So mass of the rocket is at most 0, that is impossible.

    → Reply
»
6 years ago, # |
← Rev. 2   Vote: I like it +8 Vote: I do not like it

What's wrong in my solution for third question FLY? Please someone tell.. http://codeforces.net/contest/1011/submission/40804467

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

    There is an overflow of type long long in your solution. Variables p and p_1 can be too big (p = a1 * ... * an * b1 * ... * bn ≤ 10001000 = 103000). If you send the Python code for example, it will be accepted, because Python supports big numbers.

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

What's wrong with my approach to problem Div1A? I binary-searched over the initial mass of the fuel. It's giving WA on test 58. Here is my solution

→ Reply