You are reading too much into it. That, or I am reading not enough into it ¯\_(ツ)_/¯

The authors provided context and how they felt there was nothing they could have done to prevent the unfortunate coincidence. Then, they made their opinion about how unrating the contest might be an overreaction. So they mentioned fact A, then gave their opinion about situation B, doesn’t mean they were using fact A to justify their position on B. Or they did and I’m too ignorant to read through it. Either way, I try not to jump to conclusions.

The quote was about how it was not trivial to find the problem from the contestants’ perspective, it was not about them or their effort to prepare the round. Again, could be just me and you arriving at different conclusions.

It’s pretty clear that this conversation will just devolve to arguing semantics and interpretations, so let’s just agree to disagree.

At no point did the authors bring up their effort as a possible justification for whether to unrate the contest, so him making that point like some kind of gotcha just feels weird and unnecessary to me.

Unfathomably based opinion lol

In fact I think competitive programming platforms should have an option for all participants before each contest that says "I am a pussy and does not actually want to do competitive programming; I am only here for the rating. Therefore, I would like to take the performance of [insert best AI model here] as my own for this contest and relinquish my opportunity to solve the problems and have fun, so that I won't ruin it for other people".

On a more serious note, I think we have enough time to deal with AI before some Stockfish level model happens. In chess, no one really cared about chess engines until they touched the highest level of human play with Deep Blue, even though they cracked Master level more than 2 decades prior. Even now that computer chess far exceeds human abilities, they still fail to produce engines that play "human-like", meaning that cheating in chess is oftentimes painfully obvious. If tomorrow a model that can solve every 3000-rated problem in the world with some 2000 lines monstrosity suddenly appeared, I would marvel at that feat of technology, but I doubt the competitive programming world would be "rocked" or "destroyed" because of it.

My problems are mainly for those who want to solve genuinely, but anyone can feel free to slap their AI model on it. Just like chess puzzles.

I guess there are cases where the original solver also leaks the solution deliberately, in such cases it is fair to punish all of them.

Yeah, his formula for the "expected time" part was missing a factor of $$$\frac{n}{2}$$$ — at every second, each subgame has only $$$\frac{2}{n}$$$ probability of progressing in either direction.

I forgot to mention it in the editorial, but this is exactly my original proposal! That version was a bit too guessable, as the answer is...

So I had to tweak the settings a bit.

This is basically the same as the editorial, without the "how to come up with such function" part. Note that the final function the editorial found is $$$\frac{n}{m} \binom{d_i + 1}{3} = \frac{n}{6m} (d_i^3 - d_i)$$$ (the $$$d_i$$$ part sums to $$$m$$$ and is cancelled out), but I elected not to just chuck in a magic function and call it a day, instead demonstrating how one can work it out for other problems.

For what it's worth, I, the author of problem D, also share the sentiment. That was exactly why I did away with Atcoder contests long before I retire from competitive programming altogether — the process of trying to work out the solution for an hour and spending 3 minutes on coding can sometimes feel disappointing. Then "Why is problem D here?", you may ask. I think it's fair for me to provide some context around the problem:

• It was first proposed seven years ago. You heard that right, it's older than 90% of all Codeforces account, and barely a year younger than Atcoder. Back in the day such brain-teasing problems were nowhere near prevalent as they are now. I never had the chance to use it since my div.2 proposal of 7 years ago didn't go through despite having all problems approved, due to lack of commitment from other authors. When invited by Kuroni to author a contest together, I finally had the chance to publish one of the very first problem I invented on my own. It had a special place in my heart, even though I have grown to dislike problems of its kind.

• During the testing, some testers liked it, some didn't. I expected as much since personally I wasn't the biggest fan of the problem anymore. Its perceived difficulty also went from div.2 B to C and finally D — I felt I massively misevaluated the problem. I wanted to retract the problem and offered to create a new one, but others convinced me to keep it, and no tester, both div.1 and div.2 strength, specifically said they were unhappy with the problem being selected even though some might not like it.

