DmitryGrigorev's blog

By DmitryGrigorev, 4 weeks ago, translation, In English,

Hi, Codeforces! I'm glad to invite everybody to the #489 Codeforces Round, which will be held as soon as tomorrow, on Monday, June 18, 2018 at 19:35. The round will be rated for all participants from the second division (with rating below than 2100). As usually, we will be glad to see participants from the first division out of competition!

Problems for the round have been invented and prepared by us, pupils of Moscow school №2007, Dmitry DmitryGrigorev Grigorev and Fedor ushakov.fedor Ushakov. We want to give thanks to Andrew GreenGrape Raiskiy for his aid in preparing and testing of the problems, to Ildar 300iq Gainullin and to AmirReza Arpa PoorAkhavan who have tested our problems too and to the coordinator Nikolay KAN Kalinin, since our sometimes strange and undeveloped ideas have become eventually the Codeforces round. Also, we say thank you to Mike MikeMirzayanov Mirzayanov for his unbelievable Codeforces and Polygon platforms.

You will receive 5 problems and 2 hours for solving it. During the round you will be helping for an extraordinary girl Nastya, who has been living in Byteland and sometimes receives very strange gifts for her birthday :).

Score distribution will be announced, traditionally, closer to the start of the contest.

We're holding our the first and, I hope, not the last round in Codeforces, so I hope a lot you will like our problems. Please, read all the problems. Anyway, I wish luck and high rating for all the participants!

I'm looking forward your participation.

UPD Score distribution is standart — 500-1000-1500-2000-2500

UPD2 Thank you for your participation in the contest! It's very-very pleasant for me if you like the problems, and I'm sorry if you don't :) I hope the next my contest will be even better, than this. Thank you for all!

List of the winners of the contest:

Div.2

  1. sminem

  2. guIRELItAr

  3. YaDon4ick

  4. q-O_O-p

  5. pajenegod

Div.1 + Div.2

  1. dotorya

  2. Benq

  3. anta

  4. sminem

  5. kevinsogo

My frank congratulations for all the winners!

UPD3

Editorial is here

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

»
4 weeks ago, # |
  Vote: I like it -56 Vote: I do not like it

Is it rated? don't downvote plz, tomorrow is my birthday

»
4 weeks ago, # |
  Vote: I like it +17 Vote: I do not like it

Finally someone remembered to thank both KAN and MikeMirzayanov.Hoping it would be a good round after the last one.Good Luck everyone.

  • »
    »
    4 weeks ago, # ^ |
      Vote: I like it -41 Vote: I do not like it

    is that true ??

    any one mention KAN and MikeMirzayanov will have upVotes ?

    KAN & MikeMirzayanov

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

      You got it wrong it's not the name but the thanks part for the work they do for us in preparing contests and updating codeforces on a regular basis.

»
4 weeks ago, # |
  Vote: I like it -27 Vote: I do not like it

score distribution ?

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

    It will probably be announced before the contest

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

    just saw your graph! You have my respect, mate!

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

    Of course, it will be announced before the contest. I'm sorry, I forgot to write it in the English announcement.

»
4 weeks ago, # |
  Vote: I like it -32 Vote: I do not like it

Usually strange gifts will transferred to someone else later. I predict that we will become this "someone else". However, in addition, Nastya will tell us what to do with our gift.

Nastya forces us to do strange things. Do not be like Nastya.

»
4 weeks ago, # |
  Vote: I like it -26 Vote: I do not like it
Spoiler
»
4 weeks ago, # |
  Vote: I like it +18 Vote: I do not like it

I was hoping to see one thematic contest of the world cup

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

    creates confusion for non followers and boring too

»
4 weeks ago, # |
  Vote: I like it +8 Vote: I do not like it

hoping to see more of mathematics ,all time favorite GreenGrape

»
4 weeks ago, # |
  Vote: I like it +4 Vote: I do not like it

Getting 502 Gateway error, hope that will be fine at contest time :)

»
4 weeks ago, # |
  Vote: I like it +4 Vote: I do not like it

Expecting a good contest....

»
4 weeks ago, # |
  Vote: I like it +6 Vote: I do not like it

Score distribution?

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

10 sec to go

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

In problem B the 2nd test case also includes the pair (2,6) and (6,2) Sorry i realize now that was my mistake

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

Too keked

»
4 weeks ago, # |
  Vote: I like it -10 Vote: I do not like it

In the problem C : Also, you should find the answer modulo 10^9+7 Can someone explain what this means,please?

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

    You should ask questions on "problems" page. There you can get answer momentarily.

    If the answer is A, you should print the remainder of division of A on 109 + 7.

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

Hi, in problem C im having WA on test number 2. However on my computer (with the same code) it gives the correct answer. Can someone check this out please?EDIT:It was my bad, sorry.

