### darkkcyan's blog

By darkkcyan, history, 3 weeks ago,

Hello, Codeforces!

I am really excited to invite you to Codeforces Round #763 (Div. 2) on Dec/28/2021 16:35 (Moscow time)! The start time is unusual, so please pay attention.

All the problems were authored and prepared by me. I would like to give special thanks to everyone who made this round possible:

The round consists of 5 problems and you have 2 hours to solve them.

Wish you good luck and high ratings!

UPD0: The score distribution 500 — 1000 — 1750 — 2500 — 2750.

UPD1: Congratulation to the winners of the round!

###### Div. 1 + 2

UPD2: The Editorial is out!

Hope that you guys enjoy the rounds, and thank you again for participating! <3

• +643

 » 3 weeks ago, # |   +199 As the first tester, and the first comment, I would like everyone to deliver contribution by clicking that green up button.
•  » » 3 weeks ago, # ^ |   +14 Me: Confused on if to upvote blog or upvote comment
•  » » » 3 weeks ago, # ^ |   +24 Both
•  » » 3 weeks ago, # ^ |   0 omg tdpencil orz
 » 3 weeks ago, # | ← Rev. 3 →   -17 Scoring Distribution?UPD: Why downvote?UPD2: Now it's updated.
•  » » 3 weeks ago, # ^ |   -17 Usually the score distribution comes shortly before the beginning of the contest__
 » 3 weeks ago, # | ← Rev. 2 →   +43 So many contests by the end of the year! THANK YOU people! Classic cuban granny postcard
 » 3 weeks ago, # |   +2 darkkcyan orz
 » 3 weeks ago, # |   0 Finally traditional 5 problem style. Unfortuntately, untraditional time I cannot make
 » 3 weeks ago, # |   -73 hi
•  » » 3 weeks ago, # ^ |   -74 hi, kaisa hai?
 » 3 weeks ago, # |   0 orz idol
 » 3 weeks ago, # |   -10 love :3
 » 3 weeks ago, # |   +1 Back to back contests in the end of the year, thank you Codeforces and all problem setters.
 » 3 weeks ago, # |   0 3 contests in a row. perfect setting for holidays. cinnamon cookies, hot chocolate and CP:))
•  » » 3 weeks ago, # ^ |   0 madman
 » 3 weeks ago, # |   +41 Wow tourist is a tester
 » 3 weeks ago, # | ← Rev. 5 →   0 Oops wrong announcement Thanks @below
•  » » 3 weeks ago, # ^ |   +11 I think you have commented on the wrong announcement.
 » 3 weeks ago, # |   +6 Hope everyone will get good results in this contest. Good luck ;)
•  » » 3 weeks ago, # ^ | ← Rev. 2 →   -57 wrong annoucement
 » 3 weeks ago, # |   -45 Is this contest rated for Div 2 ?
•  » » 3 weeks ago, # ^ |   0 It is written Codeforces Round #763 (Div. 2)...
•  » » » 3 weeks ago, # ^ | ← Rev. 2 →   -12 Thanks, got it
 » 3 weeks ago, # |   -14 They will WA until they die !
 » 3 weeks ago, # |   0 idol
 » 3 weeks ago, # |   0 Good luck everyone :3
 » 3 weeks ago, # |   0 Wow, Traditional Div2 round, will definitely participate ..
 » 3 weeks ago, # |   0 I wonder how many points for each peoblems Emmmm...5 problems make me scared
 » 3 weeks ago, # |   0 Rating Distribution ???
•  » » 3 weeks ago, # ^ |   +23 Rating DistributionRated for <2100 and unrated for >=2100
•  » » » 3 weeks ago, # ^ |   0 I think he meant points for taskssometimes they are written in the announcementlike: 500-1000-1500-2000-2500
•  » » » » 3 weeks ago, # ^ |   +36 Sweet Summer Child
•  » » » 3 weeks ago, # ^ |   0 Lmao I didn't knew this . Thanks for this
 » 3 weeks ago, # |   +62 Don't downvote anyone blindly. even if someone have good idea or trick to share they will fear to post that trick or idea in comment or blog because of fear of downvotes. I was very upset to see so many downvotes in TadijaSebez his contest(codeforces round 758(Div.1+Div.2)). maybe the way YouTube removed Dislike count Codeforces would be better place if there will be No downvote button. MikeMirzayanov Thank You for building such amazing place and please take my idea into consideration!
•  » » 3 weeks ago, # ^ |   +12 True, but better keep the downvote button and hide the downvote count, where comments are still hidden when they got too many downvotes.
 » 3 weeks ago, # |   0 idol darkkcyan orz
 » 3 weeks ago, # |   +6 two div 2 contest on 2 days, problemsetters are wonderfulhope i got positive delta tdy
 » 3 weeks ago, # |   0 Thank you @darkkcyan for this contest, regular contests are helping a lot.
 » 3 weeks ago, # |   0 Waiting for scoring distribution
 » 3 weeks ago, # |   -26 It will be a great contest.
 » 3 weeks ago, # |   0 Any interactive questions in the contest?