• That being said, I felt having only one single-liner was not the worst thing in the world if I was able to balance other problems around it. I felt A was decent, B was good if a bit tricky for its place, C was very satisfying, G some higher rated people found interesting, and of course Kuroni's problems were all high quality. The only real mistake was problem E, which would have been a way better problem had I found a way to prevent the answer being too guessable (for example, by forcing the number of parts to be odd) — alas, I did not think of it before the contest started.

Regarding the problem itself, while I understand your POV (I have been there in my 3 Atcoder contests before quitting), I still feel such problems deserve their spots in contests — it's unfair to restrict what should be called a programming problem. It saddens me that you attribute the existence of such problems to authors being lazy — at least for me and this particular problem, no, it was as much a labor of love as any of my other problem on Codeforces (and an old one at that!) which I thought would bring diversity to the problemset.

I will never in my life set more than one "Jewel" in a contest though, you have my word on that. This is my first one anyway.

Thanks for your civil discussion :)

Thank you as well for raising the issue — the tutorial has been updated!

Thank you for the suggestion, the tutorial has been updated ❤

Yeah I agree it's not the most intuitive way to prove the correctness. Since we are trying to bound $$$q+r$$$, maybe starting from $$$n - 2(q+r)$$$ would be better? Like this:

$$$n - 2(q+r) = (p_1 - 2)q - r$$$

$$$\geq (p_1 - 2)q - p_1 + 1$$$ (since $$$r \leq p_1 - 1$$$)

$$$\geq (p_1 - 2) - p_1 + 1$$$ (since $$$q \geq 1, p_1 \geq 2$$$)

$$$= -1$$$

Hopefully this helps!

Yeah this is getting frustrating. The $$$60$$$ is there because some constraint needs to be there, it is basic statement writing common sense. And among possible candidates, $$$60$$$ makes the most sense. What about $$$2$$$? No it doesn't work, it fundamentally changes the thinking process of the contestants, making the problem a joke. What about $$$100000$$$? Then we would have 5 test cases per file and the Codeforces server crumbles from thousands of people submitting a problem with 200 tests. What about no constraint whatsoever? Seriously? How in the hell is that even an option? Find me a problem with such output format so that I can enlighten myself please.

It has never been the case that authors have to guarantee the constraints are to guide the contestants to solve the problem. That is not the constraints' purpose. You can base your approach on the constraints, sure, no one forces you not to do that, but it is not and has never been a foolproof plan. There are times it doesn't work. There is no point arguing "trash problem, I could have solved it if this constraint is lowered to $$$2$$$" because they are two entirely different problems.

I am grateful that you are actually suggesting alternatives instead of just jumping into the circlejerk, that's exactly why I have been replying to you. But you have to understand that there are conventions and guidelines we follow that are recommended by experienced and respected authors. I hear your suggestions, but you've got to learn to accept that reinventing the wheel rarely works and it is perfectly normal that I or other authors don't find your suggestions viable or better than the current alternatives. It might be arrogant of me to say this, but setting problems is something one needs to get involved to fully appreciate others' works and be more considerate in voicing criticisms. Please consider it if you are interested; I enjoyed it greatly, maybe you will, too.

Have a good day.

That doesn't work unfortunately. We cannot just say nothing about the constraint on $$$m$$$ and then casually give $$$t \leq 10000$$$. People would start questioning my problemsetting skills and/or sanity if such an experienced setter is apparently asking them to print a billion numbers haha

To your second point, no I would have to disagree. Math has always been part of algorithmic problem solving and will stay this way. If you think I set math problems because I am incapable of doing other topics, please find my other works on Codeforces, Kattis, and VNOJ. I will continue to set math problems and non-math problems, hopefully I have your support on this.

The constraint is there for a reason and it is not to deceive people; see my comment above. It is easy to dish out criticism when you are not in a position to make decisions and take responsibility for them, but asking to minimize number of stalls is not as amazing a solution as you may think, because it has very little to do with the problem nature.

As I said earlier, setting it to $$$60$$$ was to signal that we wanted to accept any solution that doesn't use redundant stalls, which you couldn't do if you asked for minimum number of stalls. You may ask "Why not set it to $$$10^5$$$ stalls then?", to which I would like to point out that making the constraint as small as possible helps us increase the number of test cases in a single test, which makes the testset stronger (fyi us setters follow a guideline that discourages having more than $$$10$$$ pretests on problem D because of huge traffic nowadays).

