### n0sk1ll's blog

By n0sk1ll, history, 2 months ago,

Author: n0sk1ll

Hint
Solution
Bonus

## 1898B - Milena and Admirer

Author: ELDRVD & n0sk1ll

Hint
Solution
Bonus

Author: n0sk1ll

Hint
Solution
Bonus

Author: n0sk1ll

Hint
Solution
Bonus

Author: ELDRVD

Hint
Solution
Bonus

## 1898F - Vova Escapes the Matrix

Author: n0sk1ll

Hint
Solution
Bonus
• +124

 » 3 weeks ago, # |   +25 Lightning speed editorial!Thanks for the greatly balanced round !
•  » » 3 weeks ago, # ^ |   0 The bonus problems don't have a tutorial?
 » 3 weeks ago, # | ← Rev. 3 →   -39 Can't say it's a good competitionP.S. Why is there no implementation?
•  » » 3 weeks ago, # ^ |   -25 They didn't even bother to solve their own unbalanced problems lol (joke)
•  » » » 3 weeks ago, # ^ |   0 problems were pretty balanced, except C!=D
 » 3 weeks ago, # |   0 Hello! Can someone explain the bug in my code at this submission? I really can't find it after spending hours on it and it's really annoying me. Thanks!233462452
•  » » 3 weeks ago, # ^ | ← Rev. 3 →   0 I think this is a breaking testcase: NIL (sorry false statement, but it was what broke my code which failed on testcase 3 also)
•  » » 3 weeks ago, # ^ |   +2 Here is a test case that fails: 3 4 12 5 Your code outputs 3, but the correct answer should be 2. Split the 12 into 8+4, then split the produced 8 into 4+4. After two splits, the resulting array is [4, 4, 4, 4, 5]
•  » » » 3 weeks ago, # ^ |   0 That helps, thank you!
•  » » » 3 weeks ago, # ^ |   0 Even I was getting the same wrong answer. Thanks for pointing out the mistake!
 » 3 weeks ago, # | ← Rev. 2 →   0 Delete
•  » » 3 weeks ago, # ^ |   0 Would you like to share the link please?
•  » » » 3 weeks ago, # ^ | ← Rev. 2 →   0 delete
•  » » » » 2 weeks ago, # ^ |   0 Thanks for the link , i was trying to find this problem that i remember solving
•  » » 3 weeks ago, # ^ |   0 us
 » 3 weeks ago, # |   0 not able to figure out even... Milica and String ;(
•  » » 3 weeks ago, # ^ |   0 its okay , you are new even I can only solve A
 » 3 weeks ago, # |   +5 Thanks for preparing the editorial beforehand! I'm seeing a pattern of this, hopefully it will be the norm soon.
 » 3 weeks ago, # |   +5 E = obvious treap: 233471686
•  » » 3 weeks ago, # ^ |   +81 That's like using a bazooka to kill an ant
•  » » 3 weeks ago, # ^ |   0 you should learn how works std::set
•  » » » 3 weeks ago, # ^ |   0 You are right. Often I write treap, and then realize that using set is enough
•  » » » » 3 weeks ago, # ^ |   0 But in this problem, I used treap with implicit key, which cannot be replaced with std::set
•  » » 3 weeks ago, # ^ |   +5 segtree also works good here
•  » » 3 weeks ago, # ^ |   +5 I knew there will be overkillers! When I was making a test solutions, I typed a segtree of 260 lines.
•  » » » 3 weeks ago, # ^ |   0 Great! Share your code plz
•  » » 3 weeks ago, # ^ |   +5 normal vectors are also good.
 » 3 weeks ago, # |   -17 problem B only has around 2500-2600 solves accepted solves. Div2B shouldnt have this low solves. I didnt like this round.
•  » » 3 weeks ago, # ^ | ← Rev. 2 →   0 i did solve B and i am still wondering why so many less solves i mean it is not that hard after all just gotta start thinking from the end of the array and working with greeedy solutin that's it
 » 3 weeks ago, # |   +8 B problem -- SEE HERE
•  » » 3 weeks ago, # ^ |   0 exact same problem
 » 3 weeks ago, # |   -9 In 1898C — Colourful Grid editorial solution:The bottom right 3 colours are misplaced. Please fix it.