»
4 weeks ago, # |
  Vote: I like it +31 Vote: I do not like it

Wtf, math contest.

»
4 weeks ago, # |
  Vote: I like it +84 Vote: I do not like it

Mathforces Round #489 (Div. 2)

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

What is unexpected verdict when trying to hack problem C?

»
4 weeks ago, # |
  Vote: I like it +1 Vote: I do not like it

Drunken and sleepy ㅜ_ㅜ

»
4 weeks ago, # |
Rev. 2   Vote: I like it +121 Vote: I do not like it
»
4 weeks ago, # |
  Vote: I like it +1 Vote: I do not like it

How to solve div-2 B?

  • »
    »
    4 weeks ago, # ^ |
    Rev. 2   Vote: I like it +5 Vote: I do not like it

    There are two numbers. Obviously, since gcd is x, therefore common factor is x. so now both have factor x. So first number is in form a*x and second is in b*x and gcd(a, b) must be equal to 1. Since both number can't have other than x. Now GCD* LCM = first_number * second number. So x*y = (x*a) * (b*x) So y/x = a*b so we need to find all pairs (a, b) where gcd(a, b) ==1 && min(a*x, b*x)>=l && max(a*x, b*x)<=r and damn this count is the answer. There is just one catch, that y must be divisible by x. Otherwise the answer will be 0.

»
4 weeks ago, # |
  Vote: I like it +1 Vote: I do not like it

How to solve Div 2 B ?

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

    If y is not divisible by x, answer is 0. Otherwise, all pair (a, b) that satisfy the condition can be represented by (x * a', x * b'). Let , , . Now the problem is counting number of pair (a', b') in range [l', r'] such that GCD(a', b') = 1 and LCM(a', b') = y'.

    This can be done by iterate over all divisor d of y' and check if pair satisfy all the condition above.

    My implementation

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

      I think its can be done just by iterate over all divisor d of y

      and check if each pair count number of pair satisfy all the condition:
      
      l<=a<=r and l<=b<=r and gcd(a,b) = x and lcm(a,b) = y
      

      its can be done inO(d^2) where d is number of divisor of y...

      My implementation
  • »
    »
    4 weeks ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

    There are two numbers. Obviously, since gcd is x, therefore common factor is x. so now both have factor x. So first number is in form a*x and second is in b*y and gcd(a, b) must be equal to 1. Since both number can't have other than x. Now GCD* LCM = first_number * second number. So x*y = (x*a) * (b*x) So y/x = a*b so we need to find all pairs (a, b) where gcd(a, b) ==1 && min(a*x, b*x)>=l && max(a*x, b*x)<=r and damn this count is the answer. There is just one catch, that y must be divisible by x. Otherwise the answer will be 0.

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

      why min(a*x, b*x) >= l and not a*x >= l && b*x >= l ??

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

        You have to check both a*x>=l && a*x<=r && b*x<=r && b*x>=l. I done it in two statements min(a*x, b*x) >=l Since if minimum is greater than l, then the number which is greater than or equal to other number will always be greater than l. Same goes for max(a*x, b*x)<=r Since max of both number is less than r So the other number (which is less then the first one) will always be less than r. You can always check all four statements if you like. a*x>=l && a*x<=r && b*x<=r && b*x>=l.

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

          Yeah. Sorry that was a stupid question! By the way, can you explain the case for 0. why would it be 0?

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

            First of all question was not stupid. It was cool. Your solution got a problem. I, myself got 2 WA on this one. Secondly as i told you two numbers are in form a*x, and b*x Now lcm * gcd = product of number (for 2 numbers) so y*x= a*x * b*x so y=a*b*x so y must be divisible by x. if not divisible you can never find any a, b irrespective of l and r. So the count is 0 in such case.

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

              Got it Bro, Thanks :) That's what is missing in my solution, The TC 5.

  • »
    »
    4 weeks ago, # ^ |
    Rev. 3   Vote: I like it +6 Vote: I do not like it
    1. Find the prime factors of y/x
    2. For those prime factors which are present more than once, replace them with their product. For example: 12 = 2*2*2*3*5*5 should be made 12 = 3*8*125. Store these in a vector, say, "facts".
    3. It can be noted that size of vector "facts" is not more 15. So we can iterate on all subsets of facts to multiply each value of facts to either a or b. (a and b are numbers to be found). This can be done using bitmasks. For calculated values of a and b, check if they are between l and r, and increment the ans variable.
    4. Check specially for case when y is not divisible by x, and the case when a=b. Here is my solution 39374707
    • »
      »
      »
      4 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      thats exactly wha i did and i get wa on test 9..... https://pastebin.com/bCfGhsx6

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

        You can refer to my solution 39374707

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

        I'm not able to compile yours on JAVA compiler. Just check on test case 1 1000 3 100 The answer must be 0. I think you didn't check if y is divisible by x or not If not divisible then the answer is always 0.

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

    Simple Explanation is as follows:
    LCM(a, b) = a * b / GCD(a,b) ....... eq(1)
    and if g = GCD(a, b) you can write a = p * g ; b = q * g such that p & q are coprime i.e. GCD(p, q) = 1
    So above equation 1 can be rewritten as
    LCM(a, b) = ((p * g)*(q * g))/g
    LCM(a, b) = p * q * g ; where g is gcd(a,b)
    So now problem became: for given integers y and r , count number of unordered pair (p,q) such that y = p * q * r and p & q are coprime i.e gcd(p, q) = 1.
    That you can do in O(sqrt(N))
    Ref Solution