I have tried my best to make my case. I just want to say we hear and appreciate constructive feedback, and we only hope our voices and addresses to your concerns will not be drowned in a deluge of downvotes — unless you find them unreasonable, in which case I implore you to reply with reason as well.

Ooh I see, idk whether Kuroni still plays but he did hit the highest rank (is it X?) No idea where that would place him tho. Either way the game looks too insane to me, I'm gonna stick with map staring games made for old men :)))))

Kuroni was relatively cracked at std too (I think he was in the Vietnam OWC team that one year?) I used to play every mode, even though I was garbage xdddd

Apparently bro also plays competitive tetr.io which I don't really follow, looks like some kind of tetris with no drop speed?

I think he knows it better than me, considering he was former national #1 in Taiko while I was only former national #4 in Catch (totally not bragging xd)

wy didn't si and had to inspect element (it was at 729)

Should have used the wysi song but we went with songs of different languages so it didn't make the cut

Your last assumption is correct. You can think of it like this: the minigame of "can ball $$$i$$$ survive" involves ball $$$i$$$ and whatever ball right behind it in clockwise order. If at some point ball $$$b_i$$$ is overtaken by some ball $$$j$$$, it doesn't change the minigame's state, just that from that point on, we are concerned about ball $$$j$$$ instead. No matter what ball is behind it, the transition matrix is the same.

Fixed —— some negative signs unexpectedly escaped from the editorial. Thanks for reporting!

lord_vecna dulatcodes FYI

Thanks for the insight. People have polarizing opinion on this problem, but if my problems please a single person, I will continue to make them!

Hopefully you enjoyed other problems, whoever you actually are.

Schmucks. My failure then. I was so close, having tests with exactly $$$2$$$ b's and all :'D

This solution is in fact correct with high probability (if a string can be partitioned, there are at least $$$\frac{n}{3}$$$ such partitions, thus probability of failing is $$$\leq \frac{2}{3}^{100}$$$), so it's not exactly dumb. Congrats on the AC!

We didn't want people to guess the solution; also there might have been other solutions we are not aware of that uses more than $$$2$$$ and we want to accept all of them (note that performing $$$x \mod y$$$ always decreases $$$x$$$ by at least $$$2$$$ times, so any solution that doesn't use redundant stalls should always pass this constraint).

The rough idea is this: the game ends when some ball $$$i$$$ becomes the last ball standing by taking over ball $$$i-1$$$. Obviously only one such event can happen, thus the answer is probability that ball i overtakes ball i-1 $$$\times$$$ expected time ball i overtakes ball i-1 assuming it does happen. Let $$$d_i$$$ be the distance between ball $$$i-1$$$ and ball $$$i$$$, the first factor equals to $$$\frac{d_i}{m}$$$ (see Gambler's Ruin). The second factor equals to $$$\frac{n}{2}\frac{m^2 - d_i^2}{3}$$$ (the $$$\frac{n}{2}$$$ comes from the fact that each subgame has $$$\frac{n-2}{n}$$$ probability of not progressing each second).

Glad you liked it!

Here's the lore for the problem:

One day I randomly thought about problem A from this legendary TMW video and wondered "how could I make this problem more interesting"? Then I came up with adding the tax (note that the original only has $$$m=1$$$ so adding the tax only increases the answer by $$$\frac{k(k+1)}{2}$$$, the greedy obviously still works). Then I realized allowing to buy $$$m$$$ items per day doesn't change the strategy as well! (I then tried to have different limit for different days but it obviously didn't work)

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

Yeah honestly I'm still tripping myself over that comment to this day. What does he mean by "for all problems of this kind"? From my understanding maybe he means if we describe state $$$S$$$ as a sequence $$$(s_{1..n})$$$ then we can just use the potential function trick. But surely there's gotta be some additional conditions on the transitions $$$S \rightarrow S'$$$ right? How can we be sure that solving for potential functions actually gives a solution when there are a lot more equations than variables?

uoooh cuni

As the author of at least 1 problem, hi! (updoot on the right)

Sharm is located at the Sinai Peninsula, right next to Israel and the Gaza Strip. Luxor is inland, 500km from the border so I guess there should be fewer security concerns.