•  » » 3 weeks ago, # ^ |   0 They are not misplaced, they allow to do a "detour" of size 2: at position (n-2, m-1) (counting from 0), you go left, then down, then right instead of just going down.The first loop (top left) is to do cycles of 4 or multiples. And together, you can make "detours" of length 2,4,6,8,10,... By detour I mean additional steps compared to doing only n-1 + m-1 steps (the fastest trip from top left to bottom right).
•  » » » 3 weeks ago, # ^ |   0 Ohh yeah that makes sense. Sorry.
•  » » » 3 weeks ago, # ^ |   0 cant you just use top left loop for 2 also i mean only 2 additioanal sides are only added if you go downfirst
•  » » » » 3 weeks ago, # ^ | ← Rev. 3 →   0 Smart idea! Going clockwise (in cycle) for "detours" that are multiple of 4, going counter clockwise for "detours" like 2 + 4*k with k being integer. We don't even need a cycle bottom right, you are right!
•  » » » » 13 days ago, # ^ | ← Rev. 4 →   0 Did you mean from 0,0 first going down, right, up then right? Isn't it impossible for n = 3,m = 3, k = 10? For me I couldn't find a path if only using the top left loop.
 » 3 weeks ago, # |   0 why B is too hard?
•  » » 3 weeks ago, # ^ |   0 Because it is greedy algorithm, as I can see
•  » » » 3 weeks ago, # ^ |   0 Thinking about the solution (like the greedy approach) was very easy in my opinion it was the implementation that was hard and required concentration and patience
 » 3 weeks ago, # |   0 Will you add solutions in Russian?
•  » » 3 weeks ago, # ^ |   0 But also thanks)
 » 3 weeks ago, # |   -71 Hope this round for 10+ days but, I just had a worse round than the last round .All problems too hard, Div 2 just like Div 1. Writters are you crazy ??DOWNVOTED this blog.
•  » » 3 weeks ago, # ^ | ← Rev. 2 →   +28 LOL. You don't even know how hard Div 1 is. (I don't either)
•  » » 3 weeks ago, # ^ |   0 Fun fact: we dropped the original F because it was googleable.
•  » » » 3 weeks ago, # ^ |   0 what about the B?
•  » » » » 3 weeks ago, # ^ |   0 for each index, you can use binary search to find the K, K is the smallest number divided a[i] to k part satisfies the biggest part is <= min[n->i] and the smallest part is >= a[i-1]. Then the answer += k-1. If you want to minimize the operator you must divide a[i] such that the distance of all parts is smallest. Like: 5 divides to {1,2,2}, 8 to {2,3,3} or {2,2,2,2} depending on min[n->i].My accepted submission: 233693869
•  » » » » » 3 weeks ago, # ^ |   +1 That a perfect solution for a easy problem=)) I love you because you provide me a good solution<33
•  » » » » » » 3 weeks ago, # ^ |   0 Thank!
•  » » » » » 3 weeks ago, # ^ |   +1 why to even binary search it mate, consider a1,a2,a3,a4so the condition to split a3 is to find a x such that a3/x + 1(if(a3%x)!=0) and your next curr becomes a3/x.Refer this submission: Your text to link here...
•  » » » » » » 3 weeks ago, # ^ |   +1 Well, your solution is very optimate! Thank for a good solution!
•  » » » » » » » 3 weeks ago, # ^ |   +1 np
 » 3 weeks ago, # | ← Rev. 2 →   +51 Fun fact: we wanted put this D(but with minimisation) to our div.3 as F, but tester have seen it before and we removed it :)
•  » » 3 weeks ago, # ^ |   +34 bro your profile picture is insane
•  » » » 3 weeks ago, # ^ |   +23 your pic is insane too bro
•  » » » » 3 weeks ago, # ^ |   +23 bro your is also really cool
•  » » » » » 3 weeks ago, # ^ |   +12 bro your profile picture is insane too, what a coincidence!
•  » » 3 weeks ago, # ^ | ← Rev. 3 →   -50 in this problem $\min$ and $\max$ are almost the same. This round should be unrated Sorry I thought zwezdinv was one of the writters :(
•  » » » 3 weeks ago, # ^ |   0 how did u determine that authors knew it?
•  » » » 3 weeks ago, # ^ |   0 their solutions are almost same
•  » » 3 weeks ago, # ^ | ← Rev. 2 →   +7 Isn't they different? Ideas are not the same. I knew for that problem before our round.
•  » » » 3 weeks ago, # ^ |   +7 I knew about the task and informed the rest of the team, but we concluded that they were not similar enough.
•  » » » » 3 weeks ago, # ^ |   0 Really ? In your editorial you considered 3 situations. The only difference between two problems is to calcalute situation 1 and to calcalute situation 2.Unluckily, the way to calcalute is exactly the same.
•  » » » 3 weeks ago, # ^ |   0 imo idea for both of them is to represent given value into sum of lengths of segments
•  » » 3 weeks ago, # ^ |   -28 Crazy, you still used it in a contest but just changed the min to max bruh
 » 3 weeks ago, # |   +12 Really like the idea behind the Problem D. There was similar problem in the contest before, back then it was impossible to figure out by myself, but now I got it.