»
4 weeks ago, # |
  Vote: I like it +15 Vote: I do not like it

How to solve D?

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

    I thought of Divide & Conquer based solution but couldn't merge efficiently.

    If somebody solved like this, then please help how!

  • »
    »
    4 weeks ago, # ^ |
    Rev. 2   Vote: I like it +76 Vote: I do not like it

    Notice that the product will get big really fast. So for each starting index you can just iterate over the end index until the product gets too big (e.g.  > 2·1018). This will have runtime .

    The only problem with this approach is that this doesn't hold if there are a lot of 1s in it. But you can modify the approach from above so that you jump over the 1s, and check in O(1) if there is a solution (there can be only one) with the 1s that you jumped over..

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

      Really nice and simple. Thank you!

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

    Couldn't code it in the time I had, but my idea was something like this:

    I stored the sum upto n numbers in an array, and the value of k for the first n numbers taken consecutively in another array k[n]. Now, for every element for which k[i]>=k(required), just check if there are consecutive numbers up back till the last element with this property.

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

    I've compressed segments, that contains only "1". Then you can just bruteforce all segments ([0; 0], [0; 1], ... [0; n-1], [1; 1], [1; 2], ...), refreshing p and s for O(1) and breaking when p>z, where z=(2*10^5)*(10^8)*(10^5).

    It's working for O(n*log(z)), but you must handle overwflows carefuly.

»
4 weeks ago, # |
  Vote: I like it +2 Vote: I do not like it

my incorrect (WA on pretest 7) solution for B — Nastya Studies Informatics is to find all factors of y, then generate all pair, if the pair satisfy gcd(first, second) == x && lcm(first, second) == y then increment result