•  » » 3 weeks ago, # ^ |   +24 No, there will not be an interactive problem in the contest.
•  » » » 3 weeks ago, # ^ |   0 Thanks.
 » 3 weeks ago, # |   -35 Changed my handle , red colored 3 looks awesome , hope it'll be real one day , starting the journey from this contest
•  » » 3 weeks ago, # ^ |   +8 Picked the wrong day buddy.
 » 3 weeks ago, # |   +2 hope will have great time and not to lose expert.
•  » » 3 weeks ago, # ^ |   0 You can get it back by changing your rank in the magic section of your profile ;)
 » 3 weeks ago, # | ← Rev. 2 →   0 Updated
 » 3 weeks ago, # |   0 PS : The score distribution is not usual for problems C, D, E!
 » 3 weeks ago, # |   +23 Is CF running slow?
 » 3 weeks ago, # |   +9 Alice and bob are more than friends (-_-),
 » 3 weeks ago, # | ← Rev. 2 →   +2 Problem A is hard :+) many contestant said good Bye after seeing problem A (like me ) :p
•  » » 3 weeks ago, # ^ | ← Rev. 2 →   +1 How to become intelligent ?. life is hard
 » 3 weeks ago, # |   +22 Very good round for me, interesting problems. But very strange B. P.S Thanks to author for really cool illustrations for test cases
 » 3 weeks ago, # |   +39 The Gif in problem A made me so nervous
•  » » 3 weeks ago, # ^ |   0 same
 » 3 weeks ago, # |   +1 good job
 » 3 weeks ago, # |   +9 Cool gifs in A
 » 3 weeks ago, # |   +25 I always believe first problem should have simpler statement and should be on easy side. Nice contestc->d
 » 3 weeks ago, # |   +8 I made two submissions in A one in the minute 00:08 and one in 1:30 just in case the first one failed in the rejudge but i found that in standings my score in problem A decreased from 490 to 270. Will this be final score of my submission to A even after the rejudge?
•  » » 3 weeks ago, # ^ |   0 yes
•  » » » 3 weeks ago, # ^ |   0 But why? I thought that codeforces count consider the first accepted submission like ICPC rules. If I knew this I wouldn't make two submissions in A :(
•  » » » » 3 weeks ago, # ^ |   +14 but ur first soluition isn't really accepted it only passed pretests
•  » » » » 3 weeks ago, # ^ |   +6 If a contestant submits several times a problem's solution that passes all pretests, then the last solution is considered as the contestant's verified solution for this problem. All other solutions will be considered as unsuccessful attempts. Codeforces Contest Rules
•  » » » » » 3 weeks ago, # ^ |   +3 Now I feel really sad. But thanks.
 » 3 weeks ago, # |   +18 The quality of problem preparation is elite, the writer has put so much effort into the pictures... Just darkkcyan appreciation comment
 » 3 weeks ago, # |   -61 I am sorry to give a negative feedback but Problem E is extremely disappointing: no thinking required at all, and standard bin lifting during implementation. I wonder how KAN accepted this problem for a rated contest.
•  » » 3 weeks ago, # ^ | ← Rev. 2 →   0 I don't think there is any need for binlifting, it can be solved in O(N) I think (just find the next letter for each node and rest is just dfs).
•  » » » 3 weeks ago, # ^ |   -16 okay, with Binary Lifting it was completely braindead, but probably there is a solution with a better complexity. Still a very boring problem.
•  » » » » 3 weeks ago, # ^ |   0 Agree I think E is just too easy for div2E.
•  » » » 3 weeks ago, # ^ |   +29 Yes, it is O(n). In my opinion, the problem is hard, not because it requires something special, but because it is simple and the participants, on the other hand, know a lot.
•  » » 3 weeks ago, # ^ |   0 Can you please explain how did you solve the problem with a binary lifting ?
•  » » » 3 weeks ago, # ^ |   0 I thought of trying the below solution using binary lifting but ran out of time.Just as mentioned in the editorial, after finding the current inorder representation, we know the potential candidates eligible for doubling.Lets forget about the restriction k and solve the question first. i.e we can double as many nodes we want. Now for each of the eligible node from left to right, we can just traverse its ancester chain and double it if not doubled. We can stop once we find one ancestor which is already doubled. The complexity of this is O(n) as we visit each node once.Now if we add the restriction k, only difference is as below.Imagine the same process and as we double a node decrement k. Now if the number of not doubled ancestors for a eligible node is > current k, we can't double it. To check the number of undoubled ancestors we can use binary lifting (find the kth ancestor of this node and check if it is doubled). If it is already doubled, we can double the rest of the chain as it is less than k. If not we can skip the node.This is the initial submission I attempted where instead of using binary lifting for checking number of un doubled ancestors, I just looped through the ancestors to find them. https://codeforces.com/contest/1623/submission/140946673
 » 3 weeks ago, # |   +18 ordered_sett cheated.