•  » » 3 weeks ago, # ^ | ← Rev. 2 →   -24 (deleted)
 » 3 weeks ago, # |   +3 When I registered for this round, I thought I was registering for Div 2, not Educational
 » 3 weeks ago, # |   +16 Why is this editorial downvoted? Is it because problem B is repeated (from what I've read in some comments)?
 » 3 weeks ago, # |   0 A < C < E < D < B
•  » » 3 weeks ago, # ^ |   0 Observing the testing, it would be said that this time it was a rather subjective thing. Anyways, thanks for your feedback!
•  » » 3 weeks ago, # ^ |   +8 A < B < E < D < C
 » 3 weeks ago, # |   +10 The correct questions may be very difficult or have no implementation. But the authors of the questions made a lot of effort to create these questions and to create the contest.Thank you for contest :)
 » 3 weeks ago, # |   0 i didnt enjoy the round, im sorry :(
 » 3 weeks ago, # |   0 I think B and D have appeared before
 » 3 weeks ago, # |   +7 what a fantastic well-made problems ?? I'm really impressed and horribly depressed ....
 » 3 weeks ago, # |   0 why this is wrong for the first test case in problem C ? YES R B R B B R B R R B R B B R B R R R B R B B B R B R R R B R B 
•  » » 3 weeks ago, # ^ |   0 Better question, why do you think it is correct? Can you outline the path of length 11 from the top-left corner to the bottom-right corner? Personally, I'm not able to see such a path. The closest I can see travels the left edge and then the bottom edge, and then takes a detour near the end, but the colors on the last two edges do not allow for such a detour. Can you elaborate on what path you had in mind?
•  » » » 3 weeks ago, # ^ | ← Rev. 2 →   +3 Yep, I see now I missed the edge in the square of bottom right corner, thanks
 » 3 weeks ago, # |   -36 Very balanced problems! (sarcasm)
 » 3 weeks ago, # |   0 I thought in B I can just divide/2 to get the minimum operation and value . I still dont know how to proof the above assumption !
•  » » 3 weeks ago, # ^ |   0 Assume you have 18 6 Then you have to split 18 to 6 6 6
 » 3 weeks ago, # |   0 didn't my favorite one.
 » 3 weeks ago, # | ← Rev. 2 →   +1 im dumb and i apologize
 » 3 weeks ago, # |   0 This is the exact same problem as B: https://leetcode.com/problems/minimum-replacements-to-sort-the-array/
 » 3 weeks ago, # |   +19 B appeared as a subproblem in a different problem (https://codeforces.com/contest/1603/problem/C), and n0sk1ll even solved it during the contest (https://codeforces.com/contest/1603/submission/133683209).Any comments from the authors?
•  » » 3 weeks ago, # ^ |   0 wow such an amazing round, problem b appearing two other problems, one of them is sub-problem the other is the exact copy
•  » » 3 weeks ago, # ^ |   0 the author knowing it, and then too allowing this. great contest!!
•  » » 3 weeks ago, # ^ |   +9 Can one of the authors respond? Like, isn't it a serious accusation? Did the coordinator know about that?
 » 3 weeks ago, # |   +1 I am very sad to find B in this contest is exactly same to this 2366. Minimum Replacements to Sort the Array ,a problem in LeetCode.And there are many people having Accept it but I haven'tWhat makes me even sadder is that I spent too much time on question B, which caused me to AC on question D one minute after the competition.