what is wrong with the solution?

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

    You should check the case 1 1 1 1

    It cost me 3 WAs as well :(

    Edit: Answer for this case is 1 BTW, it gave me 2 due to an error in my code only for this specific case.

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

      my code output for case 1 1 1 1 is 1

      what it should be?

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

        Oh wait... have you checked both numbers in each pair >=l and <=r as well?

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

    You wrote in the program:

    int lcm(int a, int b)
    {
        return (a*b)/gcd(a, b);
    }
    

    If a and b are too big, it can be overflow (109·109 = 1018 >  maximum value of int).

    For example:

    • test case: 1000000000 1000000000 1000000000 1000000000

    • correct answer: 1

    • your output: 0

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

      oh thanks! got accepted on practice submit because of that

      that was some noob mistake :( i should check any overflow case later

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

        Pro tip: write #define int long long at the beginning of every solution and use signed main().

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

          What's the difference between int main() and signed main()?

          • »
            »
            »
            »
            »
            »
            4 weeks ago, # ^ |
            Rev. 2   Vote: I like it +5 Vote: I do not like it

            I think that if you do the define the compiler will think you wrote long long main and it would say that it's an error, but if you write signed main() it would be alright

»
4 weeks ago, # |
  Vote: I like it -57 Vote: I do not like it

worst contest with no creativity

»
4 weeks ago, # |
  Vote: I like it +3 Vote: I do not like it

Was E square root decomposition?

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

    I tried a sqrt approach, it was TLE 13. I was using unordered_maps, so I tried to implement hashes, but didn't finished in time. I think there is a log solution

    • »
      »
      »
      4 weeks ago, # ^ |
      Rev. 2   Vote: I like it +3 Vote: I do not like it

      It's too slow solution, the same our solution worked >10 sec

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

      Usually if you think it is solvable with sqrt-decomposition, dump the idea and look for a better solution. In most the cases you would be right.

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

    Of course, No :)

    Idea is simple, there are not many positions that greater than sum of previous.

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

      can you explain more ?

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

        It likes fibonacci sequence, there are little terms  ≤ 109. So what you need to do is just pick the maximum until it less than or equals 0.

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

          The way I thought about the problem was to always start searching at the first index i = 0, and if that index wasn't the shaman-king then go to the smallest index j such that j > i and aj  ≥  sum(A[: i + 1]). Continue doing this until there is no such index j. All of this can be done quickly using segment trees. Worst case aj should double in size (not Fibonacci) for each iteration, and all of the segment tree operations will run in time so my solution should run in . 39387502.

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

          chemthan Could you please explain this in brief?

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

            Assuming i1 < i2 < ... < ik are all positions d such that ad > a1 + a2 + ... + ad - 1. Then obviously aic ≥ ai1 + ai2 + ... + aic - 1 + 1. We have: ai1 ≥ 0, ai2 ≥ 1, ai3 ≥ 2, ai4 ≥ 4, .... Because ai ≤ 109 so the number of terms k is not big.

            Then let fd = ad - ad - 1 - ad - 2... - a1, using a segment tree to get all d s.t. fd ≥ 0. The number of d s.t. fd > 0 is less than log2(109) so each query we get out at most that number until fd ≤ 0.

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

    Hey My square root decomposition solution 39389380 passed after contest. (missed submitting during contest by 1 minute). Have a look.

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

PS: Found mistake . It doesnt work, Sorry

»
4 weeks ago, # |
  Vote: I like it +29 Vote: I do not like it

It was very nice contest:::::: thanks

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

pretest #12 of C? any hints please verdict- WA

Edit this is the code please tell me whats wrong-http://p.ip.fi/_4l8

Update- I got it thanks for looking over my code everyone. In python n//2 and int(n/2) are not the same it looks like.

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

when will the rating changes happen ? (sorry for bad english)

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

    There is a chrome extension called CF-Predictor

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

      i know about it , and i have it ,but that does not mean all of my problems(a,b) will be accepted.

»
4 weeks ago, # |
Rev. 2   Vote: I like it -14 Vote: I do not like it

I don't like math problems.

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

I read only A, B and C, but looked more a math contest than a programming contest to me! Thanks to the author, anyways.

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

    Programming contest are half logics and half maths.

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

Managed to solve A,B,C. How to solve D?

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

    I think the main idea is that the maximum possible product is TOTALSUM*k, so there can be at most log_2(TOTALSUM*k) elements larger than 1 in a valid array.

    Hence we can bruteforce over all possible (i,j) where i is the position of the first element larger than 1 in the array and j is the last position.

    Once you have that you just need to look at how many extra ones you can add to the left of i and to the right of j.

    I did this but I made a mistake I guess.

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

What was Test case 4 for C?

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

    k = 0, I think.

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

    i guess its y := 0

    ans should be (x<<1)%M

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

    Likely your program didn't pass that test case due to overflow. (That's what happened to me in the first attempt)

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

    Darn. I missed ONE mod sign :(

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

      I did everything right , just took 64 as 2^8 and used 2^k instead of 2k somewhere and messed up the whole thing.

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

    it was x=0 i think;(

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

How was in Problem C 'n==1' solved??

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

    Just as n==2,n==3,n==4 and so on.

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

    because at the end there will be twice the dresses, but there can be one less dress with 50% probability, so at the end there will be 2 * x and 2x + 1 dresses each with 50% prob. Rest is simple.

    This gives f0 = x

    answer is twice of fn

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

I have a doubt. Suppose I submit a solution which passes all pretest. Then I submit a solution which fails on pretest. Will then only my 1st solution be considered ? Or i will have some penalties?

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

My idea for D:

at most I will multiply with 62 numbers greater than 1, so for every number I store the next number greater than 1, and I should take care of the ones between, am I missing something???

»
4 weeks ago, # |
  Vote: I like it +16 Vote: I do not like it

RIP ratings.

»
4 weeks ago, # |
  Vote: I like it +3 Vote: I do not like it

This round makes me realize how poor my math is.TAT.

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

In problem A i was having time limit exceeded on pretest 6 as the judgement. Did any one face the same problem and knows how to fix that?

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

    your code link ??

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

        It's kinda obvious your solution works in O(n^2) for n = 1e5. No surprise you got TL.

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

          can you explain more why that obvious?

          • »
            »
            »
            »
            »
            »
            4 weeks ago, # ^ |
            Rev. 2   Vote: I like it -18 Vote: I do not like it

            _

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

              1) He said he got TL6, not WA1. He just post the wrong link. 2) It's obvious that is was some debug output and he undestands he shouldn't use printf instead of scanf. 3) Now he posted correct link.

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

            Suppose there is no a[i] = 0; Then your code is simmilar to:

            for (int i = 0; i < n-1; i++)
               for (int j = i + 1; j < n; j++)
               {
                   do_something();
               }
            

            Still not obvious?

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

              thanks! :) am a newbie dont know much so wasnt aware that nested loops of this sort are never fast enough

          • »
            »
            »
            »
            »
            »
            4 weeks ago, # ^ |
            Rev. 3   Vote: I like it +1 Vote: I do not like it

            There is a nested loop in your code:

            for(int i=0;i<n;i++){
              ...;
              for(int j=i+1;j<n;j++){
                ...;
              }
            }
            

            This nested loop takes O(n2) time.

            Note: For this problem, I recommend you to use set data structure.

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

            Your code complexity if N*N (as your code runs n times for every outer loop.) So n*n statements minimum. Generally 1 sec = 10^8 operations. and here n=10^5 so n*n = 10^10 so it will take 100 secs. That's why you are getting TLE. Hope it helps.

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

        bro you have used printf instead of scanf.....that's why tle and runtime type errors are coming.