•  » » 3 weeks ago, # ^ |   0 Do you have any better proof? Those submissions look suspicious, but that's not a definitive proof.
•  » » » 3 weeks ago, # ^ |   +12 Codeforces Contest Rules It is forbidden to obfuscate the solution code as well as create obstacles for its reading and understanding. That is, it is forbidden to use any special techniques aimed at making the code difficult to read and understand the principle of its work. MikeMirzayanov
•  » » » » 3 weeks ago, # ^ | ← Rev. 2 →   +3 You're right. At first glance I thought it was just a commented out template, but it's actually a random code copy-pasted multiple times. Definitely breaks the obfuscation rule.
 » 3 weeks ago, # |   +2 Loved problem D. Kudos to the author(s).
 » 3 weeks ago, # |   -12 binarySearchForces
 » 3 weeks ago, # |   0 In E, did it matter that the tree was binary and that we consider the in-order traversal? I don't think my solution uses either...
•  » » 3 weeks ago, # ^ |   +18 yeah, neither of them matter, except (of course) for implementation details.
•  » » 3 weeks ago, # ^ |   +26 I guess that most participants have implemented methods in $O(n \log n)$ that works on general trees...When I saw the particular structure of the tree, I guessed that there might be some method with better time complexity or lower implementation difficulty. But since the implementation of the generic algorithm is not complicated and can pass the constraints in time, I didn't bother to think about it anymore...
•  » » » 3 weeks ago, # ^ |   0 Neither of them matters for $O(n)$ methods also, except for convenience. The only thing that would change is if $u$ comes before all the children of $u$.
 » 3 weeks ago, # |   +12 why didn't you use $n*m$ or $nm$ instead of $n.m$ in D it looks like comma and it ruined my day TT :((
•  » » 3 weeks ago, # ^ |   +10 I am sorry to hear that. Initially, I wrote it as $n \times m$ but after some advice, it was changed to $n \cdot m$. But, well, the solution is solvable in $O(n + m)$ as well, which is implemented in my model solution, so maybe you can do a pro gamer's move and implement that solution :).
 » 3 weeks ago, # | ← Rev. 2 →   0 Anybody have idea on how to get the irreducible fraction in problem D?I was able to derive an analytical form involving (p%)^i, (1-p%)^i, and O(n) constants. But if I calculate the fraction under mod P, it becomes hard to simplify the fraction. And I cannot find a way to simplify it in its analytical form...XD
