rek's blog

Codeforces Round #456 (Div. 2) Editorial
By rek, history, 3 years ago, In English

We, the round authors, are eternally grateful to all the brave who took part in this round. Sadly there were some issues to encounter, but we hope it only made the contest more interesting :)

Tutorial is loading...

Author — GreenGrape
Code: 33946912

Tutorial is loading...

Author — GreenGrape
Code: 33946939

Tutorial is loading...

Author — rek
Code (rek): 33953146
Code (x3n): 33946949
Code (GreenGrape): 33947166

Tutorial is loading...

Author — GreenGrape
Code (x3n): 33946962
Code (GreenGrape, solution 1): 33946974
Code (GreenGrape, solution 2): 33946993

Tutorial is loading...

Author — GreenGrape
Code (x3n): 33947002
Code (GreenGrape): 33946911

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

Comments Comments (132)
»
3 years ago, # |
  Vote: I like it +21 Vote: I do not like it

The editorials had been very fast lately

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

Great editorial! :)

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

Is there a term for binary numbers that fill in all 1's when xor'd? For example 11000 xor 00111 is 11111 so they fulfill this property.

I think if such numbers have a name problem B relies on this idea.

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

I can't believe B turned out to be so simple, I didn't realise it said "at most k"

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

    same here but i still cant get solution can u give me its possible examples satisfying the mentioned statement means VALID PROOFING

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

      Checkout my comment bellow

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

        can u tell me why the log2(n) is not working here for the calculation of no of bits in the binary rep of n

        http://codeforces.com/contest/912/submission/34650649

        but when i calculated it recursively through loop and then applying pow(2,no of bits ) It gets accepted

        I also use fast mod exponentiation in the case when no of bits gets very large but it doesn't matter i know because for this i set my mod to be very large far beyond then 10^18 so that no overflow occurs

        http://codeforces.com/contest/912/submission/34650763 but in the ques pow is still getting accepted due to the less width of the no of bits in the bin rep of n.. Can u plzz tell me why this strange behaviour happening

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

B was simple, now i realize, started this round so late , damn !

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

I think you made a small mistake — the complexity in E is O((D(A) + D(B)) * log(D(A) + D(B)) * log1018)

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

    I use two pointers so the complexity is true :) We are uploading the sample solutions now.

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

Can someone explain the calculation of f(x, y) in problem D?

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

    Just apply all restrictions on both coordinates.

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

      Can you explain it little more.

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

        Let's solve it for a single x0. Imagine we're covered by a scoop located at x. What should be applied?

        • x ≥ 1
        • x ≤ x0
        • x + r - 1 ≤ n
        • x + r - 1 ≥ x0

        Combine them and solve the same problem for y. This will give you a rectangle where each point is valid.

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

          double fun(int x,int y)

          {

          double ro,co;

   if(1<= x <= r || n-r+1<=x<= n)ro=min(x,n-x+1);
   else ro= r;

   if(1<= y <= r || m-r+1<=y<= m)co=min( m-y+1 ,y);
   else co= r;

   return ro*co;

          }

          I came up with this function during the contest which returns the count of scoops in which (x,y) is included. I thought the get(x,y) in editorial gave the same result. But it differs in some cases. Whats wrong with the logic behind my function?

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

            lol! never mind. I dont know what I have been looking at for the past 6 hours. That isnt even a correct implementation. So shameful that i am realizing this after posting it here.

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

          Shouldn't x0 >= x ?

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

          I know that I am asking a silly question but please help me with this. How the given 4 inequality can be combined to get 1. min(n+1,x+r)-max(x,r)

          EDIT: I get it now the logic behind this.

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

          Can you elaborate on the next steps, i.e. how you solve these inequalities for x0 ?

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

Very nice problem set! I hope to see more contests from you in future.

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

For problem D, how do you check if a cell (x,y) has already been visited in O(1) ?

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

    Make a set of pairs.

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

      Oh okay I'm not really used to use sets that's why ^^ thanks

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

        actually if you go by the solution , it's impossible to get a cell (x , y) two times,.. , but we still need to get the maximum cell at top so that's why we have to use heap or set , whatever you prefer , no worry about them getting repeated

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

