Codeforces Round #886 (Div. 4) Editorial

mesanu's blog

Tutorial of Codeforces Round 886 (Div. 4)

4 days ago, # |

It feels like Problem A was directed at someone 😶

4 days ago, # ^ |

← Rev. 2 →

+14

It is easy to write verses

When you have not what to tell,

Stinging words and hollow phrases

In a gangling doggerel.

4 days ago, # |

Thanks to authors! The problemset was very cool

4 days ago, # |

I enjoyed the problems

4 days ago, # |

This competition is the best for me.

4 days ago, # |

The best competition for me is this one.

4 days ago, # ^ |

sqrt is log(n), so in fact there are no O(1) solutions

4 days ago, # ^ |

can u explain how can i get 128 bit integers working on my local compiler?

4 days ago, # ^ |

← Rev. 4 →

because your computer dose not have a 64-bit compiler.

128-bit int works only on 64-bit compilers.

4 days ago, # ^ |

its not working though

4 days ago, # ^ |

sorry i mean u don't have 64-bit compiler

4 days ago, # ^ |

calculating the sum takes O(N) time

4 days ago, # ^ |

heh) I saw the problem and immediately thought about binary search and solving the equation. I decided to choose the second one and as a result I first wrote the code for pluses, and then for python (I never used int128)

3 days ago, # ^ |

Hey, How come you have reached to this solution? Can you please explain about your quadratic formula approach

3 days ago, # ^ |

← Rev. 3 →

A painting with side s_i requires a cardboard square with side (s_i + 2*w).

The total area of the cardboard squares (the c input in the problem) is:

sum (s_i + 2*w)^2 = c <=>

sum (s_i^2 + 4*s_i*w + 4*w^2) = c <=>

sum(s_i^2) - c + 4*sum(s_i)*w + 4*w^2 = 0

The last equation is quadratic in terms of w and we can solve it using the quadratic formula

3 days ago, # ^ |

← Rev. 2 →

Nice, using commutative and associative properties of sigma, but It didn't clicked to me. This proves how silly I am :(

3 days ago, # ^ |

tried yours in mine, why does it gives compilation errorcode

3 days ago, # ^ |

It will not compile on 64 bit system. It is using __int128 which is of 128 bit

3 days ago, # ^ |

I used c++20

3 days ago, # ^ |

I tried doing like that in C++ but didn't get around precision values

3 days ago, # ^ |

Yeah long double was not going to cut it

3 days ago, # ^ |

That’s what i did, had problems with the output for large numbers tho, but it’s O(n), not O(1), instead of O(nlogn)

4 days ago, # |

Such a terrible contest. Literally just storing the frequencies of elements in a dictionary gets TLEd in Python/PyPy for G.

4 days ago, # ^ |

i got hacked on G (tle) because for some reason i thought i had to sort the points in order to get the intersection with y = x+c and y = -x + c lines.

It turns out this is unnecessary and you can solve the question with linear time O(N).