•  » » 3 weeks ago, # ^ | ← Rev. 4 →   +16 Short version: You can realize the robot's pattern is cyclic, then every step can be mapped to one position of the and calculated using AGP.Long version:The state of motion of the robot can be uniquely represented by the tuple $(r, c, dr, dc)$, so a given pattern of motion will form a cycle of at most $4 \cdot n \cdot m$ steps.Additionally for ease of implementation we can note that due to the grid formulation this cycle will never have a tail.Suppose the cycle is of length $k$ and there are $l$ positions $x_1, x_2, \ldots x_l$ (0-indexed) in this cycle which share a row or column with $(r_d, c_d)$.Then the expected time taken to clean this cell becomes the sum of: $\begin{array}{|c|c|c|c|} \hline p \cdot x_1 & p \cdot x_2 \cdot {(1 - p)} & \ldots & p \cdot x_l \cdot {(1 - p)}^{l - 1} \cr \hline p \cdot (x_1 + k) \cdot {(1 - p)}^{l} & p \cdot (x_2 + k) \cdot {(1 - p)}^{l + 1} & \ldots & p \cdot (x_l + k) \cdot {(1 - p)}^{2 \cdot l - 1} \cr \hline \ldots & \ldots & \ldots & \ldots \cr \hline p \cdot (x_1 + i \cdot k) \cdot {(1 - p)}^{i * l} & p \cdot (x_2 + i \cdot k) \cdot {(1 - p)}^{i * l + 1} & \ldots & p \cdot (x_l + i \cdot k) \cdot {(1 - p)}^{i \cdot l - 1} \cr \hline \ldots & \ldots & \ldots & \ldots \cr \hline \end{array}$where the probability in row $i$ and column $j$ represents the probability of the cell being cleaned from position $x_j$ during the $i$-th repetition of the cycle.We can notice that the $j$-th column forms an infinite AGP with $A_1 = x_j$, $G_1 = p \cdot {(1 - p)}^{j - 1}$, $d = k$, $r = {(1 - p)}^l$. This can be calculated easily using the standard formula available from Wikipedia or elsewhere.Submission — 140937671
•  » » » 3 weeks ago, # ^ |   +11 Luckily I do have another way of describing, or dare I say it, a different solution that is simpler.
•  » » » » 3 weeks ago, # ^ |   0 I would love to hear it, I suspect I overkilled the problem since it took me 30-40 mins to implement it in contrast to the 10 mins it took me to arrive at the idea.
•  » » » » » 3 weeks ago, # ^ |   +3 Well, I guarantee it to be simple. My Pascal code is only 50+ lines.
•  » » » » 3 weeks ago, # ^ |   -22 The, ahh, benefit of this solution is the ability to use WolframAlpha to take away all remaining specks of brainpower needed to solve the problem. See: formula
•  » » » 3 weeks ago, # ^ | ← Rev. 3 →   +11 Well I do have something similar:First, observe that the timesteps that cleaning is possible are cyclic, with cycle length no more than $4max(m,n)$.Then, find the cycle, suppose it's $p_1, \cdots, p_c$. Calculate the gap between neighboring points to get $g_1, \cdots, g_{c-1}, g_c=L-p_c$.Then the answer is $[g_1 + g_2(1-p) + g_3(1-p)^2 + \cdots + g_c(1-p)^c] [1+(1-p)^c+(1-p)^{2c}+\cdots]$And the latter term equals $\frac{1}{1-(1-p)^c}$.That's where I stuck, cause I dont know how to simplify the fraction...
•  » » » » 3 weeks ago, # ^ | ← Rev. 2 →   0 Aww I realized that the irreducible fraction is actually irrelevant.Since if u calculate $\frac{a}{b}=\frac{tu}{tv}$, where $gcd(u,v)=1$, then $ab^{-1} = tu(tv)^{-1}=uv^{-1}$ mod P.Sad that I didn't get this during contest...
•  » » » 3 weeks ago, # ^ | ← Rev. 2 →   0 Does Cycle always exist? I am getting MLE for Test case 10 because of the infinite loop :( My submissionMy bad :( , in above submission my cycle finding code is wrong,Here is my AC submission
•  » » 3 weeks ago, # ^ | ← Rev. 3 →   +8 Here is my solution. Let's build the graph where every node is a tuple (row, col, row_direction, col_direction). Obviously, this is a graph consisting of only one cycle and every node has only one outgoing edge. Each edge will have some weight indicating the probability of taking that edge. If a node is in the same row or column as the goal, its outgoing edge has weight $1 - p$, otherwise it has weight $1$.Now, let's say the cycle has length $L$ and the product of its edges's weights is $P$. Let's also define $length(u)$ as the length (number of edges) of the path from the starting node to the node $u$, and $prod(u)$ as the product of the edges's weights on the path from the starting node to the node $u$.Now, let's say our trip finishes at the node $u$, after traversing the cycle completely $k$ times. Then, the probability of such outcome is $P^k \cdot prod(u)$, and therefore the expected time to reach such outcome is $P^k \cdot prod(u) \cdot (L \cdot k + length(u))$.Therefore, for every node $u$ in the cycle, the expected time of finishing there is: $\displaystyle\sum_{k = 0}^\infty P^k \cdot prod(u) \cdot (L \cdot k + length(u))$ $= prod(u) \cdot L \cdot \displaystyle\sum_{k = 0}^\infty P^kk + prod(u) \cdot length(u) \cdot \sum_{k = 0}^\infty P^k$ $= prod(u) \cdot L \cdot \frac{P}{(1-P)^2} + prod(u) \cdot length(u) \cdot \frac{1}{1 - P}$Now, for every node $u$ not in the cycle, the expected time of finishing there is just $prod(u)\cdot length(u)$ — somehow, I forgot about this case when I was coding the problem, and still it passed the test cases, (it seems that the graph is always a cycle). UPD: Thanks to elManco for sharing a simple proof of why the graph is a simple cycle.Now, for every node $u$ that is on the same row or column as the goal, we add the above formulas (depending if it's on the cycle or not) multiplied by $p$ (the probability of cleaning those row and column).
•  » » » 3 weeks ago, # ^ |   +5 The graph is always a cycle indeed. Let $u_1, u_2, ..., u_k, ...$ the sequence of nodes you traversed in the graph where $u_1$ is the node where you started and $u_k$ the first repeated node (where you detected the cycle).If $u_k \neq u_1$ then there are at least two nodes that lead to $u_k$. Now if you think about the graph of the reversed moves, it is also a functional graph with the reversed edges. So a node with indegree $x > 1$ in the original graph implies a node with outdegree $x > 1$ in the reversed graph, which is functional. That is a contradiction.
•  » » » » 3 weeks ago, # ^ |   0 Excellent. Thank you so much!
 » 3 weeks ago, # | ← Rev. 2 →   +73 I don't think it's appropriate to prevent a lot of gifs in the statements. It took me about two minutes to load all things in problem A and D. I think E is a bit boring. Almost immediately after I saw the problems I came up with the solutions, all that remained was to implement them. Anyway, thank you for a very well prepared contest! I enjoyed the problems, especially the cool pictures in problem A and D, just the waiting time for the statements to load is really unpleasant xD
 » 3 weeks ago, # |   0 Can somebody share the references to calculate the irreducible fraction in general for the problems in which the answer is a fraction?
•  » » 3 weeks ago, # ^ |   +13 You calculate everything modulo $10^9 + 7$ (or whatever) and if you need to divide any time in your algorithm, just use Fermat's little theorem (so to calculate $\frac{a}{b}$ you calculate instead $ab^{10^9 + 5}$). The "irreducible" part doesn't really matter.
 » 3 weeks ago, # |   +7 speed forces again and again and again :(
 » 3 weeks ago, # |   0 Can anyone please explain to me his/her Problem C solution? I made 4-5 unsolvable equations and tried solving them for 1.5 hours only to find that they can't be solved (T~T).
