Codeforces Global Round 19

2 года назад, # |

Are AI accounts participating? Bet these AI bots did not recover well from the last round

Spoiler

→ Ответить

2 года назад, # |

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

→ Ответить

2 года назад, # |

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

→ Ответить

RisingWizard

2 года назад, # ^ |

← Rev. 2 →

DmitryGrigorev for the great coordinating and helping us with preparing probles.

typo in problems

Edit: fixed

→ Ответить

2 года назад, # ^ |

Thank you! Fixed.

→ Ответить

rohitsatpute480

2 года назад, # |

Will it contain any interactive problem?

→ Ответить

2 года назад, # ^ |

+16

No.

→ Ответить

shiro

2 года назад, # ^ |

nice

→ Ответить

pakhomovee

2 года назад, # |

← Rev. 2 →

+41

Good luck everyone!

Hope you enjoy the tasks ♡!!!

P.S. Actually, it takes a lot of hard work to prepare every task properly, so upvote the initial post as a sign of respect for the contest setters.

→ Ответить

sachin_raghuwanshi

2 года назад, # |

(づ｡◕‿‿◕｡)づ ❤

→ Ответить

rahul_rax

2 года назад, # |

+10

Waiting for AI to overpass my rating :-)

→ Ответить

threethreetwothree

2 года назад, # |

I add rating every time I join Global Round, hope you so. Really enjoy. :)

→ Ответить

Saaketh_9616

2 года назад, # |

-23

Will this round be rated?

→ Ответить

steadyLearner

2 года назад, # ^ |

Yes, it is rated for everyone.

→ Ответить

Saaketh_9616

2 года назад, # ^ |

-17

ok, thank you

→ Ответить

DitaMirika

2 года назад, # |

+27

Hoping for a nice round!

I will be not able to participate in contests for a long time after this round because of the new term. TAT

→ Ответить

Alex7

2 года назад, # |

NANOGrav

→ Ответить

tongwentao

2 года назад, # |

← Rev. 2 →

-43

I hope I will enjoy it！

→ Ответить

badluck_1441

2 года назад, # |

hoping to first time get rank under 1500 in div 2.

→ Ответить

Siam_CSE19_HSTU

2 года назад, # |

Best of luck, all

→ Ответить

stevie1024

2 года назад, # ^ |

Thanks, you too

→ Ответить

makrav

2 года назад, # |

Good luck

→ Ответить

boldcounselor

2 года назад, # |

-16

this one goes out to all my fellow noobs:

→ Ответить

bloistercvlt

2 года назад, # |

-97

"The final result for each participant is equal to the sum of points he gets in the four rounds he placed the highest."

so she doesn't get any result?

→ Ответить

ronith1

2 года назад, # |

Is registration during contest not allowed?

→ Ответить

krypton001

2 года назад, # |

I wasted too much time on B and C ... overthinking sucks man!

→ Ответить

What other rules are on Codeforces?

2 года назад, # ^ |

-8

I wasted on A. Took less time on B and C than A

→ Ответить

GOD_LYNX

2 года назад, # |

-52

Yeah, maybe this contest will make me a pupil

→ Ответить

memoryallocator

2 года назад, # ^ |

+22

Do not use anybody photo except yours. It is uncultured and could confuse Codeforces users.

→ Ответить

andreyDagger

2 года назад, # |

-65

Solved C in 30 minutes, solved D in 80 minutes, and then solved E in 20 minutes. What a disbalance!! Problem D isn't quite good, because you need just guess, that you have to minimize |sum(a)-sum(b)|. Rest was good, Liked problem E

→ Ответить

Len

2 года назад, # ^ |

← Rev. 2 →

You don't need to guess, dp[i][sum] = 1..i, sum = sum of a, it's easy to calculate the answer.

→ Ответить

Anjaneyrai

2 года назад, # ^ |

I figured that minimization actually but couldn't able to implement can anyone tell how to minimize |sum(a)-sum(b)|?