can somebody explain problem (b) elaborately ?? need help !

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

    Assume that you have number 11 binary representation (1011) , now the maximum xor sum can be 1111 , if you observe more carefully than if you take 1 complement of 11 i.e 0100 and xor it u get 1111 i.e maximum .

    So if k==1 you will print n because it is the maximum

    else print the maximum 2^p-1 where p are the bits in binary representation of n because 1's complement of n is always less than n

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

    For k=1 the problem is quite simple. You just print the greatest number which is indeed n. For k>1: [Note that the problem asked us to Select AT MOST k numbes in range n] So we can always select two numbers which will maximize the result. Take the case of n = 14, in binary n = 1110 This contains one zero which can be made 1. How? Take the xor of 1000(in decimal 8) and 0111(in decimal 7) = 1111(in decimal 15) Now 8 is in form = 2^p and 7 is in form = 2^p-1 I hope this helps.

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

    Consider the case for n = 4 , k=3, let's write the numbers from 1 to n in binary:

    1 => 001
2 => 010
3 => 011
4 => 100

    Furthermore, we know that xor of 2 binary digits is is 1 only when both differ ( 1 XOR 0 .. or 0 XOR 1).

    After observing the sequence above you realise that 3 XOR 4 is maximum, because all of the digits in both numbers differ

        011
XOR 100
  = 111 (7)

    To generalize this we observe that for any n, if k>=2 we can compute the max value by setting all the bits to 1's, since we can guarantee to find 2 numbers whose digits all differ, some examples:

    n=11, which is 1011, so answer is 1111, or 15 
n= 33, which is 100001 so the answer is 111111, or 63

    to generalise this we can use this formula: 

    if k ==1:
  answer is n
else:
  answer is 2^(floor(lg(n))+1) - 1
    → Reply
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

the contest was very good for me, but i don't think that was a standard contest.

because normal Div.2 participants mostly solved problems A and B but in a standard contest, a normal participant usually solve 3 problems.

nevertheless thank you for the contest:)

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

Auto comment: topic has been updated by rek (previous revision, new revision, compare).

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

is this contest rated?

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

In problem E, how could I estimate |D(A)|? Should I just do what I guest and check it?

( In the contest, I think the size might went to 10^9 or larger, so I didn't try to implement and check it. TAT

BTW, I think it's a good contest, thank you!

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

    Yep. It's a coding competition after all xD

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

      Can you explain how did you come up with "sizes of both D(A) and D(B) do not exceed 106"?

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

        I think we could just try to implement it and find it out

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

Was just curious how long will it take for the ratings to be updated?

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

In problem D, how f(x, y) is formulated ?

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

    That is "how many scoops cover this point".

    For example, (2, 2) from sample case 1 (reference to the pic) has f(2, 2) = 4.

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

      I mean, how it is generated?

      f(x, y)= (max... — min...)*()

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

        Take a look at this!

        Do such thing with x0 and y0 separately and take their cartesian product.

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

great editorial !!

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

Why isn't time limit for java 2x of C++ in codeforces, it is very painful to see same solutions running in C++ rather than in java, and this makes extremely difficult to pass solutions in java.

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

    It's your choice if every contestant, what language to use. If you choose C++, you get good performance, but loose, for instance, BigInteger. If you want write all problems using same language, it's definitely your problems.

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

"Let N be our initial set. Sadly we cannot just generate D(N) since its size might be of the order of 8·10^^8". How did the you compute the number 8.10^^8 ?

Also, similarly, how did you come with the number O(log 10^^18 .(|Da| + |Db|)) ?

Thanks.

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

    We cannot generate such a big set of numbers, so we are looking for a better way of computing the answer, and this way is described in the editorials.

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

      But how did we approximate the size of this big set of numbers?

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

        Use bruteforce to obtain those sets :)

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

          Complexity to generate those sets using bruteforce ?

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

            O(k) where k is the number of integers  ≤ 1e18 whose prime divisors are entirely contained in the set that you are generating.

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

          Can you tell me how to use bruteforce to calculate "D(N) which size might be of the order of 8 * 10^8 " please? Thanks.

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

Can someone elaborate on the implementation details of the problem E?

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

    Nevermind. I understood the implementation.

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

The first thought is to send the first elements to A and the rest to B. However, this is not enough; in this case the approximate size of D(A) might reach 7·106 which is way too much to pass.

