Hello, Codeforces!
Thank you all for participating in Codeforces Round 1134 (Div. 4)! I hope you enjoyed the problems and had a good time. Special thanks to everyone who helped prepare and test the round!
Below you will find tutorials for all the problems. If anything is unclear, feel free to ask questions in the comments. I would love to read about your solutions too!
Tutorial
Tutorial
Tutorial
Tutorial
Tutorial
Tutorial
2290G1 - Lakeside Trail (Easy Version)
Tutorial
2290G2 - Lakeside Trail (Hard Version)
Tutorial
Tutorial








Peak contest! Thank you
why ? any reason ?
Geniuenly amazing round! F was hard imo
Hi guys, sorry for posting this again, but I'm not sure about the proper process to appeal a ban.
I am writing from a new account so I'm unable to create a blog or dm directly.
My old handle is some_random_person, and I got banned in the contest also after I solved Problem A,B,C,D,E. I did a good amount of competitive Mathematics before entering competitive programming, which can help explain why I solved these problems pretty quickly.
I am willing to show proof that I wrote the code on myself (or my code, if allowed), but I'm not sure whether the content of the code would be enough; I'm willing to show my solutions for Educational Codeforces Round 196 (Rated for Div. 2), where I solved A,B,C,E during the contest, but I'm not sure whether the evidence is enough likewise.
I have previously commented in https://codeforces.me/blog/entry/158740, but I'm not sure whether my comment would be seen, I apologize if I am not supposed to post the same content again, and I can delete this post if the rules this is not the right place to post.
Edit: Fine I'll give up, I'm not even sure how I could prove myself now, sorry for messing up the mood by posting here, have a nice day to everyone reading this!
ruined the mood
heh i am unable to solve the questions of div4 and it is known for the beginner and as per done dsa and solved more questions on leetcode and other platform but got stucked in the simple problem and it is very demotivating for me how to improve the coding part specially maths one in the cp .please guide me it would help me a lot and i would be thankful to you guide in a way that i start enjoying cp sometime it seems like watering the dry plant efforts are going in vane
Hi, I suppose I am not the correct person to ask. But here's my thought in case anyone is interested, and I also hope it could offer some insights into how I approached the problem (instead of using AI or something): First of all I think it depends on what you specifically mean by math, I mean literally most of the questions usually involve some math knowledge. I don't want to spoil any of the solution to any of the questions, but if you're talking about things closer to just math like combinatorics I would recommend doing some competitive math (they were pretty good background knowledge at least for me), I could talk about a specific problem if necessary, but I'm just not sure whether it would count as spoiling if I talk about one of the problems in this contest right now
i think most of the easy problems are not really math at all, but rather simple and clever observations, and maybe a bit of dsa.
Nice contest! Some really interesting problems. Thanks for organizing!
For G2, during the contest I found $$$O(n \log^2 n)$$$ at first, and then I tried to optimize it. I don't know why this code is working in nearly $$$O(n \log n)$$$, but if you can find a countercase, I will be happy. 398292581
Fun fact: three minutes after my solution, I found the intended lol.
I think it can be proven that A[i] can only change like 2 times. This holds by the order of your update (the 'work' function).
Yeah, I believe in the same. But I was not entirely sure. Also in the first submission, I forgot to sort them lol
E just clicked for me, that it doesn't depend on the order of the moves but rather on the number of total moves and after that, it was just a matter of calculating total number of moves and see whether it is odd or even and that is it..
can you explain how did you calculate the total number the only way I can think of is using segment tree, I'm a noob the proof in the editorial doesn't make sense to me
This can help.
this should be the intended solution not that i%(k+1) biz, just need to optimize it for storing just the parity not whole values
that's the smart part ig. int/long long in C++ gcc by default does a 2^31/2^63 modulo and also since we are taking a modulo wrt even number. the parity is preserved. It is a malicious but fine usage of UB in C++
yes I saw these solutions with full sum calculations couldnt be hacked
No, the intended solution should be the editorial. This is only the alternative solution.
well the editorial is somewhat of an optimized version of this solution, but that could be difficult to understand for some people who have just started coding and don't have a very solid in it.
wait so your alg is about maximizing the number of moves made and then checking parity for bob and alice? does any order of moves maximize the number of moves or does that not matter for the problem?
Well the order in which alice and bob pick the number doesn't matter, the number of moves regardless of that will remain same,as to why, that is pretty simple, it follows as
intial config : a_1 , a_2 , a_3,.... a_i ,, a_j ,, a_n
we let two index say i and j, i am trying to show that it doesn't matter on which index the operation is applied first, the resulting array remains same.
i first then j
a_1 + 1, a_2 + 1, a_3 + 1, .... a_i — 1,....., a_j,.....,a_n
a_1 +2 , a_2 + 2, a_3 + 2, ... a_i — 1 + 1,...., a_j — 1,....., a_n
j first then i
a_1 + 1, a_2 + 1, a_3 + 1,....., a_i + 1,....., a_j — 1 ,....., a_n
a_1 + 2 , a_2 + 2 , a_3 + 2, ,, .. a_i + 1 — 1 ,....., a_j -1 ,....., a_n
A better way to understand these problems is through Grundy numbers and the Sprague–Grundy theorem, which are fundamental concepts in combinatorial game theory.
They are particularly useful for solving impartial games.Games in which both players have exactly the same legal moves from any given position.
The main idea is that instead of analysing the entire game state and all possible sequences of moves, we can assign a number (called a Grundy number) to each independent component of the game.
We can then combine these numbers using XOR to determine whether the current position is winning or losing.
After reading about this the solution given in tutorial definitely make sense to you.
But yes it's somewhat advanced concept but it's always better to have more knowledge.
Nice contest. Especially problem C
Ohhh yess. I've really enjoyed 'C' too! Although I solved it with deque, it'd probably be easier to solve with some vectors and calculations :|
Here is my idea for problem F today. (I used AI to help with my English grammar, because English is not my first language.)
We look at two values i and i + 1 to find their positions.
When I say "between i and i + 1", I mean the elements of the array p that are located strictly between the position of i and the position of i + 1 (in either order). Formally, if
pos[i]is the position of value i in p, these are the elements p[k] such that k is strictly betweenpos[i]andpos[i + 1]. Let k be the number of these elements.Also note that there is no integer strictly between i and i + 1, so every other value x satisfies either x < i or x > i + 1.
Key observation. The difference between b[i] and b[i + 1] depends only on the elements between i and i + 1 (including i and i + 1 themselves). Any other element x is on the same side of both i and i + 1, so it changes b[i] and b[i + 1] by the same amount, and it cancels out in
b[i + 1] - b[i].Consider the pair (i, i + 1). Since i is before i + 1 in p, b[i] is decreased by 1 and b[i + 1] is increased by 1. So this pair alone makes the difference
b[i + 1] - b[i]equal to 2, and the difference is always >= 2 in this case.Now consider the elements x between i and i + 1. Each of them is to the right of i and to the left of i + 1: - If x < i: b[i] changes by 0 (x is smaller and to the right of i, so the pair (x, i) is not counted for i), and b[i + 1] increases by 1. - If x > i + 1: b[i] decreases by 1, and b[i + 1] changes by 0.
In both cases the difference increases by exactly 1. Since there is no value strictly between i and i + 1, every element between them is of one of these two types, so the number of changed values is exactly the number of elements between i and i + 1. Therefore:
b[i + 1] = b[i] + 2 + k, sok = b[i + 1] - (b[i] + 2).The distance between the two positions is k + 1, so:
pos[i + 1] = pos[i] + b[i + 1] - (b[i] + 2) + 1 = pos[i] + b[i + 1] - b[i] - 1This case happens when
b[i] < b[i + 1].This case is similar to the case above. The difference still comes only from the elements between i and i + 1.
Since i + 1 is before i, these two elements do not affect the b values of each other (the pair (i + 1, i) is not counted, because the larger value is on the left).
Now consider the elements x between i + 1 and i. Each of them is to the right of i + 1 and to the left of i: - If x < i: b[i] increases by 1, and b[i + 1] changes by 0. - If x > i + 1: b[i] changes by 0, and b[i + 1] decreases by 1.
In both cases the difference decreases by exactly 1. Again, there is no value strictly between i and i + 1, so the number of changed values is exactly the number of elements between i + 1 and i. Therefore:
b[i + 1] = b[i] - k, sok = b[i] - b[i + 1].The distance between the two positions is k + 1, so:
pos[i + 1] = pos[i] - (b[i] - b[i + 1] + 1)This case happens when
b[i] >= b[i + 1].Both cases give the same formula,
pos[i + 1] = pos[i] + b[i + 1] - b[i] - 1. We write them as two cases only because the direction of the movement is different.We build the array step by step, starting from value 1, and compute
pos[i + 1]frompos[i]. We do not know where value 1 is, so we build an array of size 2 * n — 1 and setpos[1] = n, so thatpos[1]can end up anywhere. After computing all positions, we put each value i atpos[i].If the sum of b is not 0, the answer is -1. When we compute b, every pair (i, j) with i < j does
b[i] = b[i] - 1and alsob[j] = b[j] + 1, so the total sum is always 0. (This also fixes the shift of our construction: if the positions are distinct and contiguous, they form a block of n consecutive cells, and a zero sum forces this block to be exactly [1, n] in the real permutation.)If there is some i such that
b[i + 1] - b[i] == 1, the answer is -1. When i is before i + 1, we have b[i] < b[i + 1], and because the pair (i, i + 1) is also counted, the difference is at least 2. When i is after i + 1, the difference is at most 0. So the difference can never be exactly 1.If while building the array we get
pos[i] = pos[j]for some i != j, or a position goes outside the array of size 2 * n — 1, or the occupied positions do not form one contiguous block of n cells (they are scattered, like1 x x 4 x x 3 ...), the answer is -1.If none of these happens, the occupied block is the answer.
Time complexity: O(n)
Memory complexity: O(2n), which is O(n)
Code: 398317784
Thank you for reading my solution. This is my first time writing an editorial, so if I made any mistake in the math or in the English, please leave a comment below.
If anything is unclear or you still have questions, please comment below.
Thank you for reading.
nyc approach
Hi Mike , Thank you for the contest.
It's more of a technical point , the summations can be made cleaner by adding
\limitsright before mentioning the lower and upper bounds of the summation (or generally any structure product,cap,cup,etc..) , which sound more natural than floating boundaries , so instead of $$$\sum_{i=1}^n(g_i-h_i)\le k$$$ , $$$\sum\limits_{i=1}^n(g_i-h_i)\le k$$$ sounds better.About the code , maybe having the implementation in a separate spoiler would be better ? , I mean some people prefer to implement the task even after spoiling the idea from the editorial.
Even though I couldn't attend in time , but I feel like C is harder than D , It feels like C needs more thinking than D , probably even with the knowledge requirement.
These are just few minor things I can note , but overall great contest , I'll upsolve later problems too,
C is just sorting ig, doesnt requires much thinking
That mentality may lead to dont even know why your solution works.
but i proved my solution, its literally just sorting
I solved 'C' with sorting and deque. Although 'Editorial' shows a better way, as always lol
I solved D using a Sweep Line Algorithm 398294439
And solved E using Fenwick Tree with Range Update Point Query 398327494
holy overkill
i too initially thought of t
Perfect contest!I enjoy it,thank you
Is it only me or did anyone else code lazy segment tree for F.
only you
H can be solved by binary search and then checking if you can make all edges with value > mid,s nodes on a simple path
Could you please explain D. I didn’t quite understand the editorial.
In D, We need to find the number of letter which we applying operation on it.
for this case abdc , first we apply operation in 'c' to 'a' as c -> b ->a ,in next operation we apply in 'd' to 'b' as d->c->b ,we can observe that here c -> b is common so our operation will be like this first d to c gives abcc , then c to b gives abbb and final aaaa ,so letter b , c, d is used in operation ,thus ans is 3
so make an array for a to z with initial zero vectord(27, 0); ~~~~~
decrease the value of char(end path) in array,and increase the value of char (start path), and compute the prefix sum of result array ,and count how many >0 are there.
I did it like the merge intervals problem.
let "abcd" be the string I'll check all the pallindrome matching pairs
a-d b-c
then draw intervals first one from a to d and second from b to c because the interval a to d overlap b to c they become one i.e. a to d
it means that when we will be converting all ds to as(to match the pallindrome pair) we will also be converting everything between a and d also to a
so we need not bother about the second interval "b to c"
so answer is the one interval "a to d" => 'd' — 'a' = 3;
i did something different. i took the min and max char for each i. then i sorted, then reverse. Then i set max and min for the first element. when ever the next elements coincides with the first, they get together. whenever it doesnt happen. i add that current range then start at the next.
but my code is so hard?
D was such an interesting problem! I implemented it by brutly calculating if there is way to make the string a palindrome without making it a complete string of a's. If that took more than 25 moves, it would obviously be the wrong choice.
D was soooo good. Loved the contest
The solution to problem G2, which uses a Segment Tree for verification, and the structure is written “bottom‑up,” does not pass. Its asymptotic complexity is O(30nlogn), and the time limit is 4 seconds, but the solution gets a TL on test 3; given the speed of C++, this is very strange. (Решение задачи G2 использующие Дерево отрезков для проверки, причем структура написана "снизу-вверх", не проходит. Его асимптотика O(30nlogn), а ограничение по времени 4 секунды, но решение ловит TL на 3 тесте, учитывая скорость c++, это очень странно)
The expected complexity of G2 is $$$O(n \log h_{\text{max}})$$$, not $$$O(n \log n \log h_{\text{max}})$$$. The latter is expected to fail (if you try hard, you may have such solution to pass, though).
You can locally measure the running time if you make a largest random input.
problem E can solve by using segtree:
the tutorial E is very simple. I can't believe that there was hidden such a clever property within this problem.
any one can tell h
why they put H on last , it was so easy
Here is an alternative $$$O(n \log n)$$$ solution for problem H using binary search:
Instead of maximizing the number of reachable vertices directly, let's minimize $$$M$$$ — the maximum number of vertices that can become disconnected from vertex $$$1$$$ in the worst case. Then the answer is $$$n - M$$$.
Root the tree at vertex $$$1$$$ and precompute subtree sizes $$$sz[v]$$$. Adding one new edge creates a unique simple cycle $$$C$$$:
Thus, we want to choose $$$C$$$ so that $$$\max_{v \notin C} sz[v]$$$ is minimized.
Why it works
If there exists a cycle $$$C$$$ such that every vertex outside $$$C$$$ has $$$sz[v] \le mid$$$, then that exact same cycle $$$C$$$ also satisfies $$$sz[v] \le mid'$$$ for any $$$mid' \gt mid$$$. In other words, increasing $$$mid$$$ reduces the set of "critical" vertices that must be protected by the cycle, making the condition monotonically easier to satisfy.
How the check works for a fixed
miduse[v] = 1.cnt <= 2), because at most two cycle edges can go down from $$$1$$$.cnt <= 1), because a simple downward path cannot split into two branches.If both conditions hold, we can always extend the endpoints of the marked paths down to leaves (or connect the single endpoint back to $$$1$$$) to obtain a valid cycle $$$C$$$.
Complexity: $$$O(n \log n)$$$ per test case.
W contest!
Hello.
I'm yoniha, and I created a new account to comment here because I was banned from this contest.
I participated in Codeforces only once a long time ago and got a low rating. After that, I didn't participate in any contests on Codeforces for a while, and only participated in AtCoder. My AtCoder user page is here, and I'm ready to change the affiliation field to prove that this is my account.
Also, the template I used during the contest was submitted before the start of this contest at here, and was not generated during the contest (I modified it slightly for the Codeforces compiler).
Could you please lift the ban on my account?
Thank you.