•  » » 3 weeks ago, # ^ |   +1 ".And there are many people having Accept it but I haven't" not because you were unable to solve it means everybody who got AC had already seen the problem besides B is not that hard if you are specialist you gotta solve it iwas gray before this contest and i have solved it, besides the fact that it lost youu a lot of time is because of your bad time management
 » 3 weeks ago, # | ← Rev. 3 →   +9 I'm gonna be honest, C was excruciatingly painful. The idea was simple but the implementation was awful.I feel like a much more natural way to do D is as follows:Let $S = \sum_\limits{i=1}^n |a_i - b_i|$, then a swap of two elements of $b$ at indices $i,j$ is equivalent to $S \to S + |a_j - b_i| + |a_i - b_j| - |a_i - b_i| - |a_j - b_j|$$S is clearly invariant, so to maximise S + |a_j - b_i| + |a_i - b_j| - |a_i - b_i| - |a_j - b_j|, it suffices to maximise |a_j - b_i| + |a_i - b_j| - |a_i - b_i| - |a_j - b_j|.We can iterate over i and find the best j < i that maximises the above, and then take max over all i. If we are at index i, then |a_j - b_i| + |a_i - b_j| - |a_i - b_i| - |a_j - b_j| = |a_j - B| + |b_j - A| - C - |a_j - b_j|, where A,B,C are known "constants".Then, we just need to maximise |a_j - B| + |b_j - A| - |a_j - b_j|. The way I thought to do this was to just use the fact that x \leqslant |x|, so (a_j - B) + (b_j - A) - |a_j - b_j| \leqslant |a_j - B| + |b_j - A| - |a_j - b_j|$$(a_j - B) + (-b_j + A) - |a_j - b_j| \leqslant |a_j - B| + |b_j - A| - |a_j - b_j|$$(-a_j + B) + (b_j - A) - |a_j - b_j| \leqslant |a_j - B| + |b_j - A| - |a_j - b_j|$$(-a_j + B) + (-b_j + A) - |a_j - b_j| \leqslant |a_j - B| + |b_j - A| - |a_j - b_j|$So I made 4 arrays that stored each type of modified element, then just took the cumulative max up to index $i-1$ (i.e. $\max(\text{arr}[0:i-1])$) of all 4 arrays at each index to find the best configuration, and added in the constants later.233479793(I don't think this idea works for the min variant, i.e. minimise the score when swapped)
•  » » 3 weeks ago, # ^ |   0 I solved this way too
•  » » 3 weeks ago, # ^ |   +11 I have just upsolved problem D based on your method! Thank you for your detail explanation!
 » 3 weeks ago, # | ← Rev. 2 →   +2 im dumb and i apologize
 » 3 weeks ago, # |   -8 Your solution for 1898C — Colorful Grid does not work for the edge case m=2, k=(m-1+n-1)+2
•  » » 3 weeks ago, # ^ |   +11 3 <= m, n <= 16.
•  » » » 3 weeks ago, # ^ |   0 thanks. I misread and solved it for m, n >= 2 :p
 » 3 weeks ago, # |   -12 The C question was retarded. If you keep an implementation question try to keep it so that atleast some good pattern shows up.
 » 3 weeks ago, # |   +51 Why so many dislikes? Problems are hard but good.
•  » » 3 weeks ago, # ^ |   +13 I don't like the editorials. For example problem C editorial doesn't have explanation at all.
•  » » » 3 weeks ago, # ^ |   +13 It's simple from picture, like we can rotate for %4 in first loop and only thing remaining will be remainder 2 that is handled via second loop if exist
•  » » » » 3 weeks ago, # ^ |   0 Yeah but not everyone understands from the picture. Also they should explain how they got to the picture.
•  » » » » » 3 weeks ago, # ^ |   0 Bro I have question,why we are using mass reduction in spacecrafts wouldn't radiation pressure will be better option?
•  » » » » » » 3 weeks ago, # ^ |   0 yes
•  » » » » » » » 3 weeks ago, # ^ |   0 So why don't we work on radiation pressure to use it on spacecrafts
•  » » » » » » » » 3 weeks ago, # ^ |   0 idk
•  » » 3 weeks ago, # ^ |   -8 B, D are copied.
 » 3 weeks ago, # |   -13 Problem B and D is repeated.Also a poor distribution of problems I have a question. What did you learn from this contest guys?Please encourage people to solve problems.