Not sure about traveling plans though, most people will have to transit twice which is not ideal :/

Also unrelated but lots of good stuff to see around Luxor if you are into archaeology, like the Valley of the Kings (where many Pharaohs are buried, notably Ramesses) or the Luxor Temple

Pretty sure this does not work because unlike $$$\sum_{x = 0}^{n} x^{k}$$$, the result of this sum $$$\sum_{x = 0}^{n} F^{k}(x)$$$ is not a polynomial of any degree. Even when $$$k = 1$$$ it is well known that $$$\sum_{x = 0}^{n} F(x) = F(n + 2) - 1$$$ is not a polynomial. Unless there is some generalization of Lagrange interpolation that I am not aware of, I don't think it's possible to solve it this way (would love to be proven wrong!)

We agree to disagree; personally I don't see any issue with upvoting his comment once he already corrected himself. I upvoted him to appreciate his efforts to help me understand the solution more thoroughly and I give other upvoters the benefit of the doubt, but I see where you are coming from.

Agreed, though I don't think it is relevant to my comment. Newbies getting downvoted is a real issue — just a completely different one. My point is, calling out a comment that adds to the discussion like this is just weird.

I think this comment is the perfect example that people are not seeing and using upvotes/downvotes the way they are intended to be. If I think a comment contributes positively to the discussion even if it is incorrect, I will still upvote it, especially after the poster acknowledged and corrected the mistake. Of course there are some upvotes that didn't go beyond "me see red, me updoot" but it's an irreversible action and I don't find any reason for anyone to downvote such a healthy discussion.

Because it has not been decided yet, those who organize the training camp do not have the final say, and it's better to let him compete just in case he's eligible?

This is not the first time such a decision is made, nor will it be the last. The most famous case is probably tmwilliamlin168, who, despite being a Taiwanese citizen, was disallowed to compete by Taiwan and went on to win IOI with team USA.

Nguyen moment

Now kiss

As an author of Round 666, I just want to say that right now I have exactly 666 friends on Codeforces!

Edit: Wow, it lasted a whole 3 minutes! Now I have 667...

Well, it might be the case that size_t — the type of vector::size() is defined to be int or long long on your machine. But I'm sure that it is unsigned on Codeforces. Your solution crashes when I run it on Codeforces Custom Invocation. The "TLE" verdict is because extra.size() - 1 is evaluated to be $$$2^{32} - 1$$$, not because of slow performance.

Anyway, try to keep that in mind and remember to cast the type to int or long long to avoid those situations.

Reason: Line 469, you used the macro

fortob(0, extra.size())

Which, from line 23, is equivalent to

fornb(j, 0, extra.size())

Which, from line 19, is equivalent to

forlb(j, 0, extra.size(), -1)

Which, from line 17, is equivalent to

for(int63 name = extra.size() - 1; name >= 0; name += -1)

Since extra.size() is of type unsigned int, your code crashes when it is equal to 0.

REAL reason: Your macro sucks massive huge enormous balls. Consider scrapping it for the sake of debuggability :-s

Yeah I mean people also expect each other to not tell a dick joke at the funeral, even if it's not written in the rules, and will be upset (rightfully so) if one does.

But fair point I guess. Sorry for the bad analogy.

FYI, here is a screenshot taken from Polygon:

As you can see, the system does warn about pretests being incomplete. In fact, if you insist on trying to nitpick things, the test with $$$t=500000$$$ and $$$n=1, m=1$$$ for each case also gives the maximum input size possible (about $$$1$$$ million more integers to read), therefore it should be included in the pretest (this is rather redundant, since the third quote already pointed that out anyway).

I did not know how long it takes for Codeforces to process that amount of flushes. I used flushes to debug my solution locally, and forgot about it. I submitted the solution, saw that it passed within 1/3 of the time limit, and was completely convinced that it would not be that big of a problem.

I didn't say that I deserved to pass using 500000 flushes; however, if such tests were present in the pretest, I would have known immediately what the issue was.

For the "imaginary policy" part, feel free to enlighten yourself. Some quotes taken from the document:

• Always make tests (at least) with minimum possible, maximum possible and some value in between for each variable and their combinations.

