doreshnikov's blog

By doreshnikov, 6 months ago, translation,

Hello everyone!

I thought that maybe someone on Codeforces can help me find an error or build a counterexample. If you remember matchings in non-bipartite graphs, then the problem with Kuhn's algorithm is as follows: we need to find an augmenting path, but we can arrive at the desired vertex via an edge of the wrong type, mark it as visited, and leave.

1. First attempt to solve the problem: do a dfs on vertices of the form (v, flag), where flag is the type of edge we arrived by. Obviously, this doesn't work: we can go through both (v, false) and (v, true) because they are different vertices, but then our augmenting path in the original graph is not simple, and we haven't actually found an augmenting path.

2. Second attempt to solve the problem: do the same thing as before, but explicitly forbid dfs to go to vertices that have already been visited (are on the path from the start to the current vertex), even if they were visited with a different flag. Something like this:

vis[v, flag] <- false for each v, flag
path = []

dfs(v, flag):
vis[v, flag] = true
path.add(v)

for u : g[v], such that (status[vu] != flag) && (u not in path) && (not vis[u, !flag]):
dfs(u, !flag)

path.pop()


Since people write Blossom algorithm, and I'm probably not smarter than Edmonds, who came up with it, there is either a counterexample to my “solution” or it just takes a long time, but I haven't yet realized why. I hope that there are smart people out there who will somehow see this post and explain to me where I'm wrong :)

• +58

By doreshnikov, history, 23 months ago,

Short information

Sorry for another delayed editorial, I know I promised that it will come out sooner the previous time, but I wasn't feeling well today, so the work was slower than usual.

About problem F:

I am once again sorry for the inconveniences caused by tight ML in this problem. It was not the intended behavior since we relied too much on the main solution and didn't assume most of the solutions using DFS will fail. In this editorial I attach the code of the main solution that we expected from the beginning, it uses ~75MB of memory.

I guess, Div. 3 Rounds are not only for participants to learn but also can serve as educational for authors as well. I'll try not to repeat the same mistakes the next time :) Thanks to everyone for participating and hope to see you again!

The editorial

1607A - Linear Keyboard

Tutorial
Solution

1607B - Odd Grasshopper

Idea: doreshnikov

Tutorial
Solution

1607C - Minimum Extraction

Idea: doreshnikov

Tutorial
Solution

1607D - Blue-Red Permutation

Idea: MikeMirzayanov

Tutorial
Solution

1607E - Robot on the Board 1

Idea: MikeMirzayanov

Tutorial
Solution

1607F - Robot on the Board 2

Idea: doreshnikov

Tutorial
Solution

1607G - Banquet Preparations 1

Idea: doreshnikov

Tutorial
Solution

1607H - Banquet Preparations 2

Idea: MikeMirzayanov

Tutorial
Solution
• +122

By doreshnikov, history, 23 months ago,

Hello Codeforces!

Once again, we are glad to invite you all to Codeforces Round 753 (Div. 3), the third division round held on Nov/02/2021 17:35 (Moscow time). This round was prepared (again) by me and MikeMirzayanov. The problems are different but our anticipation is the same :) Hope you will like the problems we've prepared!

Big thanks to MikeMirzayanov for great ideas as well as for helping me with writing good statements and better tests. I'm still a bit slow with some aspects of preparing problems so it's a really noticeable help for me. (UPD: as of this moment, it became much more noticeable, so, really, thanks a lot!)

Also special thanks for testing the round to RisingWizard, ShyWoou, Mazaalai, GustavoMG, nizamoff, 2020akadaver, I_Remember_Olya_ashmelev, p0kemanbr, Kofta and, as usual, to Gassa for valuable comments! And last but not least, thanks to everyone who'll be participating! This round contains 8 problems and is expected to have a decent level of difficulty for participants with ratings up to 1600. However, all of you who wish to take part and have a rating 1600 or higher, can register for the round unofficially.

The round will be hosted by rules of educational rounds (extended ACM-ICPC). Thus, during the round, solutions will be judged on preliminary tests, and after the round, it will be a 12-hour phase of open hacks. We tried to make tests strong enough but it doesn't at all guarantee that open hacks phase will be pointless.