»
4 weeks ago, # |
  Vote: I like it +13 Vote: I do not like it

div2B was not made for div2B.

»
4 weeks ago, # |
  Vote: I like it +9 Vote: I do not like it

Problem E was really nice.

»
4 weeks ago, # |
  Vote: I like it +3 Vote: I do not like it

How to solve DIV2 C?

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

    Observe that after k months, there can be 2k * x, 2k * x - 1, ... , 2k * x - (2k - 1) clothes in the wardrobe, with equal probability .

    By using definition of expected value, we find that the expected number of clothes after k months is . The answer to this problem is twice of this number, i.e. 2k(2x - 1) + 1.

    Note the special case: if x = 0, the answer is 0 no matter what k is.

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

    Let f(x, k) be the answer for input x and k.
    Then we have the recurrence,
    For k ≥ 1,

    and f(x, 0) = 2x.

    By induction, you get f(x, k) = 2k + 1x - 2k + 1.
    Use repeated squaring to evaluate the powers with the right modulus.

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

i find the penalty on re-submission kinda weird :(

»
4 weeks ago, # |
  Vote: I like it +1 Vote: I do not like it

Can D be solved using two pointer both starting from beginning ?

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

    nope. The solution comes from fact "ones are useless"

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

Forgot to take mod in C fml. Also can someone tell whats wrong with my code for D — http://codeforces.com/contest/992/submission/39387013 ?

»
4 weeks ago, # |
  Vote: I like it +62 Vote: I do not like it

B is a bit too hard, and the problem involved a lot of maths, but the problemset is nice overall. I liked B and D the most.

Also, I appreciate the fact that pretests is strong and included corner cases (n = 0 in C).

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

    Problem E smells like an interesting problem as well. It's the kind of problem you think you'd go like 'aaa, hmm, mkay, that's pretty cool' haha

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

      I didn't come up with that observation (I thought the upper bound is at first, so RIP). But now knowing that, I think E is also a cool problem.

»
4 weeks ago, # |
Rev. 2   Vote: I like it -15 Vote: I do not like it

A lot of Maths!

»
4 weeks ago, # |
  Vote: I like it -8 Vote: I do not like it

For problem E, can we solve sqrt(q) queries at a time by pre processing for each sqrt block. My idea is to find all the indices that are updated in that block and then we make a new array having all the subsequent indices that are not updated together as a same element. We can maintain the sum of that element and also create a map to check the sum requirement of all the indices in that element, while for indices that are updated, we can check if the prefix sum till that element is equal to that element. Time Complexity will be O(n * root(q) + q * root(n)).

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

What was test case 5 for c?

»
4 weeks ago, # |
  Vote: I like it +10 Vote: I do not like it

Solution of problem B already exists on the internet. link : Click . Found it after the contest!

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

    How to modify it to include the range specification?

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

      Edit:

      Nevermind, like a tilted fool I read the wrong block of code and didn't realize it wouldn't run in time, give me a minute

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

        That solution would give TLE because it iterates all the numbers until 1e9

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

      You can iterate over all the 2^k subsets and check range of product of each subset. You can do that because k will be less than 11 as the product grows rapidly. See primorials

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

      If you read the efficient solution which was given in the link above, you can see that the answer is 2^number_of_distinct_prime_factors(lcm/gcd). You can do this: bruteforce through all pairs of numbers that can be formed using distinct prime factors of lcm/gcd such that their multiplication is equal to lcm/gcd, and add to answer if both of them are in range [l,r]. That was my solution (not the best one i think, but it passed).

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

    Its not same at all. You also have to check if a and b are between l and r, which requires a lot more work.

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

      No .. it does'nt ... once you get the logic ... checking for a pair elements to lie in a particular range is not a big deal.

»
4 weeks ago, # |
  Vote: I like it +3 Vote: I do not like it

What is pretest 9 in D and why did it bend me over?

»
4 weeks ago, # |
  Vote: I like it +2 Vote: I do not like it

Thanks for strong pretest of Problem C. To me it was easier than Problem B.

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

    Same, I had problems with B corner cases and I didn't bother reading C because there was little time left. After the end of the contest I coded C in literally 5 minutes.

»
4 weeks ago, # |
  Vote: I like it +1 Vote: I do not like it

Why is the system testing happening so slow?

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

    I think is due to the many submissions for problem A.

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

pretest 5 in B? Coldnt pass it

»
4 weeks ago, # |
  Vote: I like it +44 Vote: I do not like it

Am I the only one who really loves math problems?) Thanks to authors, problems were really nice, though harder than ussual.

