Codeforces functionality may be limited from June 18, 19:00 (UTC) to June 19, 3:00 AM (UTC) due to technical maintenance. Polygon will work as usual. ×

n0sk1ll's blog

By n0sk1ll, history, 9 months ago,

1898A - Milica and String

Author: n0sk1ll

Hint
Solution
Bonus

Author: BULLMCHOW & n0sk1ll

Hint
Solution
Bonus

Author: n0sk1ll

Hint
Solution
Bonus

Author: n0sk1ll

Hint
Solution
Bonus

1898E - Sofia and Strings

Author: BULLMCHOW

Hint
Solution
Bonus

1898F - Vova Escapes the Matrix

Author: n0sk1ll

Hint
Solution
Bonus
• +124

 » 7 months ago, # |   +25 Lightning speed editorial!Thanks for the greatly balanced round !
•  » » 7 months ago, # ^ |   0 The bonus problems don't have a tutorial?
 » 7 months ago, # | ← Rev. 3 →   -39 Can't say it's a good competitionP.S. Why is there no implementation?
•  » » 7 months ago, # ^ |   -25 They didn't even bother to solve their own unbalanced problems lol (joke)
•  » » » 7 months ago, # ^ |   0 problems were pretty balanced, except C!=D
 » 7 months 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
•  » » 7 months 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)
•  » » 7 months 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]
•  » » » 7 months ago, # ^ |   0 That helps, thank you!
•  » » » 7 months ago, # ^ |   0 Even I was getting the same wrong answer. Thanks for pointing out the mistake!
 » 7 months ago, # | ← Rev. 2 →   0 Delete
•  » » 7 months ago, # ^ |   0 Would you like to share the link please?
•  » » » 7 months ago, # ^ | ← Rev. 2 →   0 delete
•  » » » » 7 months ago, # ^ |   0 Thanks for the link , i was trying to find this problem that i remember solving
•  » » 7 months ago, # ^ |   0 us
 » 7 months ago, # |   0 not able to figure out even... Milica and String ;(
•  » » 7 months ago, # ^ |   0 its okay , you are new even I can only solve A
 » 7 months ago, # |   +5 Thanks for preparing the editorial beforehand! I'm seeing a pattern of this, hopefully it will be the norm soon.
 » 7 months ago, # |   +5 E = obvious treap: 233471686
•  » » 7 months ago, # ^ |   +81 That's like using a bazooka to kill an ant
•  » » 7 months ago, # ^ |   0 you should learn how works std::set
•  » » » 7 months ago, # ^ |   0 You are right. Often I write treap, and then realize that using set is enough
•  » » » » 7 months ago, # ^ |   0 But in this problem, I used treap with implicit key, which cannot be replaced with std::set
•  » » 7 months ago, # ^ |   +5 segtree also works good here
•  » » 7 months ago, # ^ |   +5 I knew there will be overkillers! When I was making a test solutions, I typed a segtree of 260 lines.
•  » » » 7 months ago, # ^ |   0 Great! Share your code plz
•  » » 7 months ago, # ^ |   +5 normal vectors are also good.
 » 7 months ago, # |   -17 problem B only has around 2500-2600 solves accepted solves. Div2B shouldnt have this low solves. I didnt like this round.
•  » » 7 months 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
•  » » » 2 months ago, # ^ |   -8 i couldnt code it
 » 7 months ago, # |   +8 B problem -- SEE HERE
•  » » 7 months ago, # ^ |   0 exact same problem
 » 7 months ago, # |   -9 In 1898C — Colourful Grid editorial solution:The bottom right 3 colours are misplaced. Please fix it.
•  » » 7 months 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).
•  » » » 7 months ago, # ^ |   0 Ohh yeah that makes sense. Sorry.
•  » » » 7 months 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
•  » » » » 7 months 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!
•  » » » » 7 months 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.
 » 7 months ago, # |   0 why B is too hard?
•  » » 7 months ago, # ^ |   0 Because it is greedy algorithm, as I can see
•  » » » 7 months 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
 » 7 months ago, # |   0 Will you add solutions in Russian?
•  » » 7 months ago, # ^ |   0 But also thanks)
 » 7 months 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 :)
•  » » 7 months ago, # ^ |   +34 bro your profile picture is insane
•  » » » 7 months ago, # ^ |   +23 your pic is insane too bro
•  » » » » 7 months ago, # ^ |   +23 bro your is also really cool
•  » » » » » 7 months ago, # ^ |   +12 bro your profile picture is insane too, what a coincidence!
•  » » 7 months ago, # ^ | ← Rev. 2 →   +7 Isn't they different? Ideas are not the same. I knew for that problem before our round.
•  » » » 7 months ago, # ^ |   +7 I knew about the task and informed the rest of the team, but we concluded that they were not similar enough.
•  » » » 7 months ago, # ^ |   0 imo idea for both of them is to represent given value into sum of lengths of segments
•  » » 7 months ago, # ^ |   -28 Crazy, you still used it in a contest but just changed the min to max bruh
 » 7 months 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.