→ Ответить

riadwaw

2 года назад, # ^ |

Find all the possible sum(a) instead (using variation of knapsack algo)

→ Ответить

ExplodingFreeze

2 года назад, # ^ |

+72

"You need to guess".

I don't think there is any guesswork to this problem.

Expand $$$(a_i + a_j)^2$$$ as $$$a_i^2 + a_j^2 + 2 \cdot a_i \cdot a_j$$$. Clearly the two square terms will occur regardless of which array you are in.

Toying around with equations a bit, we can realize sum $$$2 \cdot a_i \cdot a_j$$$ over all $$$i \lt j$$$ is just $$$(\sum{a_i})^2 - \sum{(a_i^2)}$$$.

The second part is again constant regardless of which array we put it in. So now we clearly want to minimize $$$(\sum{a_i})^2 + (\sum{b_i})^2$$$ which is identical to your condition.

→ Ответить

iynaur87

2 года назад, # ^ |

Simple and clear. Sad that I did not get the equations.

→ Ответить

jakubd

2 года назад, # ^ |

+22

you don't have to guess, just $$$dp[i][sum]$$$ — min cost of $$$a[0...i]$$$ + $$$b[0...i]$$$ after doing swaps on first $$$i$$$ positions and sum of $$$a[0...i]$$$ is $$$sum$$$.

→ Ответить

Dmitriy_Bukharev

2 года назад, # ^ |

Could you explain please how does this give us the correct answer? I still don't really get it.

→ Ответить

jakubd

2 года назад, # ^ |

after going through other people's code and reading the editorial i found out that my solution is pretty retarded, since i did not realize some parts of the cost are independent, but whatever:

first let's assume we have just one array, for example $$$[1, 2, 4]$$$ and add $$$x$$$ to the end of it, how does the cost change?

$$$old cost + (1 + x)^2 + (2 + x)^2 + (4 + x)^2$$$, which if we rewrite is $$$old cost + x^2 + 2x + 1 + x^2 + 4x + 4 + x^2 + 8x + 16$$$. (just $$$(a + b)^2 = a^2 + 2ab + b^2$$$, which is what i should have realized earlier, because it means $$$a^2$$$ and $$$b^2$$$ are independent, but since i solved for one unknown, i did not realize that, anyways)

you can generalize that expansion to $$$i * x^2 + x * 2 * \displaystyle\sum_{j=0}^{i-1} a_j + \displaystyle\sum_{j=0}^{i-1} a_j^2$$$.

now let $$$dp[i][sum]$$$ have 3 values, the minimum cost and then $$$\displaystyle\sum_{j=0}^{i-1} a_j^2$$$ and $$$\displaystyle\sum_{j=0}^{i-1} b_j^2$$$.

The last two values are the retarded part, since they could be completely omitted, because each $$$a_i^2$$$ is counted $$$n - i$$$ times in the final cost. ($$$0$$$-indexed and same for all of $$$b_i$$$).

Anyways, first let's set all the of the states to $$$\{\infty, \infty, \infty\}$$$.

Base cases are $$$dp[0][a_0] = dp[0][b_0] = \{0, a_0 * a_0, b_0 * b_0\}$$$.

Now the transition are:

$$$dp[i+1][sum + a_i] = min(dp[i+1][sum + a_i], \{dp[i][sum][0] + f(i, a_i, sum, dp[i][sum][1]), dp[i][sum][1] + a_i * a_i, dp[i][sum][2] + b_i * b_i\})$$$
$$$dp[i+1][sum + b_i] = min(dp[i+1][sum + b_i], \{dp[i][sum][0] + f(i, b_i, pref_i - sum, dp[i][sum][2]), dp[i][sum][1] + b_i * b_i, dp[i][sum][2] + a_i * a_i\})$$$

$$$pref_i = \displaystyle\sum_{j=0}^{i} a_j + \displaystyle\sum_{j=0}^{i} b_j$$$ — sum of first $$$i$$$ values of $$$a$$$ and $$$b$$$.

