n0sk1ll's blog

By n0sk1ll, history, 15 months ago, In English

1898A - Milica and String

Author: n0sk1ll

Hint
Solution
Bonus

1898B - Milena and Admirer

Author: BULLMCHOW & n0sk1ll

Hint
Solution
Bonus

1898C - Colorful Grid

Author: n0sk1ll

Hint
Solution
Bonus

1898D - Absolute Beauty

Author: n0sk1ll

Hint
Solution
Bonus

1898E - Sofia and Strings

Author: BULLMCHOW

Hint
Solution
Bonus

1898F - Vova Escapes the Matrix

Author: n0sk1ll

Hint
Solution
Bonus
  • Vote: I like it
  • +124
  • Vote: I do not like it

| Write comment?
»
13 months ago, # |
  Vote: I like it +25 Vote: I do not like it

Lightning speed editorial!

Thanks for the greatly balanced round !

»
13 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    13 months ago, # ^ |
    Rev. 3   Vote: I like it 0 Vote: I do not like it

    I think this is a breaking testcase: NIL (sorry false statement, but it was what broke my code which failed on testcase 3 also)

  • »
    »
    13 months ago, # ^ |
      Vote: I like it +2 Vote: I do not like it

    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]

    • »
      »
      »
      13 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Even I was getting the same wrong answer. Thanks for pointing out the mistake!

»
13 months ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

Delete

»
13 months ago, # |
  Vote: I like it +5 Vote: I do not like it

Thanks for preparing the editorial beforehand! I'm seeing a pattern of this, hopefully it will be the norm soon.

»
13 months ago, # |
  Vote: I like it +5 Vote: I do not like it

E = obvious treap: 233471686

  • »
    »
    13 months ago, # ^ |
      Vote: I like it +81 Vote: I do not like it

    That's like using a bazooka to kill an ant

  • »
    »
    13 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    you should learn how works std::set

    • »
      »
      »
      13 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      You are right. Often I write treap, and then realize that using set is enough

      • »
        »
        »
        »
        13 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        But in this problem, I used treap with implicit key, which cannot be replaced with std::set

  • »
    »
    13 months ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

    segtree also works good here

  • »
    »
    13 months ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

    I knew there will be overkillers! When I was making a test solutions, I typed a segtree of 260 lines.

  • »
    »
    13 months ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

    normal vectors are also good.

»
13 months ago, # |
  Vote: I like it -17 Vote: I do not like it

problem B only has around 2500-2600 solves accepted solves. Div2B shouldnt have this low solves. I didnt like this round.

  • »
    »
    13 months ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    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

»
13 months ago, # |
  Vote: I like it +8 Vote: I do not like it

B problem -- SEE HERE

»
13 months ago, # |
Rev. 2   Vote: I like it -9 Vote: I do not like it

[redacted]

  • »
    »
    13 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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).

    • »
      »
      »
      13 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Ohh yeah that makes sense. Sorry.

    • »
      »
      »
      13 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      cant you just use top left loop for 2 also i mean only 2 additioanal sides are only added if you go downfirst

      • »
        »
        »
        »
        13 months ago, # ^ |
        Rev. 3   Vote: I like it 0 Vote: I do not like it

        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 months ago, # |
  Vote: I like it 0 Vote: I do not like it

why B is too hard?

  • »
    »
    13 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Because it is greedy algorithm, as I can see

    • »
      »
      »
      13 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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

»
13 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Will you add solutions in Russian?

»
13 months ago, # |
Rev. 2   Vote: I like it +51 Vote: I do not like it

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 :)

n0sk1ll BULLMCHOW

  • »
    »
    13 months ago, # ^ |
      Vote: I like it +34 Vote: I do not like it

    bro your profile picture is insane

  • »
    »
    13 months ago, # ^ |
    Rev. 2   Vote: I like it +7 Vote: I do not like it

    Isn't they different? Ideas are not the same. I knew for that problem before our round.

    • »
      »
      »
      13 months ago, # ^ |
        Vote: I like it +7 Vote: I do not like it

      I knew about the task and informed the rest of the team, but we concluded that they were not similar enough.

    • »
      »
      »
      13 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      imo idea for both of them is to represent given value into sum of lengths of segments