•  » » 3 weeks ago, # ^ |   0 Do a binary search on the answer.
•  » » 3 weeks ago, # ^ |   0 binary search + DP
•  » » 3 weeks ago, # ^ | ← Rev. 2 →   +28 Let's do a binary search. We need to check if we can operate so that each pile of stones has at least $mid$ stones. Notice that if we traverse the pile of stones by their index, from largest to smallest, we can know how many stones can be removed from the pile at most. So we can just greedily move the stone forward. Note that the number of stones that can be moved forward in the $i$-th pile cannot exceed the number of stones in the initial pile, so you need to update $d_i \leftarrow \min(d_i, a_i)$. The total time complexity will be $O(n \log V)$.
•  » » » 3 weeks ago, # ^ |   0 Thanks for the detailed explanation.
•  » » » 3 weeks ago, # ^ |   0 I was wondering if moving forward from 3 to n while checking for possibility feasible?
•  » » 3 weeks ago, # ^ |   0 Use binary search. Suppose you have a function f and it’s inverse f’. Suppose computing f is straightforward and easy but f’ is tough and you want to compute f’(x). Then sometimes it is easier to search for y = f’(x) such that f(y) = x. Let us take an example for computing cube root of x. It is straightforward and easier to search for a number y such that y^3 = x than to compute x^(1/3). I hope it helps.
 » 3 weeks ago, # |   0 Can somebody help me to find out a missing edge case for my first problem's solution? code while(t>0) { int n,m, rb, cb, rd, cd; int dr=1,dc=1,time=0; cin>>n>>m>>rb>>cb>>rd>>cd; if(rb==rd || cb==cd) cout<<0<rb) cout<
•  » » 3 weeks ago, # ^ | ← Rev. 2 →   +1 you must check for min(cd-cb, 2*(n-rb)+rb-rd)) in the case where cb
•  » » 3 weeks ago, # ^ |   0 Each case should have some sort of min calculation. For example, in the (cb < cd) else case, you should still be checking (2*(n-rb)+rb-rd).
•  » » 3 weeks ago, # ^ |   0 10 10 9 1 8 10 try this
•  » » 3 weeks ago, # ^ |   0 You have the right idea, but you're not considering the case when the robot "bounces" on the horizontal side, and reaches the line of the dirty cell before reaching the columnAs a side note, 2*(m-cb)+cb-cd could be simplified to 2*m-cb-cd
•  » » 3 weeks ago, # ^ |   0 i simulated all the process using recursion, you can go check it out
•  » » 3 weeks ago, # ^ |   0 How about this?#include using namespace std; #define F first #define S second int32_t main() { ios_base::sync_with_stdio(false); cin.tie(NULL); int tt; cin >> tt; while(tt--) { int n; cin >> n; map> foo; map,int> res; for(int i = 0 ; i < n ; i++) { int l, r; cin >> l >> r; foo[l].push_back(r); } for(auto x:foo) { sort(foo[x.F].begin(),foo[x.F].end()); for(int i=foo[x.F].size()-1; i>=1; i--) { res[ {x.F,foo[x.F][i]}]=foo[x.F][i-1]+1; } res[ {x.F,foo[x.F][0]}]=x.F; } for(auto x:res) { cout << x.F.F << ' ' << x.F.S << ' ' << x.S << '\n'; } } return 0; } 
•  » » 3 weeks ago, # ^ |   0 Consider the interval $[1, n]$, and let's say Bob broke it in point $d$. If $d > 1$, then somewhere in the process the interval $[1, d-1]$ was chosen. Let's consider all intervals that start at $1$, and let $x$ be the largest index such that $[1, x]$ was chosen. Notice that no interval other than $[1, n]$ can contain $[1, d-1]$, and thus, we have that $x = d-1$. If $d = 1$, then the only interval that starts at $1$ is $[1, n]$.Implementation:I preprocessed a vector of sets ends, such that ends[i] is the set of all $x$ such that $[i, x]$ was chosen. I then sort intervals by their respective lengths, and process them in order. When processing the interval $[l, r]$, I remove $r$ from the ends[l] set, and see if the set is empty. If the set is empty, then $d = l$. Otherwise, $d$ is the largest number in the set Codefor (auto [s, l, r]: intervals) { ends[l].erase(r); if (!ends[l].empty()) printf("%d %d %d\n", l, r, *ends[l].rbegin() + 1); else printf("%d %d %d\n", l, r, l); } 
•  » » » 3 weeks ago, # ^ | ← Rev. 3 →   +1 Yes, i got it.... I implemented my approach only and got it after contest....Ughhh... I wish i did this earlier ;((((((((( Thanks by the way your solution is quite good and understandable! Nicehere is my solution
•  » » 3 weeks ago, # ^ |   0
 » 3 weeks ago, # | ← Rev. 6 →   0 // ignore — a wrong test case example