You will be given 8 problems and 2 hours to solve them. We remind you that the penalty for the wrong submission in this round (and the following Div. 3 rounds) is 10 minutes. Also please note that the number of problems has slightly increased since the last edit.

Remember that only the trusted participants of the third division will be included in the official standings table. As it is written by link, this is a compulsory measure for combating unsporting behavior. To qualify as trusted participants of the third division, you must:

• take part in at least two rated rounds (and solve at least one problem in each of them)
• do not have a point of 1900 or higher in the rating.

Regardless of whether you are a trusted participant of the third division or not, if your rating is less than 1600, then the round will be rated for you.

Good luck to everyone!

UPD: Editorial is out!

• +320

By doreshnikov, history, 2 years ago,

1579A - Casimir's String Solitaire

Idea: MikeMirzayanov

Tutorial
Solution

1579B - Shifting Sort

Idea: doreshnikov

Tutorial
Solution

1579C - Ticks

Idea: MikeMirzayanov

Tutorial
Solution

1579D - Productive Meeting

Idea: doreshnikov

Tutorial
Solution

1579E1 - Permutation Minimization by Deque

Idea: MikeMirzayanov

Tutorial
Solution

1579E2 - Array Optimization by Deque

Idea: doreshnikov

Tutorial
Solution

1579F - Array Stabilization (AND version)

Idea: doreshnikov

Tutorial
Solution

1579G - Minimal Coverage

Tutorial
Solution
• +141

By doreshnikov, history, 2 years ago, translation,

Hello Codeforces!

Sorry for a bit delayed English announcement, we are glad to invite you all to Codeforces Round 744 (Div. 3), third division round held on Sep/28/2021 17:35 (Moscow time). This round was prepared by me and MikeMirzayanov and we hope that you'll find the problems interesting and enjoy solving them.

I would like to thank MikeMirzayanov for helping me with both writing and preparing the problems for this round. Since it's the second Div. 3 round held I'm involved in but only the first one I'm preparing problems for from zero all the way to the end, without his guidance it would've taken much more of my time.

Also special thanks to nizamoff, andreumat, QAZZY, Vladosiya, CtrlAlt, vladmart, Igorjan94, okwedook, I_Remember_Olya_ashmelev and Aris for testing the round and giving their feedback on the problems as well as to Gassa and geranazavr555 for proofreading and correcting the statements. This round is very noticeably better than it could've been without your contribution. And last but not least, thanks to everyone who'll be participating! This round contains 7 to 8 problems and is expected to be of decent level of difficulty for participants with ratings up to 1600. However, all of you who wish to take part and have a rating 1600 or higher, can register for the round unofficially.

The round will be hosted by rules of educational rounds (extended ACM-ICPC). Thus, during the round, solutions will be judged on preliminary tests, and after the round, it will be a 12-hour phase of open hacks. We tried to make tests strong enough but it doesn't at all guarantee that open hacks phase will be pointless.

You will be given 7-8 problems and 2 hours 15 minutes to solve them.

Note that the penalty for the wrong submission in this round (and the following Div. 3 rounds) is 10 minutes.

Remember that only the trusted participants of the third division will be included in the official standings table. As it is written by link, this is a compulsory measure for combating unsporting behavior. To qualify as trusted participants of the third division, you must:

• take part in at least two rated rounds (and solve at least one problem in each of them)
• do not have a point of 1900 or higher in the rating.

Regardless of whether you are a trusted participant of the third division or not, if your rating is less than 1600, then the round will be rated for you.

Good luck and have fun!

UPD: Editorial is out!

• +308

By doreshnikov, 2 years ago, translation,

1547A - Shortest Path with Obstacle

Idea: MikeMirzayanov

Tutorial
Solution

1547B - Alphabetical Strings

Idea: MikeMirzayanov

Tutorial
Solution

1547C - Pair Programming

Tutorial
Solution

1547D - Co-growing Sequence

Idea: doreshnikov

Tutorial
Solution

1547E - Air Conditioners

Tutorial
Solution

1547F - Array Stabilization (GCD version)

Idea: doreshnikov

Tutorial
Solution

1547G - How Many Paths?

Idea: MikeMirzayanov

Tutorial
Solution
• +228