»
4 weeks ago, # |
  Vote: I like it +28 Vote: I do not like it

The math skills...

»
4 weeks ago, # |
  Vote: I like it +5 Vote: I do not like it

The amount of number theory and partial sums is strong with this one.

»
4 weeks ago, # |
  Vote: I like it +16 Vote: I do not like it

What could the test case 63 be for Div2 C?...I see many WA's on that test (including mine).

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

    x is multiple of 1000000007

    • »
      »
      »
      4 weeks ago, # ^ |
        Vote: I like it -26 Vote: I do not like it

      Such a cancer test case honestly.

      Bad luck keeps hitting me at contest.

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

        Such a cancer comment, honestly.

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

          Sorry the community if i'm being too negative or toxic,but honestly when i failed that test i can't hold the feeling,i feel like such a loser.

          Again,sorry for writing a stupid comment.

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

the writer of problem B is germa 66 fan

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

    How is problem B related to Germa 66? There's barely any backstory to the problem.

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

Is a lot of test case the reason of this very slow system testing ?

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

In problem D, what is the maximum p, such what p/s=k exists?

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

    well i know that you could just simulate the entire problem, like iterate for i, then for j with j > i and with some optimizations like, jump over sequences of 1 and when current p is much bigger than s + (n — j) because p rises much faster than s the situation is unrecoverable so you stop the second iteration because you are sure to have no solution with current i ans j' >= current j, Getting a nlogn complexity. Now for your question the answer is s * k

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

      1) s is not fixed. 2) If we say that s = n*max(a) and k=1e5, when p=2e18 can't exist, because all of the numbers would be 1e8, and that means 1e8^n=2e18, which is false.

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

    You can take

    108, 
    100300, 
    199700 × 1

    to get

    p = 1003·1010, s = 1003·105, k = 105.

    Not sure if that's the worst case, however.

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

    Intuition: k should be max (10^5). We would like to use a small number of numbers because otherwise, p is going to be extremely large. So we would use 2 numbers. We would like one number to have the maximum value. So the equation is (10^8*x)/(10^8+x)=k. X is slightly more than 10^5 -> maximum p is slightly more than 10^13.

    I didn't prove it but I think it's right and should be easy to actually prove.

    It could overflow even unsigned long long. I have checked that a*b < 10^y with log10(a) + log10(b) < y.

    Also, I've accidentally set the limit to 10^13 in my solution and it passed.

    UPD: yes, maybe such test is impossible to create so that's just an upper bound.

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

      I know that's no argument, but my solution passed with 10^11 as a limit :D

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

      I was for a minute scared, what product can be 2e18, because i used >= and not > :D

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

      Hello Qumeric In problem C : in this solution link i have used modInverse but in this solution link i haven't because i just had to divide the variable by 2 and my numerator is already %M.... Can you please tell me why my answer was accepted in the first case and not in the second? ( M = 1000000007)

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

        Let`s think answer is 500000004. Then before divide you should have 1000000008. But you use modulo calculations and you have 1 instead of 1000000008. If you use modulo inverse you get correct answer. But if you divide by 2 you get 0 (1/2 = 0).

»
4 weeks ago, # |
Rev. 2   Vote: I like it +77 Vote: I do not like it

Dear author(s),

Thanks for including n = 0 in pretests (Problem C). Thanks for not making it hackforces and saving my rating...

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

for C, the correct formula is 2^(k+1)*x — (2^k — 1) ? [after applying proper modulo] If yes, then why is my submission giving wrong answer? 39389996

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

    Should be overflow somethere.

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

    Take modulo of X before multiplying with 2^(k+1)

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

      Accepted, Thanks !

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

      Hello darkhorse7 In problem C : in this solution link i have used modInverse but in this solution link i haven't because i just had to divide the variable by 2 and my numerator is already %M.... Can you please tell me why my answer was accepted in the first case and not in the second? ( M = 1000000007)

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

        please attach the solution link

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

          oh sorry! in this solution link i have used modInverse but in this solution link i haven't because i just had to divide the variable by 2 and my numerator is already %M.... Can you please tell me why my answer was accepted in the first case and not in the second? ( M = 1000000007)

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

            you have to print ans modulo 1000000007. so you can't simply divide by 2. read this Link

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

              But my numerator is already % M and dividing by 2 would further reduce it then why do i again need to do %M?Please tell....

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

                you have to print (a/b) % m, what you are printing is (a % m) / b

  • »
    »
    4 weeks ago, # ^ |
      Vote: I like it -11 Vote: I do not like it

    if(b == 0) return 1;

    if(b == 1) return a%mod; // ( not a )

»
4 weeks ago, # |
  Vote: I like it +28 Vote: I do not like it

Yeah, now that I'm yellow I want to say that my D is wrong ):

It fails for this testcase:

10 2 
1 1 1 1 10 3 1 1 1 1

I think the answer is 3, but my code prints 2... I don't know how did it pass system test while failing on that simple case.

I don't deserve this :'(

Anyways, it gave AC 20 seconds before the end of the competition, so that was pretty cool (?

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

How calculate lcm in Div2 B?

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

    lcm(a, b) = a * b / gcd(a, b)

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

      Yes it is, but it overflow in test (10^18 * 10^18 / (gcd(10^18 * 10^18)), may be another way?

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

        Yes :)

        lcm(a, b) = a / gcd(a, b) * b

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

          OH, my math is very baad, thanks!

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

          For the input 1 12 1 12

          Why (2,6) isn't a good solution ?

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

        The limit is 10^9. 10^9*10^9=10^18. Overflow is not a problem

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

          Oh, you are right, mistake in another.

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

        or you can do this (a/gcd(a,b))*b

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

can anyone explain D ??

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

    p/s=k; p/s<=k; p<=s*k<=2e18, so there will be at most log_2(2e18) elements in subsegments not equal to 1.

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

I fst in D in the 132nd test. However,I run this test on my own computer,it gives the right answer immediately. It makes me fuzzy. Here is my code:code link Can anyone give me a explanation?

UPD: I resubmitted the same code in C++17 and C++11, both get AC. Only in C++14, I got TLE again.:(

UPD2: It is due to compiler's(C++14) optimization(level 2 and above). (My undefined behaviour first, it's my fault.)

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

    First of all, how can you run the test if the test is not fully available? :D

    More to the point,

    LL PP = tempPro*a[j];
    if(PP<0||PP%a[j]!=0||PP/a[j]!=tempPro)break;
    

    This is NOT the right way of testing for overflow. In the C++ standard, you can read that signed integer multiplication overflow causes undefined behavior, which means that you have no guarantee of what happens. It also means it might run well on your machine, but not run the same way on the judge.

    The proper way to test for overflow is something like this:

    //checks if a * b overflows long long
    inline bool overflows(LL a, LL b) {
      return a > (LLONG_MAX / b);
    }
    

    This avoids undefined behavior. Have a look at this submission 39391459. It's your code, but with proper overflow checking. It gets AC.

    P.S. I learned this the hard way. To understand how wild undefined behavior can be, I've had this assert (multiply two non-zero numbers and get a zero result) pass on some online judge:

    void f(long long b, long long c) {
        long long a = b * c;
        if(b && a / b != c) return;
        assert(b != 0 && c != 0 && a == 0);
    }
    
    • »
      »
      »
      4 weeks ago, # ^ |
        Vote: I like it +17 Vote: I do not like it

      Thanks a lot.

      Though my rating is declined, I'm pretty happy to learn something new.

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

Suppose mod is prime.

We know that (1/a) % mod is equivalent to (1 * a ^ (mod — 2)).

So what is (1 / (a ^ m)) % mod ?

  1. 1 * (((a ^ (mod — 2)) ^ m)
  2. find z = (a ^ m) % mod. then answer is = 1 * (z ^ (mod — 2)).

Both approaches in Problem C resulted in AC. I just want to make sure if those are actually correct and if you want, you can also include the proofs.

Not good at math. Only surviving by using theories and luck at appropriate places. :|

  • »
    »
    4 weeks ago, # ^ |
    Rev. 2   Vote: I like it +3 Vote: I do not like it

    From the exponentialtion laws we know: (ab)c = ab·c = ac·b = (ac)b Therefore:

    So both approaches are fine.

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

Got an idea for E 1:58 into the competition... Damn :D I understand the normal solution, but can someone who solved this with the sqrt decomposition elaborate? I didn't understand the comment that was posted here about it :)

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

    Most sqrt-decomposition solutions gets tle :D Idea is to make sqrt(n) blocks of size sqrt(n). If you store b[i] = prefix[i-1]-a[i] then you update, you need to decrease b[pos] and increase b[pos+1, n]. So for every block store this: all possible values of b, lazy value what is needed to be added, and some king shaman. So you need to fix the block with index i/block_size. And then for every following blocks add value to lazy, and find some shaman using lazy value and some map for all values of b.

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

      Thought about the prefix minus value and look for zero, but got stuck on n*n solutions. Really cool! Thanks :D

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

    other sqrt decomp solution: http://codeforces.com/contest/992/submission/39380451

    Main idea:

    in some block , we will keep values of form val[pos] — block_sum[pos — 1] and we sort them

    1) to update val[pos] = x, we update block of x only (just recalc the values)

    2) for query, we go through all blocks b1, b2.... bk (which takes O(k = number of blocks))

    Say you have sum of first p blocks. Binary search for that sum in block bp+1. If it exists in block bp+1, we have a king shaman

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

      Wow man! This is quite amazing that this is working! Tried compiling it with std::map and got a tle. but using vector of sized 64 apparently is a gamechanger — worked with a time of 1300ms...! sorting once and doing a binary search using bit is a-bit wow haha but kudos it's amazing you got this to work.

      I got quite intriguied by the idea and played with it a lot ( you can see the last 50+- submissions of mine haha...), This is the best working version I got:

      64-decomposition + your efficient binary search + memory reuse + arrays instead of vectors. http://codeforces.com/contest/992/submission/39407122 1263 ms

      Does anyone have an idea why the 64 "magic" works? trying to use 256 or 512 which are closer to the sqrt(2e5) is way better complexity wise, but works like hell. Cache misses?

»
4 weeks ago, # |
Rev. 5   Vote: I like it -8 Vote: I do not like it

Thanks for the delightful problems.

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

Did anyone else here get tle on test 132 in problem D?
Here is what I did:
Since the product increases very fast, for every end index I found the starting index such that p > 2e18 in by iterating over every element. Meanwhile, I updated the count of required segments. It takes at most log(2e18) time. For cases when the elements are 1, I checked in O(1).
my code
What can be the possible mistake?

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

Your crafting.oj.uz ratings are updated!

»
4 weeks ago, # |
  Vote: I like it +3 Vote: I do not like it

It was one of the most interesting contests that I had participate before thanks for this great contest ^_^

»
4 weeks ago, # |
  Vote: I like it +3 Vote: I do not like it

39389999

i was iterating over accepted submissions on the problem E and I've seen that one that i can't understand why it's not getting tle... if we have an array of zeroes and in each query we change the last element to something ...

the segment tree is obviously okay but the "beriz" function seems not okay to me at least ...

because its iterating over all segments that they're min is not positive and go down until the length of the segment is 1 and in my array his function i think will iterate over all elements of the array so that the order seems to be o(n*n)

someone plz help me with my problem ...

these code got ac so it's correct but i don't know why ...

i know the solution of the problem since I've got ac !

  • »
    »
    4 weeks ago, # ^ |
    Rev. 7   Vote: I like it +16 Vote: I do not like it

    His solution is O(n^2) and TL (works more than 5 minutes) on test like this:
    n = 1e5, q = 1e5
    a_i = 0
    p_i = 1, x_i = 0.

    If I'm not wrong, I guess, authors tests aren't strong enough.

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

    Shot dead!

    123a6bcw nice catch (your test is now #95).

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

Can someone explain algo to use in div.2 D? Seems like editorial is taking time :).

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

    An easier version that helps inspire a solution for the original problem: What if the smallest number in a[] becomes 2? That brute force tag seems fishy.

»
4 weeks ago, # |
Rev. 2   Vote: I like it +11 Vote: I do not like it

E solution w/ parallel binary search + segment tree since only sqrt-decomp solution is revealed here:

First step: Reduce the constraint a little bit — Let's say the shamans are claimed as "god-kings" if they have powers at least as much as their predecessors (instead of being exact). Note that the god-king set is a superset of the original king set, so we can check all elements of god-kings to see whether they are exactly kings.

How large is the god-king set? O(lg 1e9). Why? Consider all god-kings (i) in the set, observe that power[i] > sum(power[0:i]), so the power of the next god-king must be at least sum(power[0:i]) + power[i] >= 2*power[i-1], i.e. roughly twice as powerful as the previous one (except in constant corner cases, eg: sample 2, power[0] = power[1] = 2 results in both shamans being god-kings but no.2 is not twice as powerful as the previous god-king), thus the log factor in the complexity.

Now you'd just apply segment tree / BIT to support sum(power[0:i]) queries, and find the first element which is larger than sum(power[0:i]) with parallel binary search.

39403776

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

    I think my solution is similar to yours . Why it gets TL at test 8 ? Thx.

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

      The segment tree query function for sum query is a bit off, it misses a line which returns the sum directly if the current segment completely lies within the current range.

      if(l <= Node[u].l && Node[u].r <= r) return Node[u].sum;

      39407362

      Something it's still wrong though.

      Edit -- And long long. 39407764

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

        Oh..Thanks.I typed the wrong segment tree and i haven't noticed that . I deleted some useless optimization and gets ac. Thanks again

»
4 weeks ago, # |
Rev. 2   Vote: I like it +5 Vote: I do not like it

i got A in 2 mins i got B in 99 mins i got C in 93 mins but wrong (sad face) i am in 6th grade

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

can anyone debug why I am getting wa in test case 133 problem D

I assumed all numbers to be 1 of the array and tested in my local machine it gave me 0 only which is same as jury s answer.

pls help

my solution

http://codeforces.com/contest/992/submission/39416834