•  » » 3 weeks ago, # ^ |   0 I learned a lot from C. Mainly because I thought it would be smart to use two 2-dimensional arrays to calculate the solution and then output them.Only using one 2-dimensional array is a lot easier though. Easier to debug, easier to fill and not harder to output.
 » 3 weeks ago, # | ← Rev. 2 →   -8 E could have been better, a little bit too detailed sample testcases for a div2E.
 » 3 weeks ago, # |   0 Can someone tell me why I got 'Idleness limit exceeded' in my submission? I couldn't get it. Thanks!233470642
•  » » 3 weeks ago, # ^ |   0 Your code is a TLE but since you are using cerr, you are getting Idleness limit exceeded.Here it is without cerrs: 233490794
 » 3 weeks ago, # |   0 Problem E is very similar to 1187D - Subarray Sorting, the idea behind both problems are just the same, E just need one more not-so-hard-to-see observation. I just added a few lines of code and got AC: 233489174, 233489126
 » 3 weeks ago, # |   0 D is a pretty standard problem. I have seen very similar problem twice: https://www.geeksforgeeks.org/maximum-value-arri-arrj-j/ Once in Nutanix OA
 » 3 weeks ago, # |   +100 If you don't want to invent a new type of BFS for F but just want to use a normal BFS as a black box, you can still do it using a cool idea: we want to choose two exits and find distances from them to all points in the greed. Let's split all exits randomly into two types and run two different BFSs from the first exit and from the second exit. With probability $1/2$ our desired pair of exits will be in different groups, so we will find the answer. By repeating this process $T$ times for some constant $T$ we may bring the error probability down to $1/2^T$.
•  » » 3 weeks ago, # ^ |   +61 Maybe this solution can be improved to 0 error probability if we don't split exits randomly, instead we number each exit from $0$ to $n + m - 1$, then process $log_2(n+m)$ times, and for the $i$-th process, split those exits by $i$-th bit of their index. So that every pair of exits will be checked.
•  » » » 3 weeks ago, # ^ | ← Rev. 2 →   0 True, I did this in my solution and it worked, well I didn't split according to i-th bit
•  » » » 3 weeks ago, # ^ |   +14 Oh, yes, that's great. (I guess, there are at most $2 \cdot (n + m) - 4$ exits though but whatever).
 » 3 weeks ago, # |   0 https://leetcode.com/problems/minimum-replacements-to-sort-the-array/ Problem B is found on leetcode. This is unfair !
 » 3 weeks ago, # |   0 i want to cry, i just solve the first question. and the second question i tried 2 times. for the 4th question i really hard to devise a efficient algorithm i just can consider BF.
 » 3 weeks ago, # |   +11 When submitting code, I observed that the speed of C's spj is very slow. Although the construction of C is indeed not difficult, I want to know how C's spj checks whether the construction scheme is correct. Does it find all the cycles? Thanks, n0sk1ll.
•  » » 3 weeks ago, # ^ |   0 I am also interested in the bonus for Problem C (how to implement the checker for C).My initial idea is to split each node into two ones (red and blue, representing the color of the last edge traversed when reaching that node).The problem would then be transformed into: how to determine if there exists a path of length l between two specified points in a cyclic undirected graph. However, I haven't found a straightforward solution to solve this problem.
 » 3 weeks ago, # | ← Rev. 4 →   +3 Solution for D Code#include using namespace std; #define int long long int int32_t main(){ ios_base::sync_with_stdio(false); cin.tie(NULL); int testCases; cin >> testCases; while(testCases--){ int n,MAX=0,MIN=1e10,ans=0; cin >> n; int A[n],B[n]; for(int i=0;i> A[i]; for(int i=0;i> B[i]; for(int i=0;i=B1 after swapping the contribution is(b2 - a1) + (a2 - b1) - abs(a1-b1) - abs(a2-b2)= b2+a2-abs(a2-b2) - (b1+a1+abs(a1-b1))MAX( b2+a2-abs(a2-b2)) - MIN(b1+a1+abs(a1-b1)) => ans
•  » » 3 weeks ago, # ^ | ← Rev. 2 →   0 How did you come up with the statement A1<=B2 and A2>=B1?Please shed the thought process/intuition/example case works.Btw this thinking looks more natural
 » 3 weeks ago, # |   +3 There is a no brainer solution for problem D. We can use the idea from https://www.geeksforgeeks.org/maximum-value-arri-arrj-j/.My submission:https://codeforces.com/contest/1898/submission/233490749
 » 3 weeks ago, # |   +7 This contest stole some problem. It is stupid and should be unrated.
