Top Comments

My real father is 2-gon.

orz you son :)

Yeah, since the blog under which I originally commented that was deleted, let's remind everyone of it.

Later, he said "fuck your whole family" in a comment.

I found out that I've saved it! :D

Screenshot-20210611220724-857x462

Seems codeforces finally realized nobody reads this rules anyways, so they just removed it lol

My son is on a journey to become a Pokémon master. So he doesn't do competitive programming. So I am commenting on his behalf.

-is-this-fft- not so long ago somebody messaged you about it, if I’m not mistaken.

Radewoosh Daddy

All those downvotes are from Radewoosh alt account.

On NM_MehedyIs cerr evil?, 18 hours ago
+44

Nothing is absolutely free. Your debugging print code consumes precious CPU cycles.

I used to treat ARCs as Div. 2 contests.

I was wrong.

Plot twist- both these accounts are managed by the same person.

Normally people do not personally message for asking their doubts (unless you know the person well, are friends with the person) so you don't go messaging strangers for your doubts.

You can ask in the editorial blog but the likelihood of getting a response goes lower and lower depending on how old the blog is.

Finally you can make a blog of your own if the doubt is out of your reach and you have tried plenty. In that case you will have to let people know what all you have done so far in terms of resolving your doubt and what you are exactly stuck on. (In short don't keep things vague and expect people to understand your doubt)

And well most people just go around reading editorial, looking at the editorial blog comments and looking at other AC submissions. (This is the most preferred method)

On T1duSIOI 2021 predictions, 32 hours ago
+38

My money is on rainboy

On T1duSIOI 2021 predictions, 32 hours ago
+36

waiting for rainboy to submit Compilation Error with a poem in the last minute of IOI.

Reminder that contest starts in 5 minutes

Everything you need to know about rating is in these two blogs. Your specific confusion is answered by the second blog.

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

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

I am very interested to meet that 2.95% people who fit in that >65 years criterion. Imagine a kid seeing his grandpa smacking keyboard while doing problems lol.

As a tester I enjoyed the problems very much and think you will too.

Just practice. I don't start coding right after reading unless I have the complete solution down to details. Usually, I spend 30 seconds to 5-10 minutes just thinking about details I might have missed and easier/cleaner ways of implementing the solution even after having a correct general idea about the solution.

As an exercise: Try to think about the complete solution before coding. If you had to fix your idea in a big way then you probably could've saved time by thinking before coding.

Extra: use meaningful variable names. Anyway, coding an idea isn't that much of a problem when compared to having a fuzzy idea and thinking details aren't important.

proud

On T1duSIOI 2021 predictions, 31 hour(s) ago
+30

As someone already said, gamegame will win IOI 2021.

Leaf -> 100%

You ain't happy with your present dad? Damn, he must feel so disappointed.

+27

We will solve all the queries offline. The topics which we will require are centroid decomposition, rolling hash, lca and binary lifting. Lets say we have a node $$$u$$$ and there is some query whose starting node is $$$u$$$. Then we can check all the paths(In given tree) whose one end is $$$u$$$ using the ancestors of $$$u$$$ in centroid tree(These ancestors will be internal nodes of paths in given tree). This can be done by maintaining an array for each path_length (Of paths in given tree) from current root (current root is root of subtree while traversing a subtree of decomposed tree) which will have least lexicographic "path" and we do updates everytime we go to a node.

After each update we need least lexicographic answer possible. So for update, we use binary search on hashes (which we can store in $$$O(N)$$$ and query them in $$$O(1)$$$ time) and binary lifting to find the first node / character between two candidate "path" to get the first mismatch and we compare them accordingly.

The final time complexity is $$$O((N + Q) * log^3N)$$$ in which $$$O(N*logN)$$$ is from travelling each subtree of centroid tree, $$$O(Q*logN)$$$ is from getting the final path for each query. Also, every time we perform an update it takes $$$O(log^2N)$$$ (Because of my implementation).

If any one has other approach / solution then do mention them here. Hope every one liked the problemset :P

solution

But you looks older

+26

Thanks for the contest!

How do you solve BLAZE and TATAKAI? For BLAZE we think the number of possible strings is about N, but we haven't gotten beyond that.

On infinitus11Plagiarism False Positive, 41 hour(s) ago
+26

Sorry, I'll revert it.

Soon there will be problems in codeforces named as ... 1)Yet another cheater....

2)Even I am tired...

Problem D: Try and fail to write the solution by yourself. Remember there's a XOR MST problem in codeforces, google it and copy a solution from there

https://codeforces.com/contest/888/submission/32165432

https://atcoder.jp/contests/arc122/submissions/23373118 ;)

For real, what's the point of making combined round when there are enough problems to split round for both divisions? Nobody from div1 wants to solve first few problems as well as nobody from div2 even reads last few problems

The final for me was yesterday with nadal :P

Who is the real father of tourist ?