$$$f(i, x, sum, sumOfSquares) = i * x^2 + 2 * x * sum + sumOfSquares + a_i * a_i$$$ — cost of adding $$$x$$$ to the end of an array with length $$$i$$$ and sum of it's elements and sum of squares of each of it's elements. (you can see the independent part of the cost being independent in this function too lmao, can't believe i have not noticed this while solving the problem for the first time in contest)

answer is then minimum of $$${dp[n][sum]}$$$ for all $$$sum$$$ from $$$0$$$ to $$$\displaystyle\sum_{i=0}^{n-1} a_i + b_i$$$.

I know, it's extremely retarded. But that's how i solved it during the contest (i can finally solve harder tasks than before, but most of the time it is this kind of an overkill for some reason) and you asked for it so ¯\_(ツ)_/¯.

if you have any questions, feel free to ask. but for your sanity, i recommend simply reading the editorial.

→ Ответить

Dmitriy_Bukharev

2 года назад, # ^ |

Thanks a lot!

→ Ответить

tgp07

2 года назад, # ^ |

I solved B really quickly but took an hour on C and had to leave the contest before I had a chance to solve D

→ Ответить

adamant

2 года назад, # |

+16

Somehow, you can pass pretests in E if you use unordered_map, but not gp_hash_table, is it intended? I thought gp_hash_table should be way faster... Also, my solution seems to be $$$O(n \log n)$$$ and is already quite close to the time limit, was it intentional that $$$O(n \sqrt n)$$$ doesn't pass? Or did it pass for others?

→ Ответить

ExplodingFreeze

2 года назад, # ^ |

You can solve it in $$$O(n \sqrt n)$$$ without unordered sets, though the TL is pretty tight even then.

I had to replace a map of vectors with a single vector of pairs to pass pretests since the constant factor difference in iterating over them was too heavy.

→ Ответить

JustasZ

2 года назад, # ^ |

My $$$O(n \sqrt n)$$$ passed pretests in 967/2000 ms

→ Ответить

Nots0fast

2 года назад, # ^ |

← Rev. 2 →

Mine passed pretests with O(n root(n) ), but i dont use any maps or hash tables for the bottleneck part of the code, e.g. the (n root(n) ) part doesnt use any maps, i map the values to [1 ... n] beforehand.

→ Ответить

Thallium54

2 года назад, # ^ |

I used map and also passed pretests. Hope I wouldn't fail system test.

→ Ответить

__shaun_0124

2 года назад, # ^ |

← Rev. 3 →

My $$$O(n \sqrt n)$$$ almost got TLE on pretest (1965/2000ms). Why $$$n \le 3 \times 10^5$$$ and 2s TL if $$$O(n \sqrt n)$$$ is intended?

→ Ответить

aniervs

2 года назад, # ^ |

My $$$\mathcal{O}(m\log^2n)$$$ solution with segment tree gave TLE twice before it passed all the pretests.

→ Ответить

2 года назад, # ^ |

The problem is likely the hash function you are using. See this comment.

→ Ответить

adamant

2 года назад, # ^ |

Yeah... I spent like an hour optimizing my $$$O(n \sqrt n)$$$ thinking it's the problem. But just replacing gp_hash_table with unordered_map was enough in the first place and I just wasted a lot of time trying to circumvent it.

→ Ответить

ajpiano

2 года назад, # ^ |

← Rev. 2 →

I'm kind of surprised to see that the TL was so tight for others since my $$$O(n\sqrt{n}\log{(n+m)})$$$ solution passed in 530 ms.

→ Ответить

BiouX

2 года назад, # ^ |

Read -is-this-fft-'s comment. It may be a non-sqrt solution.

→ Ответить

ajpiano

2 года назад, # ^ |

← Rev. 2 →

Oh you're right. It's $$$O(n\log{(n+m)})$$$. That's really interesting.

→ Ответить

Bohun

2 года назад, # |

How to solve G?

→ Ответить

BULLMCHOW

2 года назад, # |

wxhtzdy orz

→ Ответить

Jhin

2 года назад, # |

← Rev. 3 →

-16

never mind this is trash i had no time to think about it well

→ Ответить

chromate00

2 года назад, # |

+29

→ Ответить

vishaaaal

2 года назад, # |

What's the ideal time complexity to solve E?

→ Ответить

ParsaS

2 года назад, # ^ |

← Rev. 2 →

O(n * lg(n) + m * lg(m))

→ Ответить

LoboLobo

2 года назад, # ^ |

I solved it in O(N*sqrt(N)) with the ideia that if the sum of elements is equal N the number of different is O(sqrt(N)).

→ Ответить

PurpleThinker

2 года назад, # ^ |

I solved it in O(nlogn + mlogm) complexity (or something like that) and the "logn" and "logm" factors come from the C++ STL maps and sets I used, as well as the STL sort function. If you really want, you could replace the maps and sets with their hash-based counterparts and the STL sort with a count sort and get a linear time complexity... (I think)

→ Ответить

codersattu

2 года назад, # |

How to solve B?

→ Ответить

gogogofuxk

2 года назад, # ^ |

← Rev. 2 →

$$$dp[i][j][k] := $$$ the maximum cost to split $$$b[i, ..., j]$$$ into k subsegments minus j-i+1 (which means $$$dp$$$ includes only the sum of $$$MEX$$$ part).

base case: $$$dp[i][j][1] = MEX(b_i, ..., b_j)$$$

transition: $$$dp[i][j][k] = \max(dp[i][x][1] + dp[x+1][j][k-1]) \ \ \forall x \in [i, j)$$$

time complexity for calculating $$$dp$$$ is $$$O(n^4)$$$, then add up the solutions for all subsegments.

for a subsegment $$$[i, j]$$$ we care about the $$$k$$$ s.t. $$$dp[i][j][k] + j-i+1$$$ is the max.

→ Ответить

tgp07

2 года назад, # ^ |

For each a[i], I set its value to 2 if a[i] is 0 else 1. Then for each number, multiply its value by the number of subsegments it is in and add that to your answer. Finally, print your answer.

→ Ответить

barun511

2 года назад, # ^ |

← Rev. 2 →

notice that max cost on a subsegment is simply length of subsegment + number of 0's in subsegment. Just sum this value over all subsegments to get answer.

→ Ответить

MaltaDreamer

2 года назад, # ^ |

(One of) the best way(s) to break each subarray is always to break it into single elements. It brings the length of subarray plus number of zeroes in it. So the result is the sum of lengthes of all possible subarrays plus number of occurencies of zeroes in all of them. With given constraints, it is possible to brute force it.

→ Ответить

ACOIer

2 года назад, # |

← Rev. 4 →

-19

Weak and useless samples!

→ Ответить

ExplodingFreeze

2 года назад, # |

Imagine implementing $$$O(n \sqrt{n})$$$ in E (and doing constant factor optimization to get it to pass) only to realize afterwards the easier $$$O(n \sqrt{n} \log{n})$$$ solution somehow runs faster — 146115870

→ Ответить

fonmagnus

2 года назад, # ^ |

How do you come with the sqrt solution in E? I still don't quite get it. So basically we can just store the frequency of all numbers and bruteforcing each possible pairs?

→ Ответить

Thallium54

2 года назад, # ^ |

because there are at most $$$O(\sqrt{n})$$$ distinct cnt values.

→ Ответить

decrypto96

2 года назад, # |

-11

E was only about realizing we need to keep max 2 elements per count (max O(sqrt(n)) candidates )? Such low number of submissions completely threw me off :/

→ Ответить

Paul-Andre

2 года назад, # ^ |

Did your solution work? I think you need more than 2 elements per count in case those two elements form a bad pair.

→ Ответить

Yaria

2 года назад, # |

← Rev. 2 →

For problem D, it took me a long time to realize that the given cost is $$$(a_1 + ... + a_n) ^ 2 + (n - 2) * (a_1 ^ 2 + ... + a_n ^ 2)$$$, and the second part doesn't affect the answer.

But if I just guess "minimizing $$$|sum(a) - sum(b)|$$$", which is actually intuitive, then I can submit a solution much quicker. However, I don't think guessing is a good way to solve problems.

→ Ответить

dario2994

2 года назад, # |

+143

Feedback on the problems:

A: Ok.
B: The idea is nice, the way you decided to transform the idea into a problem, so-so. Would have been cleaner with $$$n=100\,000$$$ and just asking for the value of the array (instead of the sum over whatever).
C: Good problem. The moment I read it, I thought I was going to get stuck and in fact I got stuck (at least I am consistent). For me, this was much harder than D.
D: Very standard, solved immediately after reading.
E: Very good problem. I had to think and when I noticed that $$$cnt$$$ can have at most $$$\sqrt{n}$$$ values and this was sufficient to solve the problem, I was somewhat happy.
F: Cute problem. This felt easy, most likely because I was lucky and noticed immediately that rooting the tree at the highest vertex is useful.
G: (unexpectedly) Cool problem. The first thought reading it is "who cares?". Then, when I saw the point of the problem (which was shown to me by a backtracking), I changed my mind. I solved this in contest apart from the limit on the number of queries (because I was doing something incredibly stupid), solved 3 minutes after the end of the round. I enjoyed solving it.
H: Not read.

I enjoyed a lot the contest because the problems at "my level" (i.e., E, F, G) were very nice. Thanks to the authors.

→ Ответить

2 года назад, # ^ |

+11

Agreed. Despite having a solution to G but writing stupid buggy code and not being able to fix it in time, I really liked the round. My favourite problem was F (with my implementation, it was a data structure problem!) but I liked E as well.

→ Ответить

kuanc

2 года назад, # ^ |

+11

I got stuck at D for 1.5 hrs... Can I know how you mean by "very standard"? What's the first thought/idea after you read the problem?

→ Ответить

shashankag

2 года назад, # ^ |

+12

can you please tell why problem D is very standard. Thanks

→ Ответить

EvgeniyPonasenkov

2 года назад, # ^ |

+10

Thank you for participating and for positive feedback about this round. I am glad you like problem G!

→ Ответить

Darknez

2 года назад, # |

After this, I feel so dumb. :(

→ Ответить

lifeModder19135

2 года назад, # ^ |

Next time you feel that way, just click through my profile. It will make you feel better about yourself.

→ Ответить

lifeModder19135

2 года назад, # |

If we comment via the "ask a question" link during the contest, is it visible to everyone or just the commentor/ judges? I made a mistake where I thought there was a problem flaw where there was none and I didn't know whether or not to apologize because I didn't want to disrupt anyone who was still coding.

Also, if it is public, is there a better way to bring things like these up?

Thanks to all, and especially to the judges for a wonderful round (and for putting up with the annoyance I may have caused you.)

→ Ответить

Ammar2001

2 года назад, # ^ |

it's only visible to the judges, and if they found that there is actually a mistake they will announce it

→ Ответить

lifeModder19135

2 года назад, # ^ |

Thank goodness!!! I was afraid I had disrupted the competition for no reason. I still looked foolish, I guess, just not in front of quite so many people. XD

Thank you for reply. +1

→ Ответить

-is-this-fft-

2 года назад, # |

← Rev. 2 →

+140

E is interesting in the sense that based con some conversations I bet there are a lot of people who wrote an $$$O((n + m) \log n)$$$ or similar non-sqrt solution without realizing it.

My solution is basically this:

1 for (int cx = 1; cx <= n; cx++) {
2   for (int x : wcnt[cx]) { // the list of things with cnt[x] = cx
3     for (int cy = 1; cy <= cx; cy++) {
4       // try the best non-forbidden y with cnt[y] = cy
5     }
6   }
7 }

Trivia question: how many times is line 4 hit? Answer: it is in fact $$$O(n)$$$. For a fixed $$$x$$$, the number of times line 4 is executed is the frequency of $$$x$$$, so in total we visit line 4 once for every element in the array.

I believe this proof can be adapted to several people who proudly claimed to have passed E in $$$O(n \sqrt n)$$$ or even $$$O(n \sqrt n \log n)$$$ with "no constant optimizations".

→ Ответить

link: https://codeforces.com/contest/1637/submission/146139122
https://codeforces.com/contest/1637/submission/146157321

2 года назад, # ^ |

+26

haha, I was guilty of this, good observation!

→ Ответить

Yogesh.Joshi

2 года назад, # ^ |

-32

can u explain me test case 3 2 1 4 5 in problem A ,as it can be sorted by prefix and suffix

→ Ответить

andrei_boaca

2 года назад, # ^ |

You are not asked to find whether you can sort the array, but if you can make the operation so that the array is NOT sorted. Thus, choosing the prefix formed by the first two numbers and the suffix with the last 3 numbers would solve the testcase.

→ Ответить

usernameson

2 года назад, # ^ |

I figured out the approach but I failed the system test because I had a typo in the break condition where I wrote ans>(cx+cy)(x*y) instead of (cx+cy)*(x+y). My solution when I replaced the * and submitted after the contest.

→ Ответить

meaningIess

2 года назад, # ^ |

-29

But your program actually is O(n sqrt(n)). I generate a data and your program updates ans 329094649 times.

→ Ответить

meaningIess

2 года назад, # ^ |

sorry I read the wrong number.It's O(n).

→ Ответить

riadwaw

2 года назад, # ^ |

I have something like

for (int x: unique_numbers) {
   for (int cnt_y: existing_cnts) { // no cnt_y <= cnt[x] check
      // find first non-forbidden y with cnt[y] = y
   }
}

Which works fast-ish as well. Do you understand if it's faster than O(n sqrt(n)) as well?

→ Ответить

-is-this-fft-

2 года назад, # ^ |

← Rev. 2 →

+35

I initially thought just this this would be faster too, but it looks like this is still $$$\Theta(n \sqrt n)$$$.

The complexity is the number of distinct frequencies, multiplied by the number of distinct values. For a given $$$n$$$ we can construct a bad case like this. Let $$$a$$$ be the number of distinct frequencies. Make a number with frequency 1, a number with frequency 2, ..., a number with frequency $$$a$$$, then add numbers with frequency 1 until we have filled the array. The number of distinct numbers is $$$a + n - \frac12 a(a + 1)$$$; the complexity will then be

$$$a \left( a + n - \frac12 a(a + 1) \right).$$$

Using calculus to maximize it for $a > 0$ shows that we can pick $$$a$$$ to get $$$\Theta(n \sqrt n)$$$ runtime.

EDIT: I tried to hack you and got unexpected verdict. People tell me this is due to a tester (?) solution failing. Maybe tests are indeed weak here?

→ Ответить

riadwaw

2 года назад, # ^ |

It got rejudged. Almost 3x from the worst real test, but still passing :)

→ Ответить

Ammar2001

2 года назад, # |

+11

I enjoyed this contest, it required a lot of observation, and problem C felt like a troll :D

took many tries and observations to figure it out, but eventually i solved it.

→ Ответить

Yogesh.Joshi

2 года назад, # |

← Rev. 2 →

-8

In problem A. 3 2 1 4 5 can be sorted as 3 2 1 and 4 5 are sorted individually so ans will be no ,but many has written solution as if there is increasing array ans will be yes. can anyone explain me this test case .

→ Ответить

lis05

2 года назад, # ^ |

... and then sort in non-decreasing order the prefix ...

→ Ответить

akwa_blue

2 года назад, # ^ |

I did the same mistake at first and wasted stupidly 1 hour on A. What you should do is find a value len for which the array is not going to be sorted at the end, if found then YES otherwise NO.

→ Ответить

Sibin_Thomas

2 года назад, # ^ |

solution is to just check if the array is sorted.

→ Ответить

andrei_boaca

2 года назад, # |

Nice round! E was cute but I was a bit dumb on it.

→ Ответить

tiasmondal

2 года назад, # |

← Rev. 2 →

For me, Problem C is harder than D and E. But liked the observation in C the most.

→ Ответить

AdityaG

2 года назад, # |

did the 700th upvote:) nice problems , loved problem D