•  » » 3 weeks ago, # ^ |   0 I've seen in your account that you didn't join the contest. If you don't support the writers of this contest, do not make them feel bad. They poured their heart in the contest, and they do not need to suffer more. Comment responsibly or don't comment at all. Roasting the writers is not a good thing to do and no one should do it. I love the CF community but I hope the community keeps itself in order and to punish any members that doesn't support the community.
•  » » » 3 weeks ago, # ^ | ← Rev. 3 →   0 I might get downvote for saying this but this is my alt to comment because I don't want negative contribution, my main account did join the contest, also I don't think they poured their heart in the contest(just look at the copied problem). Even if they do, what's good of poured their heart in the contest when the quality is bad.And... look at how you support the community: https://codeforces.com/blog/entry/119772#comment-1067920
•  » » » » 3 weeks ago, # ^ |   0 ok, that may be true, but just don't roast 'em that bad
 » 3 weeks ago, # |   0 Solution to bonus A: Only 1 operation.Let numb be the number of letters of B in string SCase1: if numb = k -> 0 operations neededCase2: if numb < k -> 1 operation, iterate over every position in string, if A -> B, numb + 1 until numb = kCase2: if numb > k -> 1 operation, iterate over string and any letter B change to A and numb-- until numb = kMaximum 1 operation
 » 3 weeks ago, # |   -8 The problem B we set k = a[i — 1] / a[i] if we have 20 6 then k will be 4 and I can set it 5 by splitting 20 to 5 5 5 5 can someone explain it to me
•  » » 3 weeks ago, # ^ |   0 split 20 into k parts(k=4) -> 5 5 5 5
 » 3 weeks ago, # | ← Rev. 2 →   0 Can someone correct me if i am wrong : problem (Milena and admirer) for the test case : 3 7 17 5 ans should be 5 but everyone's solution giving 4 how it is 4 can someone explain me? really appreciable
•  » » 3 weeks ago, # ^ | ← Rev. 2 →   0 17 -> 4 4 4 57 -> 3 4so，3 7 17 5 -> 3 3 4 4 4 4 5 5
•  » » » 3 weeks ago, # ^ |   0 thanks dude
 » 3 weeks ago, # |   0 Will be russian translations?
 » 3 weeks ago, # |   0 if i get first problem code, that will be easier to understand
 » 3 weeks ago, # |   0 Although I could not solve problem B during the contest,(it was so close to being accepted QAQ), I still think problem B is an excellent & interesting problem.The editorial is very clear too!
 » 3 weeks ago, # |   0 n0sk1ll, can you please tell why in 1898F - Vova Escapes the Matrix, it will always be optimal to find shortest path to 2 exit points in the 3rd type matrix??Because , cannot there be a such construction of matrix where the shortest path to 2 closest exit points can flow the path in such a way that later on we will not be able to put maximum obstacles in remaining blocks ??
•  » » 3 weeks ago, # ^ |   0 We will fill all the cells that are not part of at least 1 path. Therefore, we need the least amount of cells empty, but they need to form at least 2 exit paths. I might have not understood your question correctly, if that is the case, please let me know.
•  » » » 3 weeks ago, # ^ | ← Rev. 5 →   0 NemanjaSo2005, thanks for the reply.But, what I am asking is that how we are so sure that the shortest path to 2 closest exist points will be optimal.Because I am thinking cannot there be such a matrix which is constructed such that , in reaching those closest points you got to fill the maximum cells in the grid later and that will not be optimal then.And it can be rephrased also in the other way that " Cannot there be a path to some not closest points that can make the final answer optimal.(because in that unique construction of matrix the path to that not closest path is not very concentrated with initial obstacles compared to the path to closest exit points" I.e. will be able to fill out maximum cells with obstacle.Can there such a case exist ? Because greedy have to be true for all the possible cases that's why I asked the doubt ?
•  » » » » 3 weeks ago, # ^ |   0 NemanjaSo2005, I think my assumption will be wrong then ,the path I have said to the closest exit point will not be shortest then. And will become wrong by contradiction.But , however can you please still clarify. It will be very helpful.
•  » » » » » 3 weeks ago, # ^ |   0 The optimal path goes from Vova's cell to some other with shortest path. From that cell, there is a divergence to 2 paths, each being shortest path to some edge. Just draw a few matrices and you can make sure yourself that it is the case.
•  » » » » » » 3 weeks ago, # ^ |   0 Ok, thank you very much for the reply and clearing the doubt.
 » 3 weeks ago, # |   -8 Well B is just a leetcode problem.Link
 » 3 weeks ago, # |   0 Thanks for the fast editorial.
 » 3 weeks ago, # |   0 greedy algorithm is so hard
 » 3 weeks ago, # |   +8 How to solve F's Bonus? The graph truly look like a LCA problem but I cannot find a way to construct the tree. I have tried to construct the tree by the distance from the start point, but i failed. Cound someone give me a idea? It's better to use the following graph as an example. 7 5 ##### #.V.# #.#.# #.#.# #.#.# #...# #.#.# Sorry for poor English expression.
 » 3 weeks ago, # | ← Rev. 2 →   0 A simpler approach to problem C : 233694952