On T1duSIOI 2021 predictions, 32 hours ago
+22

kostia244 will win.

Damn, I can't even spell prodigy and ambidextrous too correctly, then how could I have been one?

F*ckin' precision errors >:O

On maroonrkdoubleCompare in testlib.h, 3 hours ago
+20

Thanks, I'll merge it.

Wait.. You guys still have hair?

Think in terms of graph, assume line to point graph, it will be bipartite, then the question is minimum vertex cover on bipartite graph, or MBM using konig theorem.

And such a proud father he must be.

Somewhat big gap from D to E

The ones who have this time to share & arrange solutions till B or C are gonna stay there forever. I know a tripod of cheaters who do that sort of thing eveytime and I used to stare at their profile everyday, but now I don't care anymore cause I hv already surpassed them all, becausE, I stand on my own and won't ever need any unethical support to prove myself.

I don't think so,

Remember that only the trusted alts of 1-gon's have 100+ contribution.

There is a separate rule for trusted contributors that qualify as 1-gon's alt and you should read it. You can find it in the announcement of recently concluded Div3, 4th para of <almost-copy-pasted-part>

His dad is his dad and not him, if that makes sense.

+17

Team Rocket: You can maintain two range sum trees, one for each dimension. Then, notice that all the information you need is the sum for a suffix of points considering the X coordinate and the prefix of points considering the Y coordinate.

Jiggly Puff: Create a bipartite graph with $$$2*N$$$ nodes: nodes on one side representing the indices and the other representing the values. Add edge from value $$$V$$$ to index $$$i$$$ if $$$i$$$ divides $$$V$$$. Run a bipartite matching, is guaranteed to be complete. Print the matches.

Can I please get a pikachu. You must be having few in your training center :pleading face:

I think the solution will be pretty much the same.

It would be exactly the same, but when you are computing the expected value you multiply by the probability, not by $$$1/n$$$.

In this code, in function f you can just replace E += p * v; with E += p[i] * v;.

If nodes get removed after each query, maybe you could just solve the queries in reverse, and add nodes instead of removing them?

Do you have link to the problem? So, what I understood is that we have 2 arrays of same size, and we have to make an array C consisting of distinct elements, and of the same size such that for each index i, the element is either from array A or array B?

I used to treat ABCs as Div. 3 contests.

F's editorial: This can be boiled down to a maximum flow problem.

So I was wrong again? -_-

+16

We thought of BLAZE via suffix automaton and small to large merging. Think it like this, for a node in automaton, it corresponds to a set of continuous suffixes with set of endpos. Also for a unique string from that set, the power is achieved from closest 2 indices in it's endpos set. So we can maintain the closest pair of indices using small to large merging on the suffix link tree of the automaton. And from there, it's basic math.

+16

Yes that's correct, I implemented this approach and got AC. But I still wonder how $$$O(Nlog^{2}N)$$$ was intended to pass in 1s. I tried a lot to optimize this approach but ended up trying luck and it passed lol.

Usually it just takes intuition, like thinking out how you'd prove it, but not getting into all the details. It helps to think about the corner cases as well.

Relatable.

"Recent Codes" option should be removed from Ideone -_-

I implemented a different solution for B than the one in the official editorial. Hopefully it will prove interesting for some:

We should find minimum after x and y for: (n * x + PS[n] - PS[y] - 2 * x * (n - y)) / n, where PS[i] is the sum of the first i elements of the sorted input array. Basically, y is an index such that all elements 1 <= i <= y will provide min(A[i], 2x) = A[i] and all elements y < i <= n will provide min(A[i], 2x) = 2x. This also suggests a constraint for a fixed y: V[y] / 2 <= x <= V[y + 1] / 2.

Minimizing the formula above is the same as minimizing: n * x - PS[y] - 2 * x * (n - y) = x * (2 * y - n) - PS[y]. In order to minimize this, we can iterate 1 <= y <= n and find a suitable x. In fact, if 2 * y - n is negative, x should be as large as possible, so x = V[y + 1] / 2. Otherwise (2 * y - n is positive), than x should be as small as possible, so x = V[y] / 2.

i want solve first few problems :p

I hate to break it to you but these guys already know each other. And so this has nothing to do with Ideone. Also, if in the case it were, they would have already commented about it which they didn't because of guilt.

Nice blog! I like solving problems which use such ideas, so here are a few more problems with a similar flavour:

1436F - Sum Over Subsets

Chefsums

1493D - GCD of an Array

lol angel priya on codeforces too

Yes

I think you forgot to add prefix before grandmaster

Portugal:

Good suggestion, it could be relevant back in 2011, but in 2021 problemsetters and coordinators don't have balls, so there are no hacks at all.

Reminder that contest starts in 4 minutes

Reminder that contest starts in 3 minutes

I didn't solve it :P

In C++, comparator should return false if its arguments are equal.

On NM_MehedyIs cerr evil?, 15 hours ago
+14

