### Блог пользователя n0sk1ll

Автор n0sk1ll, история, 2 месяца назад,

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
Разбор задач Codeforces Round 910 (Div. 2)
• +124

 » 3 недели назад, # |   +25 Lightning speed editorial!Thanks for the greatly balanced round !
•  » » 3 недели назад, # ^ |   0 The bonus problems don't have a tutorial?
 » 3 недели назад, # | ← Rev. 3 →   -39 Can't say it's a good competitionP.S. Why is there no implementation?
•  » » 3 недели назад, # ^ |   -25 They didn't even bother to solve their own unbalanced problems lol (joke)
•  » » » 3 недели назад, # ^ |   0 problems were pretty balanced, except C!=D
 » 3 недели назад, # |   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 недели назад, # ^ | ← 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 недели назад, # ^ |   +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 недели назад, # ^ |   0 That helps, thank you!
•  » » » 3 недели назад, # ^ |   0 Even I was getting the same wrong answer. Thanks for pointing out the mistake!
 » 3 недели назад, # | ← Rev. 2 →   0 Delete
•  » » 3 недели назад, # ^ |   0 Would you like to share the link please?
•  » » » 3 недели назад, # ^ | ← Rev. 2 →   0 delete
•  » » » » 2 недели назад, # ^ |   0 Thanks for the link , i was trying to find this problem that i remember solving
•  » » 3 недели назад, # ^ |   0 us
 » 3 недели назад, # |   0 not able to figure out even... Milica and String ;(
•  » » 3 недели назад, # ^ |   0 its okay , you are new even I can only solve A
 » 3 недели назад, # |   +5 Thanks for preparing the editorial beforehand! I'm seeing a pattern of this, hopefully it will be the norm soon.
 » 3 недели назад, # |   +5 E = obvious treap: 233471686
•  » » 3 недели назад, # ^ |   +81 That's like using a bazooka to kill an ant
•  » » 3 недели назад, # ^ |   0 you should learn how works std::set
•  » » » 3 недели назад, # ^ |   0 You are right. Often I write treap, and then realize that using set is enough
•  » » » » 3 недели назад, # ^ |   0 But in this problem, I used treap with implicit key, which cannot be replaced with std::set
•  » » 3 недели назад, # ^ |   +5 segtree also works good here
•  » » 3 недели назад, # ^ |   +5 I knew there will be overkillers! When I was making a test solutions, I typed a segtree of 260 lines.
•  » » » 3 недели назад, # ^ |   0 Great! Share your code plz
•  » » 3 недели назад, # ^ |   +5 normal vectors are also good.
 » 3 недели назад, # |   -17 problem B only has around 2500-2600 solves accepted solves. Div2B shouldnt have this low solves. I didnt like this round.
•  » » 3 недели назад, # ^ | ← 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 недели назад, # |   +8 B problem -- SEE HERE
•  » » 3 недели назад, # ^ |   0 exact same problem
 » 3 недели назад, # |   -9 In 1898C — Colourful Grid editorial solution:The bottom right 3 colours are misplaced. Please fix it.
•  » » 3 недели назад, # ^ |   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 недели назад, # ^ |   0 Ohh yeah that makes sense. Sorry.
•  » » » 3 недели назад, # ^ |   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 недели назад, # ^ | ← 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 дней назад, # ^ | ← 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 недели назад, # |   0 why B is too hard?
•  » » 3 недели назад, # ^ |   0 Because it is greedy algorithm, as I can see
•  » » » 3 недели назад, # ^ |   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 недели назад, # |   0 Will you add solutions in Russian?
•  » » 3 недели назад, # ^ |   0 But also thanks)
 » 3 недели назад, # |   -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 недели назад, # ^ | ← Rev. 2 →   +28 LOL. You don't even know how hard Div 1 is. (I don't either)
•  » » 3 недели назад, # ^ |   0 Fun fact: we dropped the original F because it was googleable.
•  » » » 3 недели назад, # ^ |   0 what about the B?
•  » » » » 3 недели назад, # ^ |   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 недели назад, # ^ |   +1 That a perfect solution for a easy problem=)) I love you because you provide me a good solution<33
•  » » » » » » 3 недели назад, # ^ |   0 Thank!
•  » » » » » 3 недели назад, # ^ |   +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 недели назад, # ^ |   +1 Well, your solution is very optimate! Thank for a good solution!
•  » » » » » » » 3 недели назад, # ^ |   +1 np
 » 3 недели назад, # | ← 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 недели назад, # ^ |   +34 bro your profile picture is insane