• In general, pretests should include: a test with maximum size of input (e.g. maximum n), a test against integer overflow, a few random small tests.

• There should be no warnings in polygon, except (if reasonable) "there are tests with input/output for statements [without TeX marks]". ("parameter 't' does not hit maximal value" is one such warning).

I have involved in preparing some Codeforces rounds, I know what I am talking about. I don't pull facts out of my ass. Have a nice day.

Okay, I will say it. The pretest for Div1 C is fucking garbage.

I passed pretests using only 580ms. The time limit is 2s. My solution is deterministic, and runs in basically the same time given that the input size is fixed.

It got TLE on test 72.

I then changed from cout << ans << endl; to cout << ans << '\n';. It now runs in 800ms.

It means that it takes at least 1.2s to flush 500000 times, which implies there is no such test where $$$t = 500000$$$ in the pretest (I really doubt the maximum $$$t$$$ in the pretest is even close). Now I'm pretty sure that Codeforces has the policy on problems that the pretest must satisfy i) it contains all corner cases on which some known solution fails and ii) all parameters specified in the problem must hit their respective maximal values. With that knowledge, I put my trust in the problem setters that they have at least complied with the policy and believed that Codeforces actually could handle 500000 flushes better than I thought. Turned out I was wrong on both, LOL.

It would be really great if anyone involved can explain the thought process (or lack thereof) behind the decision not to put such tests in the pretest.

Problem C: The Empty Box and Zeroth Maria

Petition to refer MikeMirzayanov as Mike "Don't call me Mike MikeMirzayanov Mirzayanov" Mirzayanov.

In no particular order:

Codeforces:

• 1142C — U2

• 1178E — Archaeology

• 1208F — Bits And Pieces

• 1254C — Point Ordering

• Honorable mention: My first Div1E problem :)

OpenCup: (not public)

• GP of Baltic Sea problem A

• GP of Poland problem L (also available as AMPPZ 2019)

• GP of Moscow problem M

Other ICPC problems:

• Jakarta Regional problem D

• CCPC Qinhuangdao problem K

• KAIST RUN Spring problem D

• KAIST RUN Spring problem H

• NAIPC problem G

• Taipei Regional problem F

• Honorable mentions: Many workshop problems I cannot share

Yeah, what you are describing is what I want to avoid as well. What I meant was that I want contestants to try to solve the full problem first, then if they a) cannot come up with anything or b) don't have enough time left, they can switch to the easier one, not the other way around. Maybe this clarifies the "make people feel less shitty" part.

Again, I'm not saying that this method is perfect, but it has shown from time to time that it can be very efficient if done correctly.

Thanks for the info, I'll definitely consider it the next time I set a subtask (if there's any).

Your solution was quite different from ours, I didn't take that case into account, sorry haha :)

I think this subtask would've been fine for div2 only.

Good point. I don't think it has ever been done yet, but it's indeed an interesting idea.

Unless there really is a fairly hard halfway step where a subtask would be useful.

So far, my take on subtasks in Codeforces, besides it being a great help to manage difficulty span, has always been "a consolation prize to make people who couldn't solve the full problem feel less shitty" rather than "a suggestion to solve the full problem". Maybe it's just preferences, and in certain cases it might help, but for me solving Div1 E is itself an achievement, and I don't want to make it easy for people :)

Sorry in advance if my wording choice was weird. I'm half asleep right now xD

I am the author of problems B1 and B2 in Codeforces Round #601 (Div 1), so I will try to play the devil's advocate here.

In my viewpoint, B1 as a problem is much easier than B2, as you don't need the core observation (one step is equivalent to increasing/decreasing the prefix sum) to solve B1. That's one of the reasons why we decided to make B1 worth so little; the other reason is to discourage people from solving B1 first. And I am quite sure it worked: most people who tried to solve B1 first gained zero (even negative) advantage compared to those who didn't. All they got is an insurance that their round would not end up being a disaster just because they missed that one observation to solve B.

So you may ask, why did I prepare subtasks for B in the first place? Well, at first, I also thought that this problem would fit nicely as Div1 B. Our testers didn't really agree with me though:

