Блог пользователя VladProg

Автор VladProg, 6 лет назад, По-русски

1011A - Ступени

Автор: Михаил Мирзаянов (MikeMirzayanov).

Разбор
Решение

1011B - Планировние экспедиции

Автор: Михаил Мирзаянов (MikeMirzayanov).

Разбор
Решение

1011C - Полёт / 1010A - Полёт

Автор: Владислав Заводник (VladProg).

Разбор
Решение

1011D - Ракета / 1010B - Ракета

Автор: Владислав Заводник (VladProg).

Разбор
Решение

1011E - Граница / 1010C - Граница

Автор: Владислав Заводник (VladProg).

Разбор
Решение

1011F - Марсоход / 1010D - Марсоход

Автор: Владислав Заводник (VladProg).

Разбор
Решение

1010E - Магазин

Автор: Владислав Заводник (VladProg).

Разбор
Решение

1010F - Дерево

Авторы: Ильдар Гайнуллин (300iq) и Дмитрий Саютин (cdkrot).

Разбор
Решение
  • Проголосовать: нравится
  • +109
  • Проголосовать: не нравится

»
6 лет назад, # |
  Проголосовать: нравится +51 Проголосовать: не нравится

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.

»
6 лет назад, # |
  Проголосовать: нравится +19 Проголосовать: не нравится

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

»
6 лет назад, # |
Rev. 2   Проголосовать: нравится +5 Проголосовать: не нравится

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

Spoiler
»
6 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

  • »
    »
    6 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Offline with scanline + 2d segment tree, for example

    • »
      »
      »
      6 лет назад, # ^ |
      Rev. 2   Проголосовать: нравится -11 Проголосовать: не нравится

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

      • »
        »
        »
        »
        6 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

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

»
6 лет назад, # |
  Проголосовать: нравится +8 Проголосовать: не нравится

For div2 F, what I tried was merge all nots and mark it at some other operation node(with help of a xor store for each node). Now I believe the tree is complete binary tree . So if a leaf node is to be altered I can go down to that node and use the stored values in intermediatory nodes(as we do in a segment tree). The complexity for each such query would be O(log N) I think. So overall complexity should be : O(Nlog N). Even then my code gives TLE. Can someone point out if I am going wrong.

  • »
    »
    6 лет назад, # ^ |
      Проголосовать: нравится -8 Проголосовать: не нравится

    If I understand correctly, you think that tree depth can be maximum log(N). But it is wrong, because you can build edges only to the left or only to the right, so the depth will be N.

    • »
      »
      »
      6 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      Thanks !!! I got it now . I hadn't thought properly the previous night . The depth goes order n in a simple test case of a n ordered bamboo of ANDs inclined left with each AND node having an IN node to right . Anyways thanks MaxZubec

»
6 лет назад, # |
  Проголосовать: нравится +2 Проголосовать: не нравится

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

»
6 лет назад, # |
  Проголосовать: нравится +97 Проголосовать: не нравится

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.me/contest/1010/submission/40820468

»
6 лет назад, # |
  Проголосовать: нравится +50 Проголосовать: не нравится

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

»
6 лет назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

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

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

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

  • »
    »
    6 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится +35 Проголосовать: не нравится

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

  • »
    »
    6 лет назад, # ^ |
    Rev. 3   Проголосовать: нравится +8 Проголосовать: не нравится

    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.me/contest/1010/submission/40861402)

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

    TLE KDtree (https://codeforces.me/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 :)

»
6 лет назад, # |
  Проголосовать: нравится -24 Проголосовать: не нравится

A round to test who type faster.

»
6 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

  • »
    »
    6 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

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

  • »
    »
    6 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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.

    • »
      »
      »
      6 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      Thankyou Hemant.

    • »
      »
      »
      6 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

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

      • »
        »
        »
        »
        6 лет назад, # ^ |
          Проголосовать: нравится +5 Проголосовать: не нравится

        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.

        • »
          »
          »
          »
          »
          6 лет назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится

          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?

          • »
            »
            »
            »
            »
            »
            6 лет назад, # ^ |
            Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

            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.

»
6 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Solution Link : http://codeforces.me/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.

  • »
    »
    6 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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

  • »
    »
    6 лет назад, # ^ |
      Проголосовать: нравится -8 Проголосовать: не нравится

    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)

    • »
      »
      »
      6 лет назад, # ^ |
        Проголосовать: нравится -7 Проголосовать: не нравится

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

  • »
    »
    6 лет назад, # ^ |
      Проголосовать: нравится -8 Проголосовать: не нравится

    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.

    • »
      »
      »
      6 лет назад, # ^ |
        Проголосовать: нравится -8 Проголосовать: не нравится

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

      • »
        »
        »
        »
        6 лет назад, # ^ |
          Проголосовать: нравится -8 Проголосовать: не нравится

        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.

»
6 лет назад, # |
Rev. 2   Проголосовать: нравится -8 Проголосовать: не нравится

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

  • »
    »
    6 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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.

»
6 лет назад, # |
  Проголосовать: нравится -7 Проголосовать: не нравится

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

Thank you.

»
6 лет назад, # |
  Проголосовать: нравится +8 Проголосовать: не нравится

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 ?

»
6 лет назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

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

  • »
    »
    6 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

    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.

»
6 лет назад, # |
  Проголосовать: нравится -8 Проголосовать: не нравится

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

  • »
    »
    6 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

    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

»
6 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

  • »
    »
    6 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

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

  • »
    »
    6 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

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

»
6 лет назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

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

  • »
    »
    6 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

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

    • »
      »
      »
      6 лет назад, # ^ |
      Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

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

      • »
        »
        »
        »
        6 лет назад, # ^ |
          Проголосовать: нравится +1 Проголосовать: не нравится

        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.

»
6 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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?

  • »
    »
    6 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

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

    code

    This solution will be correct if you add flush.

    • »
      »
      »
      6 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

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

      • »
        »
        »
        »
        6 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

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

        • »
          »
          »
          »
          »
          6 лет назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится

          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

  • »
    »
    5 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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!!!

»
6 лет назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

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

  • »
    »
    6 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

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

  • »
    »
    6 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

    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)

»
6 лет назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

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

»
6 лет назад, # |
  Проголосовать: нравится +8 Проголосовать: не нравится

nice problem F

»
6 лет назад, # |
  Проголосовать: нравится +8 Проголосовать: не нравится

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!

  • »
    »
    6 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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.

»
6 лет назад, # |
Rev. 2   Проголосовать: нравится +8 Проголосовать: не нравится

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

  • »
    »
    6 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

    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
»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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