•  » » » 3 недели назад, # ^ |   +23 your pic is insane too bro
•  » » » » 3 недели назад, # ^ |   +23 bro your is also really cool
•  » » » » » 3 недели назад, # ^ |   +12 bro your profile picture is insane too, what a coincidence!
•  » » 3 недели назад, # ^ | ← 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 недели назад, # ^ |   0 how did u determine that authors knew it?
•  » » » 3 недели назад, # ^ |   0 their solutions are almost same
•  » » 3 недели назад, # ^ | ← Rev. 2 →   +7 Isn't they different? Ideas are not the same. I knew for that problem before our round.
•  » » » 3 недели назад, # ^ |   +7 I knew about the task and informed the rest of the team, but we concluded that they were not similar enough.
•  » » » » 3 недели назад, # ^ |   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 недели назад, # ^ |   0 imo idea for both of them is to represent given value into sum of lengths of segments
•  » » 3 недели назад, # ^ |   -28 Crazy, you still used it in a contest but just changed the min to max bruh
 » 3 недели назад, # |   +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 недели назад, # ^ | ← Rev. 2 →   -24 (deleted)
 » 3 недели назад, # |   +3 When I registered for this round, I thought I was registering for Div 2, not Educational
 » 3 недели назад, # |   +16 Why is this editorial downvoted? Is it because problem B is repeated (from what I've read in some comments)?
 » 3 недели назад, # |   0 A < C < E < D < B
•  » » 3 недели назад, # ^ |   0 Observing the testing, it would be said that this time it was a rather subjective thing. Anyways, thanks for your feedback!
•  » » 3 недели назад, # ^ |   +8 A < B < E < D < C
 » 3 недели назад, # |   +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 недели назад, # |   0 i didnt enjoy the round, im sorry :(
 » 3 недели назад, # |   0 I think B and D have appeared before
 » 3 недели назад, # |   +7 what a fantastic well-made problems ?? I'm really impressed and horribly depressed ....
 » 3 недели назад, # |   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 недели назад, # ^ |   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 недели назад, # ^ | ← Rev. 2 →   +3 Yep, I see now I missed the edge in the square of bottom right corner, thanks
 » 3 недели назад, # |   -36 Very balanced problems! (sarcasm)
 » 3 недели назад, # |   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 недели назад, # ^ |   0 Assume you have 18 6 Then you have to split 18 to 6 6 6
 » 3 недели назад, # |   0 didn't my favorite one.
 » 3 недели назад, # |   0 Можете объяснить, что означает формула k=a(i-1)/a(i). Я пытался решить таким образом: 1 4 4 3 5 7 6: отрезок 1 2 (до а(i-1) > a(i) и второй отрезок: 1 5, в итоге: от 1 до 2: sum = 2, от 3 до 5 (в отрезке от 1 до 5): sum = 3, и в этом же отрезке 1 2 пересекается, поэтому 2^2 = 4, и все сложить: 9. Но походу такое решение сложное и возможно неверное. Поясните пожалуйста, решение к задаче B. Спасибо!
 » 3 недели назад, # | ← Rev. 2 →   +1 im dumb and i apologize
 » 3 недели назад, # |   0 This is the exact same problem as B: https://leetcode.com/problems/minimum-replacements-to-sort-the-array/
 » 3 недели назад, # |   +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 недели назад, # ^ |   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 недели назад, # ^ |   0 the author knowing it, and then too allowing this. great contest!!
•  » » 3 недели назад, # ^ |   +9 Can one of the authors respond? Like, isn't it a serious accusation? Did the coordinator know about that?
 » 3 недели назад, # |   +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 недели назад, # ^ |   +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 недели назад, # | ← 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 недели назад, # ^ |   0 I solved this way too
•  » » 3 недели назад, # ^ |   +11 I have just upsolved problem D based on your method! Thank you for your detail explanation!
 » 3 недели назад, # | ← Rev. 2 →   +2 im dumb and i apologize
 » 3 недели назад, # |   -8 Your solution for 1898C — Colorful Grid does not work for the edge case m=2, k=(m-1+n-1)+2
•  » » 3 недели назад, # ^ |   +11 3 <= m, n <= 16.
•  » » » 3 недели назад, # ^ |   0 thanks. I misread and solved it for m, n >= 2 :p
 » 3 недели назад, # |   -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 недели назад, # |   +51 Why so many dislikes? Problems are hard but good.