Only one of them solved it in their first submission (the other one is upsolved), which made me question myself. "Was this problem all cute and nice as I thought?". "What if the observation was actually hard to spot (thankfully it was not the case), would contestants enjoy my problem and the contest as a whole as much as I'd love them to?". Now, I won't try to convince you that this is the only method in the world to deal with difficulty spikes in contests. However, in this particular case, having B1 (also E1 in Division 2) as a subtask solved my concern with (subjectively) minimal side effect. I'm quite sure that the idea introduced in B1, while classic, is still new and interesting enough for many contestants here.

As for subtasks in Codeforces in general, I don't think it's necessarily a bad idea. Is it overused? Quite a bit, and I'm sorry for joining the trend. Is it evil? No. Not trying to make your contest as enjoyable as possible is evil. That being said, we can improve the subtasks by:

• using it only if the potential imbalance may happen in easier problems (in general, having subtasks in Div1 D or E is bad; they are meant to be hard),

• making the easy version worth as little as possible (but still worth the effort),

• not spamming it.

As I really want to get involved with creating contests, I'd love to hear appreciate constructive comments on this issue.

It was fixed, thank you!

https://codeforces.me/blog/entry/71534?#comment-559020

It indeed is not :) how do you feel about today's interactive problem?

Trust me, by that time Vietnam would have the game in their bag anyway, so please join our contest! :)

This is indeed a good question. However, nobody can answer your question I'm afraid, not contestants, not coaches, not contest organizers, not even RCDs.

Maybe not even the man himself (if he can then he should have done that 10 years ago).

Fortunately, this is likely the last year we have to endure this shitty corrupted ambiguous rule. There will be a PSP final next year. Or maybe the man will find another way to qualify teams he likes that will end up solving zero problems in the WF, who knows.

We joined the equivalent positions as follows: create $$$2n$$$ vertices, each position $$$0 \leq i \lt n$$$ is assigned $$$2$$$ vertices $$$i$$$ and $$$Mirror(i) = 2n - 1 - i$$$. Then if $$$l..r$$$ is a palindrome, we join $$$l$$$ with $$$Mirror(r)$$$, $$$l+1$$$ with $$$Mirror(r-1)$$$ and so on. This way we have a bunch of queries of the form "join $$$a+i$$$ with $$$b+i$$$ for all $$$0 \leq i \lt k$$$", and have to report the connected components.

To do that, we used modified DSU. First decompose the queries into $$$2$$$ parts so that each of them has length of the form $$$2^k$$$ (as in Sparse Table). Then go from large $$$k$$$ to $$$0$$$. If vertices $$$u$$$ and $$$v$$$ are connected at step $$$k+1$$$, then we join vertices $$$u + 2^k$$$ and $$$v + 2^k$$$ at step $$$k$$$. This is equivalent to joining $$$u + 2^k$$$ and $$$root(u) + 2^k$$$ for each u. After that, for each query $$$(a, b, 2^k)$$$ we join $$$a$$$ and $$$b$$$.

Oh wow, daily reminder that I'm actually getting dumber as years pass...

Can problem I be solved faster than $$$O(n*log(n))$$$? Our solution got TLEd and we had to make shitty constant optimizations...

I am aware that our solution involved duplicating the string, so I'd also be glad to know if it can be done without doing that.

L: The center's coordinates $$$(a, b)$$$ must be the average $$$x$$$ and $$$y$$$ coordinate of all points, respectively. Also, the outer radius $$$r$$$ will be $$$max(x_i) - a$$$. Knowing $$$r$$$ and $$$n$$$ we can deduce the inner radius $$$l$$$ by pre-computing $$$count[x]$$$ = number of lattice points in a circle of radius $$$x$$$. Now we have to check if the donut $$$(a, b, l, r)$$$ matches the current set of points. To do that, one can assign point $$$(x, y)$$$ a value of $$$p^{x}*q^{y}$$$ for some $$$p, q$$$ and maintain the sum modulo some big prime. Note that translating the center from $$$(0, 0)$$$ to $$$(a, b)$$$ multiplies the value by $$$p^{a}*q^{b}$$$, so to get the value of a certain donut one can also pre-compute the values of each circle of radius $$$x$$$.

Oi, let me have some chance to qualify, don't you? ><