Even if cerr is redirected to /dev/null, the useless output strings are still being created in huge amounts. The blog author's main loop contains only a tiny amount of arithmetic operations. But each of these loop iterations also tries to at least create one useless std::string and print it to cerr with a ton of overhead.

The failing testcase prints 211.5k lines to stderr and 100 lines to stdout. But I agree that this shouldn't have been fatal. On my computer it takes just slightly more than one second to run if I redirect stderr to /dev/null. And my computer is slower than the codeforces judge.

It's safer to put the debugging print code inside of an #ifndef ONLINE_JUDGE block either way.

For some reason there is a scoring distribution update in the English version of this blog post, but there is no one in Russian version.

UPD: It's ok now.

+13

This much code... Huh. Anyways problemset was good.

Thanks for making this blog, especially since now I don't need to make another blog for this question — on Yosupo Library Checker, there is this submission that runs in a blazing fast 23ms. It does not seem to be the same Meissel-Lehmer approach described in this blog or elsewhere. Can anyone explain it?

Post their full name and college too, along with their CF ids. Atleast this way, they won't be able to name themselves on CF anymore.

I believe you missed that blog ;)

It says that $$$0 \%$$$ of codeforces users are $$$< 18$$$ years old. hmm... also curious about how they are able to garner demographics data...

Great blog! I have been long looking for someone detailing this more rigorously. Seems this thread provided everything that I was looking for.

To add more practice problem, you may try to solve Project Euler 245 if you want it to run under 1 second.

And as another bonus (I think it is worth mentioning), the totient summatory function can also be computed using the same ideas.

Please never change the original comment, now all replies make no sense to upcomming readers.

for prize distribution purposes :P

+11

Rocket is simpler though, we need to maintain two Fenwick trees — one for $$$X$$$ and one for $$$Y$$$, and note that the required difference is the difference between sum of values at locations with $$$x \ge X$$$ and the sum of values at locations with $$$y < Y$$$.

I put in the same effort and I get -216 points. Life is unfair.

You're already an expert, CF has more expectations from you. Just show CF that you can live up to their expectations. Best of luck :)

I wish I had more clarity of mind while implementing problems like C :D

+11

Isn't there anyone who can help me in this problem? The day since I logged in to codeforces I am only getting downvotes. Does it work like this : People who are unable to help, they downvote? I am new to this platform that's why I am asking.

+11

lol people downvote because of 2 things

  1. ratism
  2. the question has been/is already asked / answered before or your post contributes nothing to codeforces.

But it's only 1 downvote, it's not a big deal.

On NM_MehedyIs cerr evil?, 18 hours ago
+11

Great

div3 is a subset of div2

How to solve E?

what is this behavior Mr. panda. you are a gunda of somewhere.

Contest will clash with Roland Garros finals :(

I am my own father! Except during any contest my father goes on a vacation,

What is the source of this problem?

This is such a bad problem for online assessment for job interviews.

I guess recruiters just select some problems from Hackerrank library for job interviews without even checking what the solution requires :P

Bruh, He is not pashka , He is Maxime Vachier Lagrave (FIDE rank 12).

Problem F (my favorite of the contest)

The median of a grid is $$$\leq x$$$ if there are at least $$$\lceil {\frac{a \times b}{2}} \rceil$$$ cells $$$\leq x$$$ in some $$$a \times b$$$ rectangle.

Lets define $$$b_{i, j}$$$ to be $$$1$$$ if $$$a_{i,j} \leq x$$$ and $$$0$$$ otherwise. Now the number of cells with $$$a_{i, j} \leq x$$$ in a rectangle is just the prefix sum of $$$b_{i, j}$$$ for the rectangle.

So we now have a way to check if $$$\text{median} \leq x$$$ for any arbitrary $$$x$$$ in the range in $$$O(n \times m)$$$ time. Clearly if $$$\text{median} \leq x$$$, then $$$\text{median} \leq y$$$ for any $$$x \leq y$$$, so the function $$$median \leq x$$$ for x in the range $$$[1, n \times m]$$$ has the following pattern:

$$$false\text{ }\ldots\text{ }false\text{ }true\text{ }\ldots\text{ }true$$$

So we can just binary search on the first $$$x$$$ where it becomes true.

Code — [submission:119183560]

For problem B my solution tries to perform binary search to find when the derivative flips from negative to positive.

$$$f(x) = \sum\limits_{i=1}^N (x + A_{i} - min(A_{i}, 2x)) = \sum\limits_{i=1}^N (x + A_{i} - \frac{Ai + 2x - abs(A_i - 2x)}{2})$$$

$$$f'(x) = \sum\limits_{i=1}^N \frac{2x - A_i}{abs(2x - Ai)}$$$

Points where we get NaNs because of division by zero are skipped.

Well almost, you need to multiply 0.00005 by 10, because "Random 10 participants outside of top-55...". So that's 0.00005*10 = 0.0005. But I don't think it changes anything)