»
13 months ago, # |
  Vote: I like it +12 Vote: I do not like it

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.

»
13 months ago, # |
  Vote: I like it +3 Vote: I do not like it

When I registered for this round, I thought I was registering for Div 2, not Educational

»
13 months ago, # |
  Vote: I like it +16 Vote: I do not like it

Why is this editorial downvoted? Is it because problem B is repeated (from what I've read in some comments)?

»
13 months ago, # |
  Vote: I like it 0 Vote: I do not like it

A < C < E < D < B

  • »
    »
    13 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Observing the testing, it would be said that this time it was a rather subjective thing. Anyways, thanks for your feedback!

  • »
    »
    13 months ago, # ^ |
      Vote: I like it +8 Vote: I do not like it

    A < B < E < D < C

»
13 months ago, # |
Rev. 2   Vote: I like it +10 Vote: I do not like it

.

»
13 months ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

.

»
13 months ago, # |
  Vote: I like it +7 Vote: I do not like it

what a fantastic well-made problems ?? I'm really impressed and horribly depressed ....

»
13 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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
  • »
    »
    13 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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?

    • »
      »
      »
      13 months ago, # ^ |
      Rev. 2   Vote: I like it +3 Vote: I do not like it

      Yep, I see now I missed the edge in the square of bottom right corner, thanks

»
13 months ago, # |
  Vote: I like it -36 Vote: I do not like it

Very balanced problems! (sarcasm)

»
13 months ago, # |
  Vote: I like it 0 Vote: I do not like it

didn't my favorite one.

»
13 months ago, # |
Rev. 2   Vote: I like it +1 Vote: I do not like it

im dumb and i apologize

»
13 months ago, # |
  Vote: I like it +19 Vote: I do not like it

B appeared as a subproblem in a different problem (https://codeforces.net/contest/1603/problem/C), and n0sk1ll even solved it during the contest (https://codeforces.net/contest/1603/submission/133683209).

Any comments from the authors?

  • »
    »
    13 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    wow such an amazing round, problem b appearing two other problems, one of them is sub-problem the other is the exact copy

  • »
    »
    13 months ago, # ^ |
      Vote: I like it +9 Vote: I do not like it

    Can one of the authors respond? Like, isn't it a serious accusation? Did the coordinator know about that?

    n0sk1ll BULLMCHOW

»
13 months ago, # |
  Vote: I like it +1 Vote: I do not like it

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't

What 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.

  • »
    »
    13 months ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    ".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

»
13 months ago, # |
Rev. 3   Vote: I like it +9 Vote: I do not like it

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)

  • »
    »
    13 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I solved this way too

  • »
    »
    13 months ago, # ^ |
      Vote: I like it +11 Vote: I do not like it

    I have just upsolved problem D based on your method! Thank you for your detail explanation!

  • »
    »
    12 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Why does it not work for minimization?

  • »
    »
    8 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    What is A B C -> "where A,B,C are known "constants".

    • »
      »
      »
      7 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      $$$A = a_i$$$, $$$B = b_i$$$ and $$$C = |a_i - b_i|$$$, those are constant for a fixed $$$i$$$.

»
13 months ago, # |
Rev. 2   Vote: I like it +2 Vote: I do not like it

im dumb and i apologize

»
13 months ago, # |
  Vote: I like it -8 Vote: I do not like it

Your solution for 1898C — Colorful Grid does not work for the edge case m=2, k=(m-1+n-1)+2

»
13 months ago, # |
  Vote: I like it -12 Vote: I do not like it

The C question was retarded. If you keep an implementation question try to keep it so that atleast some good pattern shows up.

»
13 months ago, # |
  Vote: I like it +51 Vote: I do not like it

Why so many dislikes? Problems are hard but good.

  • »
    »
    13 months ago, # ^ |
      Vote: I like it +13 Vote: I do not like it

    I don't like the editorials. For example problem C editorial doesn't have explanation at all.

    • »
      »
      »
      13 months ago, # ^ |
        Vote: I like it +13 Vote: I do not like it

      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

      • »
        »
        »
        »
        13 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Yeah but not everyone understands from the picture. Also they should explain how they got to the picture.

        • »
          »
          »
          »
          »
          13 months ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          Bro I have question,why we are using mass reduction in spacecrafts wouldn't radiation pressure will be better option?

          • »
            »
            »
            »
            »
            »
            13 months ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            yes

            • »
              »
              »
              »
              »
              »
              »
              13 months ago, # ^ |
                Vote: I like it 0 Vote: I do not like it

              So why don't we work on radiation pressure to use it on spacecrafts

»
13 months ago, # |
  Vote: I like it -13 Vote: I do not like it

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.

  • »
    »
    13 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

»
13 months ago, # |
Rev. 2   Vote: I like it -8 Vote: I do not like it

E could have been better, a little bit too detailed sample testcases for a div2E.

»
13 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Can someone tell me why I got 'Idleness limit exceeded' in my submission? I couldn't get it. Thanks!

233470642

  • »
    »
    13 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Your code is a TLE but since you are using cerr, you are getting Idleness limit exceeded.

    Here it is without cerrs: 233490794

»
13 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
13 months ago, # |
  Vote: I like it +100 Vote: I do not like it

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$$$.

  • »
    »
    13 months ago, # ^ |
      Vote: I like it +61 Vote: I do not like it

    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.

    • »
      »
      »
      13 months ago, # ^ |
      Rev. 2   Vote: I like it 0 Vote: I do not like it

      True, I did this in my solution and it worked, well I didn't split according to i-th bit

    • »
      »
      »
      13 months ago, # ^ |
        Vote: I like it +14 Vote: I do not like it

      Oh, yes, that's great. (I guess, there are at most $$$2 \cdot (n + m) - 4$$$ exits though but whatever).

»
13 months ago, # |
  Vote: I like it +11 Vote: I do not like it

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.

  • »
    »
    13 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

»
13 months ago, # |
Rev. 4   Vote: I like it +3 Vote: I do not like it

Solution for D

Code

submission 233513167

Can someone help with the proof of this solution!

i generalized all cases as A1<=B2 and A2>=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

  • »
    »
    12 months ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    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://codeforces.net/contest/1898/submission/233522779

»
13 months ago, # |
  Vote: I like it +3 Vote: I do not like it

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.net/contest/1898/submission/233490749

»
13 months ago, # |
  Vote: I like it +7 Vote: I do not like it

This contest stole some problem. It is stupid and should be unrated.

»
13 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Will be russian translations?

»
13 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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 ??

  • »
    »
    13 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

    • »
      »
      »
      13 months ago, # ^ |
      Rev. 5   Vote: I like it 0 Vote: I do not like it

      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 ?

      • »
        »
        »
        »
        13 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        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.

        • »
          »
          »
          »
          »
          13 months ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          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.

»
13 months ago, # |
  Vote: I like it -8 Vote: I do not like it

Well B is just a leetcode problem.

Link

»
13 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Thanks for the fast editorial.

»
13 months ago, # |
  Vote: I like it 0 Vote: I do not like it

greedy algorithm is so hard

»
13 months ago, # |
  Vote: I like it +8 Vote: I do not like it

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.

»
13 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Where can i attempt bonus problem??

»
13 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
13 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Any idea to solve the bonus for problem B? Thanks in advance!

  • »
    »
    13 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Did you got the the solution for bonus part of problem B?

»
13 months ago, # |
Rev. 3   Vote: I like it 0 Vote: I do not like it

ELDRVD and nosk1ll , would you please tell how to solve bonus part of problem B?

»
13 months ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

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+6

k-(n+m) is multiple of 4 then k = n+m+4

k-(n+m) is multiple of 2 then k = n+m+2

Now 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.

»
13 months ago, # |
  Vote: I like it 0 Vote: I do not like it

how to solve bonus problem E?

»
12 months ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

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.

»
11 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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.

»
11 months ago, # |
  Vote: I like it 0 Vote: I do not like it

anyone can give hint for bonus problem in B

»
2 months ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

.

»
2 months ago, # |
Rev. 3   Vote: I like it 0 Vote: I do not like it

..