•  » » 3 weeks ago, # ^ |   0 Why did you remove your test case? Looks legit to me.
•  » » » 3 weeks ago, # ^ |   0 Because this is an invalid test case. I understood the problem statement incorrectly. Discussed this here: https://codeforces.com/blog/entry/98385?#comment-872273
 » 3 weeks ago, # |   +12 Video Solutions for A,B,C in case you are interested.
 » 3 weeks ago, # |   0 I hate speedforces rounds like this one !!
 » 3 weeks ago, # | ← Rev. 4 →   +69 Personally, I think 5 problems is not enough to form a contest. Since there are too few problem, it will always happen that it is unbalanced, and there is a huge difficulty gap between two problems. Codeforces will become Speedforces, if you are not fast enough, or even bad internet, you are finished. For example, problem C is expert level problem, and problem D and E are master and grandmaster level. Solving 3 problems will make the ranking ranges from 300 to over 2000, and the rating will make very huge difference. A balanced div 2 contest should at least have 6 problems with the following:A: newbie level (800-1000), B: newbie or pupil level (1000-1300), C: specialist or expert level (1400-1700)D: expert or candidate master level (1600-2000)E: master or grandmaster level (2100-2500)F: grandmaster level above. (>=2500).
•  » » 3 weeks ago, # ^ |   +8 There used to be another problem, but there was a problem with constant optimization solutions getting accepted, so it had to be scrapped.
•  » » » 3 weeks ago, # ^ | ← Rev. 2 →   +1 To be fair the intended solution is still 2-3 time faster compared to your solution with the latest constraints. But the thing is, I NEED to support JaVa, which is very painful to optimize. And, the Java solution still works pretty fast on my machine. I don't really know how come it ran a lot slower on Polygon.
•  » » 3 weeks ago, # ^ |   0 Agree, as a 1900 level participant, I feel painful as I spent 1 hour getting the correct formula for problem D and realized I had no time to code it.
 » 3 weeks ago, # |   0 Problem B: Any idea why this test 1 2 1 1 2 2 gets Validator 'validator.exe' returns exit code 3 [FAIL The given ranges are not from a valid game (test case 1)]
•  » » 3 weeks ago, # ^ |   +5 For n=2 there must be 1 2 range since set start from (1,n)
•  » » » 3 weeks ago, # ^ |   0 weird. Hm. Seems like I do not understand something in this problem. Could you please explain why this test case fails with the same error? 1 3 1 3 1 1 2 2 
•  » » » » 3 weeks ago, # ^ | ← Rev. 3 →   0 Ohhh. Now I get it. We literally should work with segments and cannot split them other than by Bob's actions.I solved a different problem, but my solution happened to work on this one as well XD
•  » » » » 3 weeks ago, # ^ |   0 instead of 1 1 or 2 2 it should contain 1 2 or 2 3. I think I misunderstood the problem as well during the contest, but now reading it back I get it clearly.
•  » » » » » 3 weeks ago, # ^ | ← Rev. 4 →   0 1 3 1 3 1 1 3 3 is also a valid test case
•  » » » » 3 weeks ago, # ^ |   +5 If i simplify the problem statement then initially you have range (1,n)On each step take 1 number d from range and break the range into two ranges. 1 range contains number smaller than d and other contain numbers greater than d.Now in your test case initially you have (1,3). If you break it at point d=1 then set will contain (2,3). On next step remove either 2 or 3. Other remaining range will be (3,3) or (2,2) respectively. If you break at d=2 then set will contain (1,1) and (3,3)If you break at d=3 the set will contain (1,2). On next step if you take d=1 the remaining range (2,2), other wise (1,1)But test case you made is possible in no way
•  » » 3 weeks ago, # ^ |   +5 Its missing this tc: 1 2
 » 3 weeks ago, # |   0 why B is easier than Problem A
•  » » 3 weeks ago, # ^ |   0 Both are text understanding problems in first place, so it is arbitrary which one feels more or less complecated.
•  » » » 3 weeks ago, # ^ |   +1 And reading the problem A statement is so much harder because of these animated pictures flashing into your face. I ended up skipping the contest exactly because of this single reason. I'm not epileptic, but it still felt very uncomfortable.
•  » » » » 3 weeks ago, # ^ |   0 I had problems distinguishing dr and rd, as well as dc and cd from each other.
 » 3 weeks ago, # | ← Rev. 2 →   0 Tle in test 6 in B (BFS) Can someone help... Link:- https://codeforces.com/contest/1623/submission/140934881
•  » » 3 weeks ago, # ^ |   0 use binsearch bro
 » 3 weeks ago, # |   0 Video editorial for anyone looking (Problems A to C)
 » 3 weeks ago, # |   +8 Hello! I found some perplexing behavior with the online judge:Problem: AIssue: the same code gets AC with pypy3/python3 and TLE with pypy3-64 with a small alteration (no difference logic-wise) gets AC with pypy3-64 Submission details: https://codeforces.com/contest/1623/submission/140947850Could someone enlighten me what's going on here? Could an admin help look into it if it's some interpreter issue?