How do we know this?

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

    If you write a code to generate D(A) where A contains the first 8 prime numbers. You will see that its size will indeed be approximately 7e6. I have verified this on my computer.

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

What is the time complexity of the "count_le" function in x3n's code?

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

"The first thought is to send the first n / 2 elements to A and the rest to B. However, this is not enough".

I did exactly that and it passed in around 1100MS: http://codeforces.com/contest/912/submission/33953122

GreenGrape is that a typo, or did I get lucky?

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

    That’s not a typo :)
    My solution uses two pointers approach and hence works in

    Yours iterates through the smaller set and binary searches the greater, and hence works in

    That means that a skew partition works fine in your case and fails in mine. As an opposite, the equallized partition slows down your solution and speeds up mine.

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

In problem C, isn't it easier just to add f(t) changes in map and then count ans after any change (choose max of them). And then output ans if f(t) == 0 after all changes or "-1" in another case. like this

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

For problem E: Can someone explain what's happening in the function "go" of the editorial solution? I understand that the primes are split between lp and rp, but I didn't get what the recursive function calls will do:

go(1, 0, lp, A);
go(1, 0, rp, B);
→ Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    It generates all numbers less than 10^18 which can be written as product of primes in the desired set.

    For example primes = {2,3}, you generate all numbers less than 10^18 which can be written in the form 2^k1 * 3^k2

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

      What is the complexity to generate all such numbers in the "go" function ?

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

        complexity per prime = log(1e18)/log(2) * log(1e18)/log(3) * log(1e18)/log(next prime in the sequence) *.... * log(1e18)/log(current prime)

        here log has base 10.

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

        But the interesting thing is, this is a very loose upper bound. So in practice it's not as bad as it looks.

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

thanks for a nice editorial :) specially D and E !

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

Can't E be solved using bitmask?

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

    I thought of it too, but since the occurrence of each prime can be more than once, I decided against it..

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

I liked the thought behind E. It's all about optimizations!

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

some one interesting to problem B if you can choose "exactly" K numbers? obviously K=1 or 2 is like the ordinary problem

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

    I had the same thoughts — how would we solve problem B if the question was finding max XOR given we can pick "exactly k numbers"

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

In problem " B " , in testcase #48 , n was 2^58,so answer should be 2^59-1(xorring 2^58 and 2^58 -1) but answer was 2^58-1 (when k=2)!! how!! also why different answers with log2() and log2l()... is it about (rounding off) of double value

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

    2^58=1<<58=288230376151711744 testcase #48 is 288230376151711743 which is (2^58)-1 so...

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

      oops!!xD

      thanks....

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

        but when i just used log2() instead of log2l() ,(int)(log2(n)+1) gave (59) and (int)(log2l(n)+1) gave 58!!why

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

          both to me i have 59.. i dont know why you have 58 for (int)(log2l(288230376151711744)+1) UPD you can submit this to any problem

          #include <bits/stdc++.h>
using namespace std;
int main(){
	cout<<(int)(log2l(288230376151711744)+1)<<endl;
	cout<<(int)(log2(288230376151711744)+1)<<endl;
}
          → Reply
          • »
            »
            »
            »
            »
            »
            3 years ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            pls check your code for 288230376151711743 = (2^58-1) giving 58 ,59!!!!!

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

              Really! its seem log2l work specially ,sor i dont kwow what log2l going on ,i usually use log2 instead maybe some "double" type problem ?

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

For problem D, May I ask why this part || (f_a == f_b && a > b); is added in the compare function of solution 2? (f_a == f_b && a > b) and (f_a == f_b && a < b) both give AC and without these output do not match.I wonder why?

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

    A set cannot contain equal elements by its definition. Hence if fa = fb, the second point will not be added.

    In order to fix it we should force our set to treat them as distinct ones. Since all points are distinct, this comparison works fine.

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

      I still do not understand.

      Since all points are distinct, then why do we need to force the set to treat them as distinct? Am I missing something?

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

