Will provide a nice breathing space after the AtCoder Grand Contest that ends 5 minutes before this contest too

Ya Plz

We got a guy from future here, peeps.

It is not so easy, that we can solve it without a statement

just do whatever you want. you can use some convex hull tricks, or persistent data structures, just do it :)

Should be 20. I believe, this change will only affect Div.3 rounds.

UPD: I'm wrong, check later comments.

My hero academia too

Now I can enjoy it.

It is 10,read this comments.

Not sure if this comment meant to gain upvote like before or to gain more downvote so he could be on the last page of contribution rank.

Edit : he's already on the last page !

¯\_(ツ)_/¯

div3 is a subset of div2 maybe that's why who knows

Using the same logic, Why he didn't mention that it is unrated for Div. 1 participants also? Maybe because they are smart enough to know the contest is unrated for them.

10

Well, it's even somewhat bold in the statement. And also repeated a couple of times. Should be noticeable.

aah shit

But 40343744 ??? I think that problem E require another sequence 40349064

UPD: sorry, my wrong, I just forgot about modulo

Not sure why this is being downvoted, I found the exact same sequence online during the contest.

A fairly common problem solving technique: 1) write naive solution 2) find pattern (possibly look online) 3) hard code in formula

It's a greedy problem.

In your code, "sum" overflows for very large N.

Small datatypes may overflow, so long double should fix the problem.

n is an int up to 10^5 and you are doing n*(n+1) when you calculate beech

One obvious reason is overflow. You have beech = n*(n-1), but n is an int. See what happens when n = 100000 or n = 99999.

There are actually 130 tests in this problem.

It was originally used in Saratov SU trainings a few days ago, and there was a man who managed to receive RE 130.

Yeah, strong tests in tree problem without test "1-2-3-...-N". This is Educational round.

For C: check overflow. You're multiplying two ints and storing the result in a long long. Overflow happens before the storing does.

For E: You're reading 10^6 numbers using cin. Speed it up with ios::sync_with_stdio(0) and cin.tie(0) or use printf/scanf.

I tried 20 45 and the last edge you print is 4 10. GCD( 4 , 10 ) = 2. Hope this helps

Looks like you're just counting multiples of a number as non-coprime with it, which is only true for primes — not composite numbers. Try 6 11. You print 4 6.

For every x, sieve will only delete every multiple of x (not relatively prime of x). So your sieve will delete every multiple of x, add every y where y is not multiple of x, and readd every multiple of x

Got it, thank you Diegogrc, IceKnight1093 and Firastic! I'll upsolve this now.

I'm not sure but i think your arrays are too small (10000 instead of 100000).

1011201120112 is 0111111120202

Put all '1' s just before first "2". 012012 becomes 011202 , whereas your code gives 012012

so, count '2' and '0' from first '2' and put them back of the string with same order. fill the rest of numbers 1

count 1 in string then count 0 before any 2 comes then print 0 as per count then print all 1, then just print 0/2 as they come in string. for eg. 101201120 becomes 011112020

Maintain the order of 0's ans 2's. Take all 1's and put them just before 1st occurence of 2.

Amazing

But what's more Amazing is that you just submit the first 3 problems in 3 minutes

This recurrence is wrong because it doesn't take probabilities into account.

For example, suppose you are analyzing 4-th kilometer and trying to find a closest rest stop before it. The probability that it will be on position 3 is 0.5, the probability that it is on coordinate 2 is 0.25, and so on. So we can't just sum all these dp values up, we need some coefficients.

Note: I didn't actually solve E but I got the problem right after contest ended...

The answer is:

where

P[i] = 2^{N - i - 1}·(N - i + 2) for i = 1...N-1

P[N] = 1 (technically same as above but 2^- 1 is fractional)

mod MOD at each step of course

I used brute force to find array for first 10 numbers and entered the list into OEIS

edit: off by 1

stl deque many times proves inefficient for many problems in time n memory usage

I think .clear() doesn't free memory. Could you try delete operation?

SAAAME

With a greedy taste.

try using ios::sync_with_stdio(false);cin.tie(NULL);. It can boost up speed of cin/cout to that of scanf/printf. See 40351502

Looks like your solutions just overflows in m>(n*(n-1)/2).

The problem with the first one was overflow: you were comparing m with (n*(n-1))/2 where n was an integer. If n is large enough the product will overflow and become negative. Second submission doesn't have that comparison so it passed.

double ans = (double)sum/n

ans might overflow, you should've typecasted sum to long double!

No, it should be okay.

We can always bring any 1 to the beginning of the string, since we can swap 1 with any other digit.

because there are sufficiently many 1s in the string, the 0 and 2s have become invisible after the moves.

Its relative error is smaller than 10^- 6

In terms of relative error, it's correct.

If it is stated that "Your answer is considered correct if its absolute or relative error doesn't exceed 10^- x", then checker considers the minimum of absolute and relative errors.

Run two loops(1 to n and from i+1 to n)and calculate gcd (i,j)if it is 1 then print as m can be atmost 100000 so the both loop terminates after m iteration. And if n>m-1 you have to print impossible as the graph then can't remain connected

Given n, the number of possible edges is basically all those (unordered) pairs (x, y) such that x, y ≤ n and gcd(x, y) = 1 and x ≠ y. This number is simply φ(1) + φ(2) + ... + φ(n) - 1, where φ is the totient function. (subtracting 1 since we can't have the pair (1, 1).

This gives us 2 edge cases: if m is greater than this number or m < n-1 it's not possible to create such a graph — either it won't be connected or there won't be enough edges.

In every other case, it's possible. Connect 1 to every other node first to connect the graph. Then, for each pair (i, j) such that gcd(i, j) = 1, i ≤ j, 1 < i, j ≤ min(n, 600) you have one edge. 600 because φ(1) + ... + φ(600) > 100000 so you're guaranteed to have enough edges with just that.

In D, the most important task was to check possible or not because other than that, we just need to output co-primes together.

In order to check co-primes of available, you just need to implement Euler's totient function. Thus in O(n), we can check possibility or not.

We could have stored this value in a vector to check is total count is greater than required and n-1 as well. But that can bring TLE for large cases.

Submission

https://codeforces.net/blog/entry/44351

Do dfs on a tree, and for every node x, you can find the array d(x). You can make it in O(nlogn) if you merge there arrays carefully. MLE solution: 40349306 Correct: 40349677

Turns out my solution was wrong. Sorry.

Maybe using long double instead double will help?

The graph should be connected.So your solution got wrong when m<n-1