bump: the contest will start in 24 hours!

You're right, fixed

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

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

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

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

Wow, this proof is really smart. Thanks for sharing!

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

https://codeforces.me/blog/entry/82500?#comment-694826

Thank you for the round! I love each of Div.1 ABCD.

A1 is the same as ARC086B, but this is not an issue. (that's why I had first solve :D

I am not a fan of 1E: I think at least hacks should be disabled for this kind of unproved/unverified problem (and maybe specify that pretests = tests).

As a tester, I recommend participation

So hard

I is the same as https://ac.nowcoder.com/acm/contest/9328/B

As the 7th place, congratulations and good luck!

As a cyan tester, I recommend partipating

When I open my submission for Bribing Friends in Gold, it show a blank page: http://usaco.org/current/viewsource.php?sid=4318354 Is this intended? (my other submissions are all shown correctly)

As a tester, problems are good and I recommend participating

I know that in some year's (edit:2017) Chinese IOI Training Essays, there exists a paper that claims "PAM can support arbitary pushfront pushback popfront popback operations in complexity same with only pushfront pushback". (However I have never seen an implementation of it) So I guess it indeed can be solved in less complexity.

How to solve H:

• Remember that in https://ac.nowcoder.com/acm/contest/33189/F you have PAM with both-side insertions and undo.
• Remember that in https://uoj.ac/problem/693 you have a "two pointers with one stack".
• Merge the codes (this is quite disgusting actually)
• AC

I have no idea whether my solution to sets is right, but it did get 100 points.

First $$$O(n^3)$$$ dp is trivial: let $$$f(l,r)$$$ be whether you can erase everything in range $$$[l,r]$$$.

Note that

• only when the xor sum of $$$[l,r]$$$ is 0, $$$f(l,r)$$$ might be 1.
• The transitions look like enumerate $$$k$$$ and then check if both $$$[l,k],[k+1,r]$$$ can be erased. When doing so, use an array to store all $$$k$$$ such that $$$f(l,k)=1$$$ and only try those $$$k$$$-s.
• if now $$$f(l,r)=1$$$, break; immediately.

With the two optimizations, it passes $$$n=10^4$$$ in 0.3 seconds.

F is so annoying to implement (256MB memory limit makes it even worse!). But D and E are interesting.

I solved it by directly simulating what is written in the statement with digit dp. This gives a $$$O(2^{12}n)$$$ solution, which actually can pass.

Why not unrated?

The name seems complexed, but the checking algorithm is actually very simple: if a vertex has exactly one incoming edge (from $$$x$$$) and exactly one outgoing edge (to $$$y$$$), remove the vertex and link an edge from $$$x$$$ to $$$y$$$. Keep simulating this process until only $$$1$$$ and $$$n$$$ are left.

I learned about the algorithm beforehand so I'm not sure, but it seems not impossible to come up with it independently (?)

C: For an edge $$$(x,y,w)$$$, if $$$dis(1,x)+w=dis(1,y)$$$ and $$$dis(x,n)=w+dis(y,n)$$$ call it useful. If we can pass any unuseful edge in our route, the answer is 1, and it's trivial to check.

If we only pass through useful edges, the answer is 1 iff we can pass an edge backwards. After drawing several cases, it is not hard to discover that we should just check if the useful edges form a Two-Terminal Series-Parallel Graph, where terminals are $$$1$$$ and $$$n$$$.

I think the idea is exactly the same as 1667D - Edge Elimination

The pretests make my own implementation run in $$$\Theta(n^2)$$$, but it turns out that some implementations are smarter and need other tests to break. We are sorry :(

This problem was originally proposed as 1B, but after some changes it ended up as E.

We tried to replace it, but we couldn't find any suitable problem :(

I'm really sorry if you find standard.

I solved E with a simple greedy. Can anyone hack me or prove it?

Our goal is to choose a subset that does not change the answer.

Let $$$g$$$ be the final answer. For each prime factor $$$p$$$ of $$$g$$$, it suffices to choose two elements $$$x,y$$$ that $$$f_p(x),f_p(y)$$$ are the smallest and second smallest. (definition of $$$f_p$$$ is same as editorial)

Now we have a set $$$S$$$, but the gcd of pairwise products in $$$S$$$ still might not be $$$g$$$. Let the reduntant prime factors of $$$g$$$ be $$$[p_i]$$$. For each $$$p\in [p_i]$$$, we need to choose two more elements $$$x,y$$$ that $$$f_p(x),f_p(y)$$$ are $$$0$$$.

This directly passes. However I can't prove that it will never take more than $$$14$$$ elements. https://codeforces.me/contest/1687/submission/159458664

upd: hacked

Actually, 1028E - Restore Array is strictly harder than both problems.

My solution to C require no casework (though I don't know if I will FST)

Sort each row and check if there are at most 2 columns that differ. And if there are such 2 columns we try swapping them.

Wow, I made the last "pretests passed" submission in the whole Div.1 round, at 01:59:46.

My heart was beating soooo fast!

As a 2800-rated on CF, I have never solved any C of AGC during contest.

upd: This time I went for D. I think editorial of D is not detailed enough :( I have come up with everything in the editorial during the contest, but failed to find an $$$O(d^3)$$$ per testcase solution with it (My solution runs in $$$O(d^4\log n)$$$)

This round is toooooo hard!!!!!!!!!!

I really miss the old days when ARC's hard problems are not always modulo $$$998244353$$$ problems!

Testdata for E was somewhat a little weak, I passed with parrel binary search with some optimizations. In the actual testdata it took no more than $$$500$$$ queries to find the answer.

Can anyone hack me?

another problem: ARC108F

One very surprising problem that seems unrelated, but actually uses diameter: 1617E - Christmas Chocolates

didn't solve C :(

However I really like this kind of easy problems that high rated users might stuck on!

Totally agree!!!

Thanks for such brilliant E! I was shocked by its beauty when I opened the editorial.

I applied the exact same idea and passed, I don't think parallel binary search is needed.

Why is time limit for D1D so tight? My solution is $$$O(n2^m)$$$ but it runs for 1500ms even after optimizations, but some people's $$$O(n^2/w)$$$ solution runs under 500ms.

Another fun fact: I gave a problem using exactly the same idea as E in a Chinese OJ contest in Feburary 18th. However I lacked time so I didn't pass E :(

1583F - Defender of Childhood Dreams

1542B - Plus and Multiply

1534F2 - Falling Sand (Hard Version)

ARC121D — 1 or 2

AGC056C — 01 Balanced

Why is there no obvious corner cases in D's pretests?

I have an $$$O(n\log^3 n)$$$ solution for D1D which sadly I wasn't able to debug during contest because of wasting time on A:

Just use segtrees to optimize calculating $$$f(n,K)$$$. Precalculate $$$g(n,k)$$$ which is the number of $$$l$$$s such that $$$gcd(n,l)=k$$$, and mainting a segtree with range add and range minimum. When we encounter $$$n$$$, we insert $$$f(n-1,k-1)$$$ into segtree, and go over all $$$n$$$'s divisors $$$d$$$ and add $$$[1,d]$$$ by $$$g(n,d)$$$.

Problems are great, but I personally think the duration is a bit short, especially for data structure problems like H. Sadly I wasn't able to debug my code in time :(

more sadly, I succeeded in debugging it 10 minutes after the contest ended :(

I now feel so lucky to accidentally pass d1b without FST during contest!!!

By chance, I submitted my solution in C++14 and it passed systests in 1903ms. Before I submitted it, I added a small optimization which seemed quite useless: cut off states with $$$k \gt n-m+1$$$. It didn't make my solution run faster on samples.

After the contest, I submitted three more times:

• Just switching the language to C++17(64): TLE on test 33.
• Deleting that optimization: TLE on test 31.
• Submitting the exact solution in contest again: TLE on test 43 (hack).

Overall, if (I submitted in another language/I didn't add the optimization/the tests were a bit stronger) I would have FSTed! How lucky I was!

My randomized greedy solution during contest got WA on test 133. I optimized it for a little and it passed all tests now. Can anyone hack me?

Can anyone provide some information about solving min cost flow with Dijkstra (is there a way to get rid of negative edges)? I have never seen anything about it...

What a dumbhead I am, my D's solution is equivalent to the standard one if all $$$a_i \gt 0$$$, and is wrong otherwise. But my stress test data generator only generated data with $$$a_i \gt 0$$$ so I couldn't find the mistake!

Wow, I feel so lucky to get the first place! I recently came across a problem very similar to F, which I think might be the reason.

Yes, that's what I did in the contest. I really think it's a good problem, but the limit seems quite tight. I douted whether it would pass before submitting (it passed though).

In D1B, I wrote int posa[500005],posb[500005] and used $$$posa[a_i],posb[b_i]$$$. However $$$a_i,b_i$$$ might be $$$10^6$$$! Despite this fact, this program with too small array bounds passed pretests. I really wonder how strong pretests are.

As a tester, I want contribution!

The problems are fun and interesting, so don't forget to participate!

I'm a Chinese, I love my country, but I downvoted every comment here. (Including yours)

This person is definitely wrong. But he has received enough downvotes so most people here aren't really racialists, which means that there is no need to stress it again (someone already said that, why say it again?).

Posting angry words in some old post just because you saw someone saying bad things about China and also calling others to attack him is just online bullying — I don't think what you did leaves others a good impression on China.

China's positive international profile isn't created by posting angry and belligerent posts on Codeforces (a CP site!), but by hard work of all Chinese people.

I became red in the round and I'm so happy!!!

But I have to say I didn't like D very much — its Mo's algorithm on tree solution require not much thinking but the limits were quite tight. My first solution ran for 4960ms and I was afraid that it would fail system tests so I resubmitted after optimizing constant factors (making me rank 70 -> 150) but it turned out that the pretests were just all system tests.

Huge thanks to ABCs for letting me become sooooooo aware of floating point errors! I was never so afraid of them before.

1406A - Subset Mex is a special case (k=2) for B, but the solutions are rather similar.

• 1458C - Latin Square
• 1446D1 - Frequency Problem (Easy Version)
• 1408F - Two Different
• 1404C - Fixed Point Removal
• 1338D - Nested Rubber Bands
• 1344C - Quantifier Question

This contest makes me know that you should never give up halfway during a contest! Last night it was 0:30 a.m. here and I really wanted to quit the contest and sleep, but I didn't. And I managed to come up with the solution to C in the last 10 minutes, successfully implemented it in about 5 minutes and got AC! And finally I became international master ;)

Totally agree!!! With 30 minutes I would likely succeed debugging my C... (or find out that my solution is wrong)

D1A is very similar to 1406D (which was in my contest)

So many people got FST in D1C...

https://codeforces.ml/blog/entry/84056?#comment-714979

My solution for F requires little thinking. (and little coding time since I wrote a similar code before and copied it...)

Just move $$$r$$$ from $$$1$$$ to $$$n$$$. Let $$$f_i$$$ be the answer for segment $$$[i,r]$$$.

If $$$a_r=0$$$, we don't do anything. (just add the sum of all $$$f$$$ to $$$ans$$$) Otherwise, let $$$lst$$$ be the minimum number that $$$a_{lst}\sim a_r$$$ are all $$$1$$$. Add $$$f_lst \sim f_r$$$ by $$$1$$$, and make $$$f_{1} \sim f_{lst-1}$$$ be the maximum one of themselves and $$$r-lst+1$$$.

Use a segment tree with lazy tags to handle range add and range chkmax. There's a well-known trick on maintaining the sum: maintain the number of minimums in the segment, the minimum in the segment and the second minimum in the segment. If the segment's minimum is greater than $$$k$$$ ($$$k$$$ is $$$r-lst+1$$$) then quit. If the minimum $$$x$$$ and the second minimum $$$y$$$ satisfy $$$x \lt k\le y$$$ then change the minimum and the count. Else brute force into its left and right sons. The upper bound of complexity is proved to be $$$O(n\log^2 n)$$$. (I don't know the exact complexity though)

Thanks a lot for answering.

Maybe isaf27 should check the solutions on Polygon?

My solution is $$$O(nm\log n)$$$ with huge constant factors (because I used unnecesary multisets).

The reason I passed D in contest may be the small optimization: If two robbers' position $$$(a,b),(c,d)$$$ satisfy $$$a\le c,b\le d$$$ then $$$(c,d)$$$ surely won't effect the answer. For the searchlights if two $$$(a,b),(c,d)$$$ satisfy $$$a\le c,b\le d$$$ then $$$(a,b)$$$ can be deleted. After the deleting, the real number of $$$n$$$ and $$$m$$$ become so small that I passed in only 60ms.

(fixed a typo)

The system test is a little bit weak. I hacked myself in D after the contest.

I made such a big mistake in A (mixing the odd and the even indices) and my solution amazingly passed all pretests!

fixed

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

Really sorry for problem B. Still we hope you have enjoyed this contest.

Sorry for the problem being well-known. None of the testers knew this problem before. (In fact B used to be exactly the same as abc173e, but to make it easier we chose k=5). We're really sorry for it.

We're very sorry. But please, still enjoy the contest.

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

fixed, thanks for pointing out

No.

They are written, but not published.

OK, added a sentence

I think it is already highlighted.

I'm also wondering if it's dp or greedy (just can't solve it..)

Rank12! It's the highest rank I've ever had.

I think it's because on Codeforces, O2 is always turned on.

On my computer, if I choose O2, it seems that the complexity has been optimized to $O(1)$。

Finally become master in this round. I like the problems! Thanks a lot.

So can we still hack in this round?