In D we can use another method. Let see that optimal area is convex (or approach to convex). For this reason we should find rectangle area with square >=2*k. For find it let move vertical or gorizontal bounders (what's is better).

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

    Yeah, but most such solutions fail somewhere between test cases 81 and 95.

    It’s cool that yours passed.

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

in Tricky Alchemy problem,my algorithm was correct but in third test case, the output was correct but negative (-2147483648),i tried using long long,long double,int and it didn't work,any help?

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

    Please add a link to your solution below.

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

      Here,http://codeforces.com/contest/912/submission/33944085

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

        You should be using long long since 2147483648 is not a valid value for an int, it overflows resulting in the answer you are getting.

        If you change the inputs to be long long and change the printf flag to %lld then it should pass.

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

          Thank you so much you're right,i used long long but in scanf typed %ld,thanks a lot

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

"The first thought is to send the first elements to A and the rest to B. However, this is not enough; in this case the approximate size of D(A) might reach 7·106 which is way too much to pass. To speed it up we can, for example, comprise A of elements with even indexes (i.e p0, p2, ...) so that sizes of both A and B do not exceed 106 and the solution runs swiftly."

What's the difference? In both the case, one set will be of size floor(n/2), and the other will be of size n — floor(n/2). What am I missing?

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

    Applied a minor correction, thank you. Should be up soon :)

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

      done?

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

      pls help me out of weirdity of log2() and log2l() behaviour towards (2^58-1) in problem b:(

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

How do you get better? I'm always able to solve only one or two questions in div 2?

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

Please help me out with Problem B \n Link to code- http://codeforces.com/contest/912/submission/33950052 \n I first convert number n to binary, then traverse the binary string checking if '0' is there -> convert it to '1' and decrement k. Getting WA from test case 9.

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

Wonderful job with the editorial!!

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

In D, is it necessary that all fishes are placed horizontally only or verticaly only? The sample case doesn't cover the case of all 3 fishes under the square.

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

    The problem statement says you are not allowed to put more than one fish per cell.

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

      I know that, I'm saying that the 3 fishes can be placed in the shape of L in three different cells so that all 3 can be covered under the square

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

      "In the first example you can put the fishes in cells (2, 1), (2, 2), (2, 3)." Why so? why not (1,1), (2,1) , (2,2), so that output is 3?

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

        I believe it is because they are asking you to place fishes such that a random net has the highest expected value. In the given example, the expected value is 2 because there are 4 possible net positions and those net positions capture 8 fish --> Expected value = (total fish) / (net positions) = 8/4 = 2.

        If you place the fish like you said at (1,1) (2,1) (2,2) it is true that the first net position (top left) will contain three fish. However, you will see that because of this the other net positions will contain 1, 2, and 1 fish. Then total fish = 3 + 1 + 2 + 1 = 7. Expected value = 7/4 which is less than 2 so this placement is not maximizing the expected value.

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

So I've been stuck on E for a bit now (did this as a virtual contest and spent most of my time on it). I had a (I think) similar-ish idea. Instead of splitting the set in two I added one prime at a time, keeping track of the smallest k numbers one can make with the first m of the n primes. This (or at least my implementation of it) ended up being too slow. Is there a reason the DP approach is doomed to be too slow that I'm not seeing? Or is it likely just that my implementation sucks? Also (relatedly) I'm not seeing how to prove the O(|D(A)|+|D(B)|) part of the complexity? I suspect if someone would be nice enough to fill in this bit I'll see what I'm doing wrong on this problem.

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

    k might be as large as 8·106.

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

      Hello GreenGrape, can you please explain how to estimate number of recursive calls that it takes to build sets D(A) and D(B)? And how do you come up with 10^6 limit? The way I estimate it is this: For the worst case we pick for A primes 2,5,11,17,23,31,41,47. Therefore total time is 18/log(2) * 18/log(5) ... 18/log(47)~10^9... Which will exceed time limit...

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

Direction array:

int dx[4] = {-1 ,1 ,0 , 0} ;

int dy[4] = {0 ,0 -1 , 1} ; ==> gave wrong answer. but then

changing it to ,

int dx[4] = {-1 ,0 ,0 , 1} ;

int dy[4] = {0 ,-1 , 1 , 0} ; ==> the solution got accepted!

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

In the problem, E.I'm stuck in bs implementation of @GreenGrape.

my question is,for smallest t we got count_le(t) == k.how can I prove that t is in the set of some combination of(D(A)*D(B))?

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

GreenGrape , can you explain how do we get the numbers 8*10^8 (size of D(N) ) ... and also how do we get numbers 10^6 if we split N into A and B...

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

    I think he found it out empirically . You can recursively compute the set A and B . It would be helpful if you try to think of it as a tree . At each height you can branch off into some power of the corresponding prime.

    static void brute(int idx ,int len,  long curr, long collect[]) {
        if(idx == len) { 
            collect[ptr++] = curr;
            return;
        }
        brute(idx + 1, len , curr , collect);
        while(curr <= MAX / primes[idx]) {
            curr *= primes[idx];
            brute(idx + 1, len, curr, collect);
        }
    }

    I'm currently stuck in a TLE while computing the the number of numbers less than a given number part . I tried Med0b1011's idea. If someone has solved E in java and faced the same issue please help me out . CODE

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

      I don't think it's possible to pass (logn)^2 in Java, at least without doing major changes to the generate function.

      • The solution in mashup takes 8190 seconds to run. The time limit is around 3.5 seconds, this looks like too much to optimize.

      • All Java solutions that passed run from 1.5 to 3.5 seconds, and they do it in logN. I don't think it would be possible to squeeze an extra log factor in.

      The fastest solution in Java here runs in 1200MS : http://codeforces.com/contest/912/submission/33951400

      Maybe you can use his generate function, and combine it with double binary search.

      Note : I still find it surprisingly weird how can my CPP solution run in 1000MS without even attempting to optimize it while Java takes 8. I expected it to run in say 4-5 seconds at most.

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

        I think that's due to using ArrayList , I wrote another solution using arrays but even that gave a TLE though it ran ~3.3s on my PC . Actually generate and sort took ~0.8s only. Can you try running this

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

          Takes 3.7 seconds, you are almost there. I think Java uses quick sort so that may slow it down (Changing long to Long to force merge sort takes 8) so try using your own sort function.

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

            Thanks a lot , Finally AC

            • Used UWI's radix sort
            • Removed Java's binarySearch and implemented my own
            → Reply
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Can someone please share a problem which is similar to problem D,where we need to find the first K values which maximizes or minimizes a given function. Thanks.. :)

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