→ Ответить

cmll02

2 года назад, # |

+33

pretest in E is so weak...

→ Ответить

willy108

2 года назад, # ^ |

+17

+1 to this

One would think that a max test would be

1
300000 0
1 1 1 ... 1 1

but that has no solutions. so instead if you had done

1
300000 0
2 1 1 1 ... 1 1

you would have made the simplest max test. and yet not a single test in the pretests had an element occur more than 800 (which was a constant in my code) times.

→ Ответить

cmll02

2 года назад, # ^ |

i find that. I just calc ans like (i+j)*p.w instead of (u+v)*p.w and it passed pretest:(

→ Ответить

sevlll777

2 года назад, # |

+64

F is cool, create interesting&fresh task on tree is giga hard nowadays, so thanks to authors :)

→ Ответить

Sibin_Thomas

2 года назад, # |

-9

Didn't use long long in C. (T_T)

→ Ответить

Nahian9696

2 года назад, # ^ |

Same
Got two submission wrong for it :)

→ Ответить

Restricted

2 года назад, # ^ |

Same, I lost my expert for it :)

→ Ответить

Neal_lee

2 года назад, # |

MikeMirzayanov My submission on E got TLE on system test. But the exactly same code passed after the contest.

Could you rejudge the submission please? Thanks in advance!