•  » » 3 weeks ago, # ^ | ← Rev. 2 →   +6 I have tested with some other submissions from ao35612:TLE with pypy3-64: https://codeforces.com/contest/1623/submission/140938214AC (much less than TL) with pypy3: https://codeforces.com/contest/1623/submission/140948424and n0k:TLE with pypy3-64: https://codeforces.com/contest/1623/submission/140916043AC (much less than TL) with pypy3: https://codeforces.com/contest/1623/submission/140948345geranazavr555 or anyone can advise on this issue for python users?
•  » » 3 weeks ago, # ^ |   0 Nice, my simple solution for A got TL: SolveL = lambda: sys.stdin.readline().rstrip("\r\n") Ns = lambda: list(map(int, L().split())) def solve(): n, m, rb, cb, rd, cd = Ns() dr, dc = 1, 1 curx, cury = rb, cb ans = 0 if rd >= rb: ans = rd - rb else: ans = n - rb + n - rd if cd >= cb: ans = min(ans, cd - cb) else: ans = min(ans, m - cd + m - cb) print(ans) https://codeforces.com/contest/1623/submission/140913342
•  » » » 3 weeks ago, # ^ | ← Rev. 2 →   0 https://codeforces.com/problemset/customtest can be used to do some experiments. It looks like just your import directives from the top of your source file alone waste 794 ms of the execution time. A much leaner template without excessive imports for the stuff that you even don't need in that particular solution may help. But it's a good question whether pypy3-64 really needs to spend that much time on processing imports.Edit: Looks like all the damage comes from import unittest.mock. Commenting out this single line fixes performance problems. What is the purpose of having this particular import?
•  » » » » 3 weeks ago, # ^ | ← Rev. 2 →   0 I think this issue is quite different from the issue I showed above. The above issue may have hidden impacts on many python users.
 » 3 weeks ago, # | ← Rev. 2 →   +38 Thanks for the contest! Here are my thoughts(as I have only recently "unlocked" unrated Div2s): Problem AI thought that this problem A was rather unnecessary, and the slow-loading GIFs + long statement did not make the experience very enjoyable for me. Still, kudos to you for putting in the work of making these GIFs! Problem BNo real thoughts, felt like a filler problem. Problem CI enjoyed this problem :) Nice binary search (the way I solved it), though I do believe that the statements in the round could have been a little better, but maybe that's just me! Problem DBrilliant problem! I solved it by considering the path as a functional graph, and even though I have dealt with the resulting equations multiple times, I really enjoyed the way it was used! Problem EDid not get an opportunity to attempt this in-contest. I look forward to upsolving it!
•  » » 3 weeks ago, # ^ |   +28 Wow! Thank you for participating and feedback! I really appreciate it. <3
 » 3 weeks ago, # |   +3 For problem D, after counting the cycle with all possible step number, how to use these information to get the result of the problem(in a brilliant way)? I guess I can force each of them have same denominator and doing the mod operation to every one, but I wonder if there's some brilliant way to do these thing?Any idea?
•  » » 3 weeks ago, # ^ | ← Rev. 3 →   +21 Here was my solution:We only ever have the possibility of cleaning the target, if we are at the same row or column as the target. When we start traversing the matrix as given in the statement, we end up with a graph which has a chain of vertices (possibly of size 0) followed by a cycle.For the chain and the cycle, let's store the number of moves we took to reach a vertex $v$, for all vertices $v$ such that $v$ is at either the same row or same column (or both) as the target. I call these vertices "potential vertices".Say the chain had some potential vertices $c_1, c_2, \dots c_k$ at distances(moves) $d_1, d_2 \dots d_k$.Also, say the cycle had potential vertices $C_1, C_2 \dots C_K$ at distances $D_1, D_2 \dots D_K$.Let us consider only the cycle first. Once we have entered the cycle, the expected time to clean the target is: \begin{align} f = (\sum_{i = 1}^{K}(1 - p)^{(i-1)} *p *D_i )+ (1 - p)^K*(cycle\_size + f) \\ \implies f = g + a(b + f) \\ \implies f = \frac{(g + a*b)}{1 - a} \\ \end{align}Now, the total expected time: $F = (\sum_{i = 1}^{k}(1-p)^{(i - 1)}*p*d_i) +(1 - p)^k*f$
•  » » » 3 weeks ago, # ^ | ← Rev. 3 →   +3 Actually, there is always no chain before the cycle. This is because after lcm(2 * n — 2, 2 * m — 2) moves you will be in the starting vertex.
•  » » » » 3 weeks ago, # ^ |   +8 Ah yes, I complicated it unnecessarily yet again! Thanks!
 » 3 weeks ago, # | ← Rev. 2 →   +37 Thanks for this super nice round !IMO the problems were all interesting and educative. I hope to see more rounds from Vietnam :)Here are my thoughts about each problem Awell I guess it's cool to have a problem related to the D because it saves some implementation time ? BProblems B are often very unbalanced (i.e to easy or to hard) but it seems this one has the right difficulty ! CThis may seems stupid but I really liked the fact that the greedy algorithm needs to start from the end. It felt like a more "unique" problem to me DI couldn't solve (I thought you could go through the cycle any number of times so the expected value will be an infinite sum) but it appears this sum can be simplified ! I think this problem is really educative and the small number of AC shows that not a lot of people knows about the trick involved. EI found the solution at the end so I couldn't implement it in time but I loved the problem!PS: The gif in problem A was incredible !! darkkcyan did you use the tool from 3blue1brown to make it ?