•  » » 3 weeks ago, # ^ |   0 nice solution! how did you come up with this?
•  » » » 2 weeks ago, # ^ | ← Rev. 2 →   0 we can complete the path by taking any n-1 rows segment and m-1 column segements....so why we can't take the easiest one path...ie. either we can take first row and last col to reach end or we take first col and last row to reach end....and if you do dry-run.. you will realise parity of k must be same as that of n-1+m-1 or simple (n+m) and obviously k>=(n-1+m-1)Sorry for the late reply...I was busy
•  » » » » 2 weeks ago, # ^ |   0 thanks
 » 3 weeks ago, # |   0 Where can i attempt bonus problem??
 » 3 weeks ago, # |   0 C, i am getting this error on testcase 1:wrong answer Token parameter [name=answer] equals to "R", doesn't correspond to pattern "[Yy][Ee][Ss]|[Nn][Oo]" (test case 5)my answer for 5th test case which is 4 4 8 is ~~~~~YES R B R R R R B B B B B B B B B B B B B R B B R B ~~~~~there's a path which follows. -> -> -> v v <- v ->233730117
•  » » 3 weeks ago, # ^ |   0 Check your output on the fourth test.
•  » » » 2 weeks ago, # ^ |   0 Thank you, got it
 » 3 weeks ago, # |   0 For Problem D, I had implemented the idea of swapping either min(a) with max(b) or max(a) with min(b). Can anyone tell me the problem in my solution?
 » 13 days ago, # |   0 Any idea to solve the bonus for problem B? Thanks in advance!
•  » » 10 days ago, # ^ |   0 Did you got the the solution for bonus part of problem B?
 » 13 days ago, # |   0 Problem c can't go from 1 to 2, and then go from 2 to 1 again.
 » 11 days ago, # |   0 please can anyone explain problem C
 » 10 days ago, # | ← Rev. 3 →   0 ELDRVD and nosk1ll , would you please tell how to solve bonus part of problem B?
 » 10 days ago, # | ← Rev. 2 →   0 I think for the bonus part of problem C , We can use meet in the middle concept.K-(n+m) is odd or negative then no solution exit.k-(n+m) is multiple of 6 then k = n+m+6k-(n+m) is multiple of 4 then k = n+m+4k-(n+m) is multiple of 2 then k = n+m+2Now k can be at max 38.Use meet in the middle concept here. Find number of nodes({point,last edge as red or blue}) where it can end starting from (1,1) and (n,m). And then take intersection. If null color pattern is bad, else it is good enough is have atleast one path.
 » 10 days ago, # |   0 how to solve bonus problem E?
 » 5 days ago, # |   0 .ComplaintFrame { display: inline-block; position: absolute; top: 0; right: -1.4em; } .ComplaintFrame a { text-decoration: none; color: #ff8c00; opacity: 0.5; } .ComplaintFrame a:hover { opacity: 1; } ._ComplaintFrame_popup p, ._ComplaintFrame_popup button { margin-top: 1rem; } ._ComplaintFrame_popup input[type=submit] { padding: 0.25rem 2rem; } ._ComplaintFrame_popup ul { margin-top: 1em !important; margin-bottom: 1em !important; } emmmm, I'm curious how the special judge is implemented in question C. It seems like I would only write dfs k-steps to verify the answer