→ Ответить

Neal_lee

2 года назад, # ^ |

← Rev. 2 →

+18

The test case where I TLEed only takes 1871ms. The volatility is more than 129ms, which is a bit huge. I felt really bad about this :(

→ Ответить

MrOtter

2 года назад, # |

Spent too much time on C but solution is concise and pleasant 146131266

→ Ответить

2 года назад, # |

How to prove that "minimum power of two at least n" is the minimum achievable value in G?

→ Ответить

BurnedChicken

2 года назад, # ^ |

+136

If we "undo" two numbers $$$x,y$$$ then two numbers become $$$\frac{x+y}{2},\frac{x-y}{2}$$$, so we can never get rid of any odd prime factor of the final value.

→ Ответить

2 года назад, # ^ |

nice proof, thanks

→ Ответить

AnACPlease

2 года назад, # |

Fast Rating Change!!

→ Ответить

2 года назад, # ^ |

-15

Apparently, there was no plagiarism in this contest. The ranks during the contest are same as final standings. In the last educational round, Mike said that there would be a recheck and ratings would be updated after removing cheaters, and apparently, ratings never got updated. https://codeforces.com/blog/entry/99483?#comment-883045

→ Ответить

2 года назад, # |

-8

Can somebody please point out whats happening? I used modified knapsack in D and here are two submissions Solution 1 AC Solution 2 WA The only difference between them is that I sorted arrays a and b before knapsack in solution 2 but that should not affect the answer. Can somebody point out the reason? Thanks in advance

→ Ответить

Vladithur

2 года назад, # ^ |

You can only swap $$$a_i$$$ and $$$b_i$$$ for some $$$1 \le i \le n$$$, not $$$a_i$$$ and $$$b_j$$$ for some $$$1 \le i, \ j \le n$$$.

→ Ответить

2 года назад, # ^ |

-8

oh shoot didn't notice that detail thanks a lot

→ Ответить