In this Code (rek): 33953146 what does cnt[at-1]+=0 and cnt[time-1]+=0 do? why to do += by zero

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

    That's a tricky (but not really beautiful in terms of code style) thing that lets us add a key (at-1 and time-1 respectively) to an STL C++ map. The "square brackets" operator of the map will create a key if it doesn't exist yet, so:

    • if we have no such key, it will simply add it and set its value to 0 so it won't affect answer
    • if we do have, the value won't get changed, so it won't affect the answer as well

    Why do we need to add this key at all? It's because both at-1 and time-1 are the last points of times when we can kill a certain enemy before its health gets changed to be too high to let us kill it.

    Though I personally think that it's ugly as I mentioned before, it's short and efficient :)

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

Can someone explain C problem ? I couldn't understand the tutorial and why cnt[at]--?

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

    at is the point where enemy's health becomes too high to kill it, so we have to decrease count of the people we can kill there by 1.

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

      but intitially cnt[at]==0 ,right??

      so it will get -1

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

        cnt holds the difference between the previous and the current moments of time, so -1 would be ok, and mean that "the number of enemies we can kill now is less by 1".

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

Can someone plz explain me the first solution approach in D ??

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

Just by practicing E, I managed to understand how two pointers are more efficient than STL upper_bound/lower_bound in merging results in sub-problems in a meet-in-the-middle problem. Never thinking that way before ;)

Many thanks for enlightening me ;)

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

For Problem E, I used a Accepted code run the second sample. But I found a problem ==> I print the rank of 98 and rank of 93, both of them are 17, In other word both of them satisfy the Problem E, But the right answer is 93, so I want to know why it is right that if both of number have same rank, Always choose the smaller one. ( It can control by changeing the detail in the binary_search )

Hope someone can understand what I say and help me solve this problem, thanks!!!

→ Reply
»
8 months ago, # |
  Vote: I like it 0 Vote: I do not like it

I have a shorter(/est) solution for Problem B

n,k=map(int,input().split())
if(k==1):
    print(n)
else:
    print(2**(len(bin(n))-2)-1)
→ Reply
»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

For the second problem if we consider K=4 then we have chosen 2^p and 2^p - 1 that's all right but what about the other two numbers? How can you say that even including the other two numbers won't change the result?

→ Reply