•  » » 3 недели назад, # ^ |   +13 I don't like the editorials. For example problem C editorial doesn't have explanation at all.
•  » » » 3 недели назад, # ^ |   +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 недели назад, # ^ |   0 Yeah but not everyone understands from the picture. Also they should explain how they got to the picture.
•  » » » » » 3 недели назад, # ^ |   0 Bro I have question,why we are using mass reduction in spacecrafts wouldn't radiation pressure will be better option?
•  » » » » » » 3 недели назад, # ^ |   0 yes
•  » » » » » » » 3 недели назад, # ^ |   0 So why don't we work on radiation pressure to use it on spacecrafts
•  » » » » » » » » 3 недели назад, # ^ |   0 idk
•  » » 3 недели назад, # ^ |   -8 B, D are copied.
 » 3 недели назад, # |   -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 недели назад, # ^ |   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 недели назад, # | ← Rev. 2 →   -8 E could have been better, a little bit too detailed sample testcases for a div2E.
 » 3 недели назад, # |   0 Can someone tell me why I got 'Idleness limit exceeded' in my submission? I couldn't get it. Thanks!233470642
•  » » 3 недели назад, # ^ |   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 недели назад, # |   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 недели назад, # |   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 недели назад, # |   +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 недели назад, # ^ |   +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 недели назад, # ^ | ← Rev. 2 →   0 True, I did this in my solution and it worked, well I didn't split according to i-th bit
•  » » » 3 недели назад, # ^ |   +14 Oh, yes, that's great. (I guess, there are at most $2 \cdot (n + m) - 4$ exits though but whatever).
 » 3 недели назад, # |   0 https://leetcode.com/problems/minimum-replacements-to-sort-the-array/ Problem B is found on leetcode. This is unfair !
 » 3 недели назад, # |   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 недели назад, # |   +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 недели назад, # ^ |   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 недели назад, # | ← 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 недели назад, # ^ | ← 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 недели назад, # |   +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 недели назад, # |   +7 This contest stole some problem. It is stupid and should be unrated.
•  » » 3 недели назад, # ^ |   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 недели назад, # ^ | ← 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 недели назад, # ^ |   0 ok, that may be true, but just don't roast 'em that bad
 » 3 недели назад, # |   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 недели назад, # |   -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 недели назад, # ^ |   0 split 20 into k parts(k=4) -> 5 5 5 5
 » 3 недели назад, # | ← 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 недели назад, # ^ | ← Rev. 2 →   0 17 -> 4 4 4 57 -> 3 4so，3 7 17 5 -> 3 3 4 4 4 4 5 5
•  » » » 3 недели назад, # ^ |   0 thanks dude
 » 3 недели назад, # |   0 Will be russian translations?
 » 3 недели назад, # |   0 if i get first problem code, that will be easier to understand
 » 3 недели назад, # |   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 недели назад, # |   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 недели назад, # ^ |   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 недели назад, # ^ | ← 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 недели назад, # ^ |   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 недели назад, # ^ |   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 недели назад, # ^ |   0 Ok, thank you very much for the reply and clearing the doubt.
 » 3 недели назад, # |   -8 Well B is just a leetcode problem.Link
 » 3 недели назад, # |   0 Thanks for the fast editorial.
 » 3 недели назад, # |   0 greedy algorithm is so hard
 » 3 недели назад, # |   +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 недели назад, # | ← Rev. 2 →   0 A simpler approach to problem C : 233694952
•  » » 3 недели назад, # ^ |   0 nice solution! how did you come up with this?
•  » » » 2 недели назад, # ^ | ← 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 недели назад, # ^ |   0 thanks
 » 3 недели назад, # |   0 Where can i attempt bonus problem??
 » 3 недели назад, # |   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 недели назад, # ^ |   0 Check your output on the fourth test.
•  » » » 2 недели назад, # ^ |   0 Thank you, got it
 » 3 недели назад, # |   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 дней назад, # |   0 Any idea to solve the bonus for problem B? Thanks in advance!
•  » » 10 дней назад, # ^ |   0 Did you got the the solution for bonus part of problem B?
 » 13 дней назад, # |   0 Problem c can't go from 1 to 2, and then go from 2 to 1 again.
 » 11 дней назад, # |   0 please can anyone explain problem C
 » 10 дней назад, # | ← Rev. 3 →   0 ELDRVD and nosk1ll , would you please tell how to solve bonus part of problem B?
 » 10 дней назад, # | ← 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 дней назад, # |   0 how to solve bonus problem E?
 » 5 дней назад, # |   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