IIRC the last two Thailand Regional contests were hosted in Nakhon Pathom by ICT Mahidol and it went smoothly (no stupid shenanigans or technical fuck-ups). I did not recall any complaint about the 2016 contest either (hosted by Chulalongkorn, also the host in 2014 and this year). So I'm very surprised they decided to go back from being one of the better regional contests to this.

Sucks that there are a lot of strong teams competing in Bangkok this year (Tokyo, Seoul, NTU Taiwan, NUS just to name a few). They don't deserve this.

The more important question: Is I_love_Hoang_Yen Hoang Yen?

Good to know I'm not alone xD

Yes, the problems' names of the Div2 contest are the same

Fact: If $$$f(x)$$$ is a polynomial with degree $$$n$$$ then $$$f_{1}(x) = f(x + a) - f(x)$$$ (with any constant $$$a$$$) is a polynomial with degree $$$n-1$$$. If we define $$$f_{k}(x) = f_{k-1}(x + a) - f_{k-1}(x)$$$ then $$$f_{n}(x)$$$ will be a non-zero constant and $$$f_{n+1}(x) = 0$$$. The converse is also true. Therefore you can ask integers of form $$$b+at$$$ with some random constants $$$a$$$, $$$b$$$ and compute values of $$$f_{k}(x)$$$ accordingly. As soon as we find out $$$f_{k}(b) = f_{k}(b+a) = 0$$$ we can determine with high probability that $$$f(x)$$$ is of degree $$$k+1$$$.

We took the vertex with the lowest degree (don't care about its component) and got AC. Seems like the judges want to make people happy and let everyone pass :D

At least 3 persons on my friend list who got F accepted fail this test:

3
2 4 2

Please look into this.

Oh, the sentence was not there when I commented, thank you for pointing out :)

In problem "split", it isn't always possible is it? Do we have to determine whether it is possible as well?

Needs more coke spilling

Nice solution! Actually you can solve for all $$$n$$$ up to $$$k(m+1)$$$ using DP in $$$O(k^2 * m * 2^m)$$$, so this problem can be done for even larger constraints (e.g. $$$k \le 100, m \le 10$$$) than I expected.

Well, this problem was still WIP by the time it was chosen (because something unexpected happened), so I did expect that I may have missed better solutions. But my unfinished idea was very close to this one, so I'm pretty "salty" now :D

The idea of making Div2C = Div1A did wonders when the Div1 cutoff was 1700 — the average skill of Div1 was much lower back then, so it's OK for Div1B to be easy. Right now it's very hard to set a balanced problemset for both divisions this way. The last 5+ Div1+Div2 rounds had either (or both) of them consist of 6 problems, so that the average blue will solve 3-4.

This round's Div1B was not imbalanced, it's just that Div2 people are too used to have 6 problems, therefore Div1B is supposed to be Div2E. I think it'd be better to just make every Div2 contests have 6 problems, and share 3 problems with Div1 (or even 2, hardly anyone solves Div1C anyway).

The solution does not use any min/max operations, only additions, so it works fine.

If you insist on using the standard (take max) solution, comparing them using big integer is the correct way, but you can pass just by using modulo because there's (unsurprisingly) no $$$n \le 1000$$$ such that your solution fails (read my other reply).