•  » » 3 weeks ago, # ^ |   0 yeah in prob C dumb me always thought of a solution preceding "3 --> n" but the key was to start from the end.
•  » » » 3 weeks ago, # ^ |   0 Usually when you are stuck on a problem it's a good idea to try a different approach and change the way you are viewing the problem, now you'll know that you need to try thinking backward :p
•  » » » » 3 weeks ago, # ^ |   0 yes! noted down, mate.
•  » » 3 weeks ago, # ^ |   +12 Thank you so much for participating and feedback! Yes, the library is called Manim. I will also public the source code for animation in the editorial.
•  » » » 3 weeks ago, # ^ |   +5 thanks!! I hope that more problemsetters will do the same kind of animations in the future
 » 3 weeks ago, # |   +10 Video tutorial b:https://www.youtube.com/watch?v=AiP4D3vyovQ
 » 3 weeks ago, # |   0 Problem C: Is there a way to solve this problem by following the order "3 --> n".
•  » » 3 weeks ago, # ^ |   0 What?
•  » » 23 hours ago, # ^ |   0 did you figure it out?
•  » » » 23 hours ago, # ^ |   0 no, i did it in reverse only
 » 3 weeks ago, # |   0 Hey, ive solved c with binary search but was wondering whether this would work as well:First we find sufix that has minimum average value. Lets say that this value is some k.Does it stand that the answer is k, k-1 or k-2? Or sth similar?
•  » » 3 weeks ago, # ^ |   0 Okay, definitely not — 1rst case scenario
•  » » 3 weeks ago, # ^ |   0 No it won't work actually.
 » 3 weeks ago, # |   +6 Will the first to solve every problem be published? darkkcyan
 » 3 weeks ago, # |   +2
 » 3 weeks ago, # |   +5
 » 3 weeks ago, # |   0 I saw some comment explain how to use binary search to solve the Problem C. I encounted same kind of the problem but I still cannot solve it =(
•  » » 3 weeks ago, # ^ | ← Rev. 2 →   0 step 1. function "check" to answer the question, is it possible to get the minimum value M for the source array. check it in one pass of the array from last elem to firststep 2. get a estimate for the minimum and maximum of M (minimum is min elem of source array, maximum is min(a[i] + a[i+1]/3 + a[i+2]/3*2)step 3. binary search — check with M=(min + max)/2. if true, move min, if false, move max
 » 3 weeks ago, # |   +25 An important note : When you see a problem that asks you to minimize the maximum value of something or maximize the minimum value of something then Binary Search absolutely works.
•  » » 3 weeks ago, # ^ |   0 based on latest contests, binary search will be in mediun task with 90% propability)
•  » » 3 weeks ago, # ^ |   +14 More generally, if you can show the monotone of the function that you are checking (that is, before some value, the checking function returns false, and after that, it returns true`), then you can always do binary searching. There are problems that ask to maximize the minimum (or minimize the maximum) that do not involve binary search, especially when the function is not monotonous.
•  » » » 3 weeks ago, # ^ |   0 Yes before my teacher said that in such problems (maximize the minimum (or minimize the maximum)) you can use binary search, I thought we have to use DP, I'll be happy if you send some example of such problems you said that they don't need BS. Thanks.
 » 3 weeks ago, # |   0 Upload the editorial!!
 » 3 weeks ago, # |   +8 When will rating be updated?
 » 3 weeks ago, # |   0 blease giv problems with shorter statement O_o
 » 3 weeks ago, # |   0 Ratings must have been updated till now...!!
 » 3 weeks ago, # |   0 I hope rating will be updated before today's contest
 » 3 weeks ago, # |   +28
•  » » 3 weeks ago, # ^ | ← Rev. 2 →   +14 Lmaooo SpoilerI didnt observed there was animated test case until I saw this meme
•  » » » 3 weeks ago, # ^ |   0 And did you know, there is also animated editorial :catthink:
 » 3 weeks ago, # |   0 unrated?
•  » » 3 weeks ago, # ^ |   0 It seems to be unrated, cause I opened my unrated contest section at my profile and I found it at there
•  » » » 3 weeks ago, # ^ |   0 It's not, Any new contest you join will be found in unrated till rating changes occur (i.e : we still don't know) (but it will possibly be rated)
•  » » » » 3 weeks ago, # ^ |   0 thanks
•  » » » » » 3 weeks ago, # ^ |   0 You are welcome :)
 » 3 weeks ago, # |   +8 The start time is unusual The Update time is unusual, too :(.
 » 3 weeks ago, # |   +40 Meme
•  » » 3 weeks ago, # ^ |   0 Even I'm searching for that..
 » 3 weeks ago, # |   0 Unrated?
•  » » 3 weeks ago, # ^ |   0 Just wait
 » 3 weeks ago, # |   0 When will the rating changes come?