•  » » 7 months ago, # ^ | ← Rev. 2 →   -24 (deleted)
 » 7 months ago, # |   +3 When I registered for this round, I thought I was registering for Div 2, not Educational
 » 7 months ago, # |   +16 Why is this editorial downvoted? Is it because problem B is repeated (from what I've read in some comments)?
 » 7 months ago, # |   0 A < C < E < D < B
•  » » 7 months ago, # ^ |   0 Observing the testing, it would be said that this time it was a rather subjective thing. Anyways, thanks for your feedback!
•  » » 7 months ago, # ^ |   +8 A < B < E < D < C
 » 7 months 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 :)
 » 7 months ago, # |   0 i didnt enjoy the round, im sorry :(
 » 7 months ago, # | ← Rev. 2 →   0 .
 » 7 months ago, # |   +7 what a fantastic well-made problems ?? I'm really impressed and horribly depressed ....
 » 7 months 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 
•  » » 7 months 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?
•  » » » 7 months ago, # ^ | ← Rev. 2 →   +3 Yep, I see now I missed the edge in the square of bottom right corner, thanks
 » 7 months ago, # |   -36 Very balanced problems! (sarcasm)
 » 7 months 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 !
•  » » 7 months ago, # ^ |   0 Assume you have 18 6 Then you have to split 18 to 6 6 6
 » 7 months ago, # |   0 didn't my favorite one.
 » 7 months ago, # | ← Rev. 2 →   +1 im dumb and i apologize
 » 7 months ago, # |   0 This is the exact same problem as B: https://leetcode.com/problems/minimum-replacements-to-sort-the-array/
 » 7 months ago, # |   +19 B appeared as a subproblem in a different problem (https://mirror.codeforces.com/contest/1603/problem/C), and n0sk1ll even solved it during the contest (https://mirror.codeforces.com/contest/1603/submission/133683209).Any comments from the authors?
•  » » 7 months 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
•  » » 7 months ago, # ^ |   0 the author knowing it, and then too allowing this. great contest!!
•  » » 7 months ago, # ^ |   +9 Can one of the authors respond? Like, isn't it a serious accusation? Did the coordinator know about that?
 » 7 months 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.
•  » » 7 months 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
 » 7 months 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)
•  » » 7 months ago, # ^ |   0 I solved this way too
•  » » 7 months ago, # ^ |   +11 I have just upsolved problem D based on your method! Thank you for your detail explanation!
•  » » 6 months ago, # ^ |   0 Why does it not work for minimization?
•  » » 2 months ago, # ^ |   0 What is A B C -> "where A,B,C are known "constants".
•  » » » 3 weeks ago, # ^ |   0 $A = a_i$, $B = b_i$ and $C = |a_i - b_i|$, those are constant for a fixed $i$.
 » 7 months ago, # | ← Rev. 2 →   +2 im dumb and i apologize
 » 7 months ago, # |   -8 Your solution for 1898C — Colorful Grid does not work for the edge case m=2, k=(m-1+n-1)+2
•  » » 7 months ago, # ^ |   +11 3 <= m, n <= 16.
•  » » » 7 months ago, # ^ |   0 thanks. I misread and solved it for m, n >= 2 :p
 » 7 months 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.
 » 7 months ago, # |   +51 Why so many dislikes? Problems are hard but good.
•  » » 7 months ago, # ^ |   +13 I don't like the editorials. For example problem C editorial doesn't have explanation at all.
•  » » » 7 months 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
•  » » » » 7 months ago, # ^ |   0 Yeah but not everyone understands from the picture. Also they should explain how they got to the picture.
•  » » » » » 7 months ago, # ^ |   0 Bro I have question,why we are using mass reduction in spacecrafts wouldn't radiation pressure will be better option?
•  » » » » » » 7 months ago, # ^ |   0 yes
•  » » » » » » » 7 months ago, # ^ |   0 So why don't we work on radiation pressure to use it on spacecrafts
•  » » » » » » » » 7 months ago, # ^ |   0 idk
•  » » 7 months ago, # ^ |   -8 B, D are copied.
 » 7 months 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.
•  » » 7 months 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.
 » 7 months ago, # | ← Rev. 2 →   -8 E could have been better, a little bit too detailed sample testcases for a div2E.
 » 7 months ago, # |   0 Can someone tell me why I got 'Idleness limit exceeded' in my submission? I couldn't get it. Thanks!233470642
•  » » 7 months 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
 » 7 months 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
 » 7 months 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
 » 7 months 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$.
•  » » 7 months 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.
•  » » » 7 months ago, # ^ | ← Rev. 2 →   0 True, I did this in my solution and it worked, well I didn't split according to i-th bit
•  » » » 7 months ago, # ^ |   +14 Oh, yes, that's great. (I guess, there are at most $2 \cdot (n + m) - 4$ exits though but whatever).
 » 7 months ago, # |   0 https://leetcode.com/problems/minimum-replacements-to-sort-the-array/ Problem B is found on leetcode. This is unfair !
 » 7 months 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.
 » 7 months 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.
•  » » 7 months 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.
 » 7 months 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