The graph needs to be connected as well (if you don't count isolated vertices).

For a rough intuition of why there was no counter-test against your second solution, you can read this comment.

To be fair, we could have killed such solutions if we wanted to, by deliberately choosing a modulo that makes those solutions fail, or including the modulo in the input. But then again it will be unfair because there might be other implementations we are unaware of that avoid this specific counter-test, but fail on other tests.

A close analogy to this situation is: Should we include a test that kills a hash function with modulo $$$10^9 + 7$$$ and base $$$31$$$ just because we can?

No, we do allow to make moves beyond 504, and our solution handles that.

The idea is to insert the planets in decreasing order into the path; it is possible that we first insert 508, then insert 504 before 508, then 500 before 504, which gives the path 500-504-508.

Sorry if any part of the solution confuses you. Hope this clears.

That was quite unlucky :(

However, by any chance, did you misread the condition of constant $$$l$$$ on problem J? As $$$l$$$ must be a positive integer, it's not very hard to come up with a solution that uses only integer arithmetic. The implementation wasn't that error-prone either.

Is chemthan hacked?

Yes, but he regained access to his account.

The blog is now deleted.

chemthan requested to disable his temporary alt, therefore the blog is removed.

Source: I am his friend (trust me reds tell no lie).

We still don't know who hacked him yet, but it is likely that they are not Vietnamese, as we all got PMs in English.

Also chemthan when you see it pls accept my FB friend request :(

Our team has an O(2ⁿ * n²) solution:

For each pair of rows i < j, calculate c[i][j] as follows: its k^th bit is on if and only if a[i][k] < a[j][k]. Build a graph where vertex i has an edge to vertex j with color c[i][j]. Now if we choose all the columns, then the number of monotonic rows is equal to the number of monochromatic paths in the graph. Similarly, if we choose a mask msk of columns, then the color of edge will be c[i][j] & msk. For each value of msk we can do this easily in O(n²).

Hopcroft Karp algorithm runs in

Already did but my assertion assert(ntest > 0); fails, which likely means the judge has no input.

I tried but it says "404 page not found"...

Can I submit this problem somewhere? It seems the ICPC Live Archive doesn't have any input (my assertion assert(ntest > 0) failed).

I can't think of an Segment Tree solution so here goes my shitty sqrt one:

I had an O(N² + CYlog(Y)) solution, where C = N - M is the number of connected components, which involves C fast polynomial multiplications. But when I submitted my "brute" solution using naive multiplication just to ensure correctness, it magically runs in 2.6 seconds :o So I didn't have to implement FFT. You can read my code here, it's quite easy to understand.

gaypride

2

6 7

Uh, that's because their Codeforces handles (and therefore their names) are not updated. Are they the same team as last year?

Also we may need to see the team's actual performances in the Workshops. TBH I didn't know much about SJTU 2018 team before MW.

You will get it once you achieve something other than trolling for fake internet attention haha cheers ;)

Found a perfect place for you to meet people of your kind :o

Wow what the fuck is wrong with those people bashing the authors for including anti rand() tests in pretest? If they weren't kind enough to make those pretests for you then surely someone would hack you in like 5 minutes. Do you guys seriously expect the authors to publicly announce Hurr durr just saying rand() is weak you should not use that but this problem is definitely not about random?

Maybe next time try to actually appreciate the knowledge you gained in contests.

We had the same idea, you would be a bit disappointed looking at our solution though...

bool win(int x, int y) {
	int cnt = 0;
	For(i,1,n) if (pos[x][i] < pos[y][i]) ++cnt;
	return cnt >= (n + 1) / 2;
}

int id[maxn];

void process() {
	For(i,1,k) id[i] = i;
	sort(id + 1, id + 1 + k, win);
	For(i,1,p) cout << id[i] << " ";
}

1. MSU

2. U Tokyo

3. MIT

4. Warsaw

5. MIPT

6. Cambridge (actually beat Oxford last NWERC)

7. Peking (it feels wrong not to include any Chinese team here)

8. ITMO

9. Oxford (can't wait to see another post from our boy after getting another bronze)

10. KAIST

11. CUHK (or some unexpected team)

12. Kim Chaek UT (because why not)

13. (but still gets a medal) UWaterloo (as is tradition)

14. (but still gets a medal because reasons) Ural FU

National University of Singapore: sidhant btzy bayweiheng

Hanoi University of Science and Technology: Quang ladpro98 Boros_

University of Engineering and Technology — VNU: dthangnguyen19 lazyc97 Slumdog

Our university is free to choose which team will go to WF among those who have already qualified. In NEERC you cannot have multiple qualifying teams, as NEERC acts as one super-regional and no one other than the top team from the university could qualify. In NEERC, if you don't want to go to WF then you are blocking all other teams from your university, while in Asia we are still sending another legitimate team.

Yea we are extremely worried that Um_nik's team may actually steal our certain victory on their best day /s

On a more serious note (not for you Lance), no, this is completely personal. Every year WF welcomes a set of many strong teams; changing the attending year won't have much effect if you don't improve, whatever your goal is.

Also I don't want to retire after just 2 years QQ