HACKED submission O(Nlog(N)

O(N) submission

4 days ago, # |

For anyone using JAVA , never ever use Arrays.sort even after shuffling the array, I got unnecessary TLE and rectified using Collections.sort. The tests were designed carefully.

2 days ago, # ^ |

Yes as Arrays.sort uses counting sort versus Collections.sort implements merge

4 days ago, # |

What is a failed test case for this solution for D?

214942704

4 days ago, # ^ |

I make the same code and i do not know where is the wrong

4 days ago, # |

Editorial published during open hacking phase?!

4 days ago, # |

G Problem is kind of impossible with python

4 days ago, # ^ |

Even if we forget the fact that there are workarounds to the hash hack in python, we can still solve the problem using python quite easily.

Instead of using maps/dictionaries, we can just store all values of $$$x$$$, $$$y$$$, $$$x + y$$$ and $$$x - y$$$ in four separate arrays, sort each of them and check the number of equal elements that way. And as far as I know, there is no hack for sorting in python (unlike in java).

Code (pls forgive me for horrible python): 214952260

4 days ago, # ^ |

thanks got it now sorting also a good option

4 days ago, # ^ |

← Rev. 2 →

i got hacked on G (tle) because for some reason i thought i had to sort the points in order to get the intersection with y = x+c and y = -x + c lines.

It turns out this is unnecessary and you can solve the question with linear time O(N).

HACKED submission O(Nlog(N))

O(N) submission

4 days ago, # ^ |

← Rev. 2 →

+12

That is (quite obivously) code obfuscation, which is not allowed. Hopefully they'll get skipped for breaking rules.

4 days ago, # ^ |

what does code obfuscation mean?

4 days ago, # ^ |

If only there was some magical place where you could just type the words "what does obfuscation mean" and you'd get an answer instantly...

4 days ago, # ^ |

But how many defines is code obfuscation then? Some c++ solutions are absolutely unreadable even though their authors had no intention to muddle their code.

4 days ago, # ^ |

← Rev. 2 →

I don't think there are any specific numbers I can give; I think the more important part is intention:

If the author didn't intend to make the code unreadable (and they can read it themselves), I wouldn't call it obfuscation.

If the author deliberately made the code unreadable (possibly using automated help), I would definitely call it obfuscation.

I think it should be clear that the aforementioned code falls under the second case.

4 days ago, # ^ |

Unfortunately I saw a lot of solutions with defines like this that make the code unreadable. But I don't really know what to do with that as I haven't found any flag/signal. button yet.

3 days ago, # ^ |

I think the only reason you said this is because you cheated.

3 days ago, # ^ |

Could you elaborate?

3 days ago, # ^ |

Of course, this is an obvious violation of the rules, and the user will be punished.

3 days ago, # ^ |

lesss gooo !

3 days ago, # ^ |

Can you see the message that I sent you. Please coach

3 days ago, # ^ |

What the hell lol.. he seems too scared of being hacked

4 days ago, # |

Hello! This is my first contest and I submitted the problem A. I was registered but I do not see an increase in my rating, can someone tell me when will I get them?

4 days ago, # ^ |

check again tommorrow afternoon (indian time)

4 days ago, # |

can someone try to hack my solutions?

4 days ago, # |

I used binary search for problem-E but it has some error which I am unable to figure out. Can anyone please help me find error in my binary search logic for my submission 214950555. ? edit : when i set r = 1e10 the sample test-cases passed but on submission it fails again on some test case.

4 days ago, # ^ |

it looks like the res function might overflow, I had that problem and dealt with it as explained in the editorial. you can also use __int128 instead of long long to avoid overflow.

4 days ago, # ^ |

try r=sqrt(c) , it's the smallest value of r that can be valid

4 days ago, # ^ |

true, an alternative is also to use r=1e9+1.

4 days ago, # |

Thanks for this round. The round was very enjoyable!

4 days ago, # |

← Rev. 2 →

Why this solution TLE in problem F because It does unnecessary work when we have more occurrences of one elment. I think the TC Is exactly the same as the one proposed by the editorial in the end. Also if we have the test case 1,2,3....,2e5. The solution posted does the same number of operations as the one of the editorial. Am I wrong thinking that this has the same TC as editorial?

4 days ago, # ^ |

If all n values of ai are equal to 2, each one will need n/2 iterations, in total n*n/2 operations.

Therefore it is necessary to treat together the array values that are equal.

4 days ago, # |

maybe f can be hacked, consider case {1,1,1...} * 10^5

3 days ago, # ^ |

We keep in cnt_i how many frogs we have for each hop distance.

this prevents it.

3 days ago, # |

i think E problem's optimal solution O(N) my submission

3 days ago, # |

← Rev. 4 →

I liked problem H . Before reading editorial, i didn't though it will turn that easy.

3 days ago, # |

can someone explain why my E solution is accepted here:
https://codeforces.com/contest/1850/submission/214991383

but it is failing here:
https://codeforces.com/contest/1850/submission/214991353

the only difference is in my accepted version, i did (sizes[i] + w * 2) * (sizes[i] + w * 2)
but in the failing version, i did pow((sizes[i] + w * 2), 2)

3 days ago, # |

Can someone help me understand why my solution for G got hacked? I have written same code as tutorial. https://codeforces.com/contest/1850/submission/214891422

3 days ago, # ^ |

Because you are using unordered map which has a worst case time complexity O(n). Read this for more information:https://codeforces.com/blog/entry/62393

3 days ago, # ^ |

Thanks, I never considered this issue. I guess just stick to map unless unordered_map is really required.

3 days ago, # |

Really a very good, balanced, and learning contest for beginners.

Thanks to the Author.

3 days ago, # |

← Rev. 4 →

In this contest can my E be WA, G be TL?

My submission in E in contest: 214829184. I don't know how it's passed pretests. In code wrongly I did: x = s[i] + 2 * md + 1 and printed l but x should be s[i] + 2 * md and printed l — 1. Like this code: 214997775 which I submitted after contest. Please let me know if it's hackable.

My submission in G in contest: 214869824. Can it be TL or ML? It passed pretests with 1668 ms 76900 KB(Time limit is 2s). After contest I optimized it (removed set) and passed pretests with 904 ms 39300 KB(214997753). Please let me know it's hackable.

3 days ago, # |

Very good problem set. Thanks to all the people who were involved in organizing this round.

3 days ago, # |

can you guys pls explain to me how not to get integer overflow in my submission?

https://codeforces.com/contest/1850/submission/215016417

3 days ago, # ^ |

Someone suggested me to use long double and it worked. While printing the value, typecast it into long long to get the desired format

3 days ago, # |

I was wondering if someone used Newton Raphson method for solving E?

3 days ago, # ^ |

I doubt it, it's too overkill for a problem like this.

3 days ago, # |

During the contest,I misunderstand Problem F,I think each second we can place a trap,so in this case,can we also calculate the maximum number of the frogs we can catch?I need help,thanks.

3 days ago, # |

← Rev. 2 →

Nice round , I hope all next rounds(div4) will be on this level

3 days ago, # |

← Rev. 2 →

Hello, during the contest I submitted this code which got accepted, but after that my code go from accepted to "In queue", can anyone explain? Thank you

Here's the link to the code: https://codeforces.com/contest/1850/submission/214905784

3 days ago, # ^ |

It is just getting reevaluated

3 days ago, # |

Can anyone help me my code has resulted in TLE in system testing?, it is having similar complexity as of author O(nlogn)

Code

3 days ago, # ^ |

← Rev. 2 →

Your code does about this many iterations $$$\sum_{x=1}^{n}\sqrt{x}$$$, but the TLE is probably because you are using unordered map, i advise you to read this article:https://codeforces.com/blog/entry/62393.

3 days ago, # ^ |

Your code is $$$O(n^2)$$$ because of unordered_map

3 days ago, # |

MikeMirzayanov Unlike the original contests/exams in real life,can I get assistance from external websites while doing a contest? I mean it's quite easy,I have seen it. I am doubting a lot

please answer my question

3 days ago, # |

The solution of F was already available on geeks for geeks and other various websites , seems to be a quite popular problem

3 days ago, # |

how does my morning star submission got hacked I did the same thing said in the tutorial lol

3 days ago, # ^ |

No offense, but you are the millionth person already asking the same question. It is because you used unordered map which can be hacked easily if you don't use a custom hash. Read this article for more information:https://codeforces.com/blog/entry/62393.

3 days ago, # ^ |

none taken haha, thank you tho.

3 days ago, # |

← Rev. 2 →

I used an unordered map on F. I will never use an unordered map again.

3 days ago, # |

Why does that give TLE if unordered_map is used instead of the normal map in C++? Can anyone tell me when to use unordered_map and normal map?

3 days ago, # |

← Rev. 3 →

Can anyone explaine how Wrapper function works? This is my hacked submission: https://codeforces.com/contest/1850/submission/214906792 And then i fixed it by Wrapper function which make my submisson accept https://codeforces.com/contest/1850/submission/214984466 *sorry for bad english

3 days ago, # |

can someone tell why Question 'G' Fails for an Unordered map, but runs absolutely fine for ordered map

void mr_kamran(){

ll n; cin>>n; ll ans = 0; unordered_map<ll,ll>m1,m2,m3,m4; for(int i = 0;i<n;++i) { ll x,y; cin>>x>>y; m1[x]++; m2[y]++; m3[y-x]++; m4[y+x]++; } for(auto it : m1) { ans+=(it.second*(it.second-1)); } for(auto it : m2) { ans+=(it.second*(it.second-1)); } for(auto it : m3) { ans+=(it.second*(it.second-1));
} for(auto it : m4) { ans+=(it.second*(it.second-1)); } cout<<ans<<an;

3 days ago, # ^ |

Check the editorial, this question has been answered a million times here.

https://codeforces.com/blog/entry/62393

2 days ago, # ^ |

there might be some internal collisions due to the internal implimentation of unordered maps

3 days ago, # |

COULD ANYONE PLEASE EXPLAIN WHY USE OF THE QUADRATIC FORMULA IS NOT WORKING IN E PROBLEM?

3 days ago, # |

Regarding Maths solution for E problem

Why I get compilation error for this solution: https://codeforces.com/contest/1850/submission/215091151

but this other solution works: https://codeforces.com/contest/1850/submission/214911845

im going crazy, literally same thing

Pleasse help someone

3 days ago, # |

Solved problem H using Union Find.

215052919

3 days ago, # |

Hello, guys, could you share some useful resources about harmonic series, especially how it can be used in solving cp problems?

3 days ago, # |

is it possible to solve problem G with dp ?

2 days ago, # |

why my solution isn't working on 2 test case in problem B. code

2 days ago, # ^ |

int ans = v[0].second;
int mx = 0;

Consider the case when first pair was 11 and INF . your answer won't get updated

2 days ago, # ^ |

isn't that what the problem wants, not to get updated if > 10 is first value

2 days ago, # ^ |

well , you are assuming that the v[0].first will not be greater than 10.

2 days ago, # ^ |

well, i am using &&(AND) so it should'nt get updated

2 days ago, # ^ |

You gave the variable mx value 0 before even checking v[0].first is less than 11 or not . Change both ans and mx to -1 and it should pass

2 days ago, # ^ |

it worked. Thanks, learnt the lesson.

2 days ago, # |

← Rev. 2 →

Code

1850E - Cardboard for Pictures

Can someone Explain Why my code gives WA? For Some Test Cases it the While Loop Breaks and prints 1 which I used for Checking.

2 days ago, # ^ |

in your predicate function (s) 'ans' variable is overflowing.

to combat this return ans as soon as it becomes larger than c

ll s(ll md, vector &v) { ll ans = 0; for (ll i = 0; i < v.size(); i++) { ans += ((v[i] + 2 * md) * (v[i] + 2 * md)); if(ans>c) return ans; } return ans; }

2 days ago, # ^ |

Thanks, It worked!!

How did you spot it?

2 days ago, # ^ |

like md is 1e9 now you square it becomes 1e18

now you are adding it a maximum of 1e5 times

so 1e18 X 1e5 will give you 1e23 — overflow

2 days ago, # |

Problem E was headache for beginners. Handling large int values...ahhh!

2 days ago, # |

why F is nlog(n)? if there are 2e5 1 than is n*n

2 days ago, # ^ |

hash the count of each number

so even is there are 1e5 1s the answer will run in n

2 days ago, # ^ |

I don't think they say that in this problem .Is there a hint here? It is guaranteed that the sum of n over all test cases does not exceed 2⋅105

2 days ago, # ^ |

i did not get your point sorry lol

2 days ago, # ^ |

the problem f isn't say hash the count of each number.

2 days ago, # ^ |

you just have(can ig) to do it in order to solve it lol

2 days ago, # ^ |

sorry ig our views differ due to our solutions

2 days ago, # ^ |

but i also n't understand

2 days ago, # |

why in problem G it gives TLE error if we use unordered_map<int,int> instead of map<int,int>. The time complexity of unordered_map is O(1) whereas operations on map take O(log n) time.

43 hours ago, # |

problemset was so cool but i think the "word on the paper" problem was too easy for problem C

31 hour(s) ago, # |

For problem H dfs gives me runtime error, and

sol2 sol is getting accepted, Can someone explain me why??

20 hours ago, # |

Hey guys! Can somebody help me please why in task E — Cardboard for Pictures we should use mid = l + (r — l) / 2? I am new at this and would appreciate any answer)

9 hours ago, # |

In H if there is a cycle can one of the 2 paths give us correct coordinates and another one not.Like can this be a case?

6 hours ago, # |

← Rev. 2 →

How to approach problem F if condition would have been that we place one new trap each second unitl game conitnues. Thanks In advance

5 hours ago, # |

Nice problems but i got minus xD

mesanu's blog

Recommend

Samsung Galaxy F34's key specs and design revealed, launching soon

虚幻引擎5再现《失控玩家》！游戏NPC在线怀疑人生

多益输掉商标官司《神武4》或被迫改名，称“判决非常不合理”

海信海外推出U8KQ电视支持120Hz/144Hz刷新率

韩国跨行业人工智能联盟启动，成员包括现代汽车、LG 电子等头部企业

Why does IAsyncAction or IAsyncOperation.GetResults() produce a E_ILLEGAL_METHOD...

网易严选马蹄椰椰爽清补凉“走红”，布局千亿级养生食补赛道-品玩

LG 推出搭载全新 AI 芯片组的下一代可升级家电产品

《使命召唤：现代战争III》宣传物料曝光，以红色为主题色 - 超能网

广联达：已构建建筑行业 AI 大模型层、工具平台层、产品应用层三层 AI 技术体系

About Joyk