Разбор Codeforces Round #456 (Div. 2)

6 лет назад, # ^ |

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

→ Ответить

Yusif

6 лет назад, # |

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

→ Ответить

6 лет назад, # ^ |

Just apply all restrictions on both coordinates.

→ Ответить

aadish

6 лет назад, # ^ |

Can you explain it little more.

→ Ответить

6 лет назад, # ^ |

← Rev. 2 →

Let's solve it for a single x₀. 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 ≥ x₀

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

→ Ответить

6 лет назад, # ^ |

Shouldn't x0 >= x ?

→ Ответить

6 лет назад, # ^ |

Oh, thanks for pointing out.

→ Ответить

6 лет назад, # ^ |

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

→ Ответить

6 лет назад, # |

+12

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

→ Ответить

brurrito

6 лет назад, # |

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

→ Ответить

6 лет назад, # ^ |

Make a set of pairs.

→ Ответить

brurrito

6 лет назад, # ^ |

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

→ Ответить

yaksha

6 лет назад, # ^ |

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

→ Ответить

6 лет назад, # |

Автокомментарий: текст был обновлен пользователем rek (предыдущая версия, новая версия, сравнить).

→ Ответить

M_H_H_7

6 лет назад, # |

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

→ Ответить

6 лет назад, # |

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

→ Ответить

oToToT

6 лет назад, # |

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!

→ Ответить

6 лет назад, # ^ |

Yep. It's a coding competition after all xD

→ Ответить

aj1

6 лет назад, # ^ |

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

→ Ответить

oToToT

6 лет назад, # ^ |

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

→ Ответить

all_out

6 лет назад, # |

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

→ Ответить

6 лет назад, # ^ |

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.

→ Ответить

all_out

6 лет назад, # ^ |

I mean, how it is generated?

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

→ Ответить

6 лет назад, # ^ |

Take a look at this!

Do such thing with x₀ and y₀ separately and take their cartesian product.

→ Ответить

mathmaniac

6 лет назад, # |

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.

→ Ответить

BagishovMikail

6 лет назад, # ^ |

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.

→ Ответить

6 лет назад, # |

← Rev. 2 →

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

→ Ответить

6 лет назад, # ^ |

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.

→ Ответить

6 лет назад, # ^ |

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

→ Ответить

6 лет назад, # ^ |

Use bruteforce to obtain those sets :)

→ Ответить

Single_Ready_To_Mingle

6 лет назад, # ^ |

Complexity to generate those sets using bruteforce ?

→ Ответить

6 лет назад, # |

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

→ Ответить

6 лет назад, # ^ |

Nevermind. I understood the implementation.

→ Ответить

6 лет назад, # |

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?

→ Ответить

Lance_HAOH

6 лет назад, # ^ |

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.

→ Ответить

6 лет назад, # |

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

→ Ответить

JustLive

6 лет назад, # ^ |

← Rev. 3 →

It's $\text{[math]}$ (or $\text{[math]}$ )

→ Ответить

6 лет назад, # |

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

→ Ответить

6 лет назад, # ^ |

That’s not a typo :)
My solution uses two pointers approach and hence works in $\text{[math]}$

Yours iterates through the smaller set and binary searches the greater, and hence works in $\text{[math]}$

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.

→ Ответить

6 лет назад, # ^ |

Got it..thanks :)

→ Ответить

nikich340

6 лет назад, # |

← Rev. 2 →

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

→ Ответить

motatoes

6 лет назад, # |

← Rev. 2 →

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

→ Ответить

6 лет назад, # ^ |

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

→ Ответить

Single_Ready_To_Mingle

6 лет назад, # ^ |

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

→ Ответить

I_love_Captain_America

6 лет назад, # ^ |

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.

→ Ответить

I_love_Captain_America

6 лет назад, # ^ |

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

→ Ответить

pk842

6 лет назад, # |

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

→ Ответить

nimom

6 лет назад, # |

← Rev. 2 →

Can't E be solved using bitmask?

→ Ответить

HumbleDoor

6 лет назад, # ^ |

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

→ Ответить

I_love_Captain_America

6 лет назад, # |

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

→ Ответить

6 лет назад, # |

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

→ Ответить

6 лет назад, # |

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

→ Ответить

6 лет назад, # ^ |

← Rev. 3 →

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

→ Ответить

6 лет назад, # ^ |

oops!!xD

thanks....

→ Ответить

6 лет назад, # ^ |

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

→ Ответить

6 лет назад, # ^ |

← Rev. 2 →

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;
}

→ Ответить

6 лет назад, # ^ |

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

→ Ответить

6 лет назад, # ^ |

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

→ Ответить

mahim007

6 лет назад, # |

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?

→ Ответить

6 лет назад, # ^ |

A set cannot contain equal elements by its definition. Hence if f_a = f_b, 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.

→ Ответить

ruban

6 лет назад, # |

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

→ Ответить

6 лет назад, # ^ |

← Rev. 2 →

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

It’s cool that yours passed.

→ Ответить

AlwaysHustle

6 лет назад, # |

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?

→ Ответить

6 лет назад, # ^ |

Please add a link to your solution below.

→ Ответить

6 лет назад, # |

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

→ Ответить

6 лет назад, # ^ |

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

→ Ответить

6 лет назад, # ^ |

done?

→ Ответить

6 лет назад, # ^ |

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

→ Ответить

_Mr_Fab

6 лет назад, # |

Wonderful job with the editorial!!

→ Ответить

JVirak

6 лет назад, # |

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.

→ Ответить

6 лет назад, # ^ |

k might be as large as 8·10⁶.

→ Ответить

yaksha

6 лет назад, # |

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

→ Ответить

bhishma

6 лет назад, # ^ |

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 Medo.'s idea. If someone has solved E in java and faced the same issue please help me out . CODE

→ Ответить

6 лет назад, # ^ |

← Rev. 3 →

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.

→ Ответить

bhishma

6 лет назад, # ^ |

← Rev. 2 →

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

→ Ответить

6 лет назад, # ^ |

← Rev. 2 →

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.

→ Ответить

bhishma

6 лет назад, # ^ |

← Rev. 2 →

Thanks a lot , Finally AC

Used UWI's radix sort
Removed Java's binarySearch and implemented my own

→ Ответить

arsrivish2

6 лет назад, # |

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

→ Ответить

6 лет назад, # ^ |

← Rev. 2 →

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

→ Ответить

agamanan96

6 лет назад, # |

← Rev. 2 →

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

→ Ответить

6 лет назад, # ^ |

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.

→ Ответить

agamanan96

6 лет назад, # ^ |

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

so it will get -1

→ Ответить