•  » » 7 months 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
•  » » 5 months ago, # ^ |   +3 The proof is almost complete.Since the left and right terms are independent, they can be computed separately, and later combined to optimize the solution **** Think of having one loop for MAX and another for MIN. Since you want to maximize contributions, you want the to take the best combination (keeping track of max for all i).Might be easier to grasp if you convert the MIN into a max of the negative value. See: https://mirror.codeforces.com/contest/1898/submission/233522779
 » 7 months 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/.
 » 7 months ago, # |   +7 This contest stole some problem. It is stupid and should be unrated.
•  » » 7 months 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.
•  » » » 7 months 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://mirror.codeforces.com/blog/entry/119772#comment-1067920
•  » » » » 7 months ago, # ^ |   0 ok, that may be true, but just don't roast 'em that bad
 » 7 months 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
 » 7 months 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
•  » » 7 months ago, # ^ |   0 split 20 into k parts(k=4) -> 5 5 5 5
 » 7 months 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
•  » » 7 months ago, # ^ | ← Rev. 2 →   0 17 -> 4 4 4 57 -> 3 4so，3 7 17 5 -> 3 3 4 4 4 4 5 5
•  » » » 7 months ago, # ^ |   0 thanks dude
 » 7 months ago, # |   0 Will be russian translations?
 » 7 months ago, # |   0 if i get first problem code, that will be easier to understand
 » 7 months 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!
 » 7 months 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 ??
•  » » 7 months 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.
•  » » » 7 months 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 ?
•  » » » » 7 months 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.
•  » » » » » 7 months 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.
•  » » » » » » 7 months ago, # ^ |   0 Ok, thank you very much for the reply and clearing the doubt.
 » 7 months ago, # |   -8 Well B is just a leetcode problem.Link
 » 7 months ago, # |   0 Thanks for the fast editorial.
 » 7 months ago, # |   0 greedy algorithm is so hard
 » 7 months 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.
 » 7 months ago, # | ← Rev. 2 →   0 A simpler approach to problem C : 233694952
•  » » 7 months ago, # ^ |   0 nice solution! how did you come up with this?
•  » » » 7 months 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
•  » » » » 7 months ago, # ^ |   0 thanks
 » 7 months ago, # |   0 Where can i attempt bonus problem??
 » 7 months 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
•  » » 7 months ago, # ^ |   0 Check your output on the fourth test.
•  » » » 7 months ago, # ^ |   0 Thank you, got it
 » 7 months 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?
 » 7 months ago, # |   0 Any idea to solve the bonus for problem B? Thanks in advance!
•  » » 7 months ago, # ^ |   0 Did you got the the solution for bonus part of problem B?
 » 7 months ago, # |   0 Problem c can't go from 1 to 2, and then go from 2 to 1 again.
 » 7 months ago, # |   0 please can anyone explain problem C
 » 7 months ago, # | ← Rev. 3 →   0 ELDRVD and nosk1ll , would you please tell how to solve bonus part of problem B?
 » 7 months 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.
 » 7 months ago, # |   0 how to solve bonus problem E?
 » 6 months ago, # |   0 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
 » 6 months ago, # | ← Rev. 2 →   0 Can someone intuitively explain why it's okay to swap a[i] and b[i] in problem D? I did some casework and am convinced that it is correct, but I can't wrap my head around it intuitively.
 » 5 months ago, # |   0 I have no idea why my solution 241233386 doesn't work for 1898D - Absolute Beauty. Please point out the issue. Thank you![Explanation] Let $S = \sum{|a_i - b_i|}$. This represents the initial absolute beauty. Let $S(i, j)$ denote the beauty after swapping elements at indices $i$ and $j$. We can express $S(i, j) = S + \delta(i, j)$, where $\delta(i, j) = |a_i - b_j| + |a_j - b_i| - |a_i - b_i| - |a_j - b_j|.$Hence, it suffices to maximize $\delta(i, j)$. Now, fixing index $i$ and considering $\delta(i, j)$ as a function of $j$, we can identify four possible expressions after removing absolute value brackets: $\delta(i, j) = \alpha_1 a_j + \beta_1,$ $\delta(i, j) = \alpha_2 b_j + \beta_2,$ $\delta(i, j) = \alpha_3 (a_j + b_j) + \beta_3,$ $\delta(i, j) = \alpha_4 (a_j - b_j) + \beta_4,$where $a_k$ and $b_k$ are constants. Each expression can be regarded as a linear function of the variables $a_j$, $b_j$, $a_j + b_j$, and $a_j - b_j$, respectively. Since a linear function within an interval takes its maximum at either endpoint, the candidates for $(a_j, b_j)$ to maximize $\delta(i, j)$ are at most 8. (Candidates are to maximize $a_j$, $b_j$, $a_j + b_j$, or $a_j - b_j$, or to minimize one of them). These candidates remain invariant even when iterating over $i$. Therefore, it is sufficient to iterate over $i$, check $8N$ pairs of $(i, j)$, and calculate $\delta(i, j)$ straightforwardly.
 » 5 months ago, # |   0 anyone can give hint for bonus problem in B