maroonrk's blog

By maroonrk, history, 2 months ago, In English

We will hold NOMURA Programming Contest 2021(AtCoder Regular Contest 121).

The point values will be 400-500-500-700-700-800.

We are looking forward to your participation!

 
 
 
 
  • Vote: I like it
  • +129
  • Vote: I do not like it

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

why did so many reds fail to solve D? I think it was very ez lol

my code

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

Bruhhh... I just did some random shit for C XD
Can anyone explain their solution?

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

    Can you elaborate the random shit that you used :)

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

      Lmao

      I iterated $$$n^2$$$ times and maintained a variable for the current parity. Each time I loop through the array I swapped any $$$a_{i} > a_{i + 1}$$$ if $$$i$$$ matched the current parity, if there was no such $$$i$$$ I just swapped the first $$${i}$$$ that matched the current parity and continued to the next iteration.

      Submission

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

        I was also trying to do the same, but it got TLE. can you elaborate on how did you chose any i, when it is not sorted and every ai > ai+1 does not match current parity.

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

          Oh I didn't explain that properly, I edited my comment.

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

          In the case you mentioned if you swap any index that matches current parity from the right it won't cause you TLE I guess.

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

          I changed the first $$$i$$$ which matches parity and $$$a_i > a_{i+1}$$$.

          If there is no such $$$i$$$, then swap the last $$$i$$$ which matches the parity.

          I changed the last and not the first because if you swap the first, then some latter move may try to reverse that swap before looking at the elements at the right of the swap and fall into an infinite cycle.

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

            Can you give an example where it may TLE if we choose to swap first parity matching element?

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

              Try all permutations of size 3, if it passes all those tests, try all the permutations of size 4, it won't pass all of them.

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

My code for B is getting RE on 15 cases. Can somebody help please? I implemented simple two-pointer technique. My Code for B...

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

    The following testcase seems to fail on your solution (expected 999999999900000, output 0): 2 100000 B 1000000000000000 A

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

      Thanks a lot, I had used INT_MAX for infinity as I thought #define int long long will take care. Learnt, a new thing today :')

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

    I believe the problem is line 360 (and similar line), you forget to check that the size is at least 2 when looking at rb[1].

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

      I found my mistake, it was in the INT_MAX. By the way thanks for having a look

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

    My Submission for B

    I made 3 vectors (say $$$V_1$$$, $$$V_2$$$ and $$$V_3$$$) with the $$$a[i]$$$ values of the respective 3 colours and sorted all 3 of them. Then if all of them are of even size you obviously have 0 as your answer other wise I swapped the vectors such that my first two vectors, $$$V_1$$$ & $$$V_2$$$, are of odd size (we will have exactly two vectors with odd size currently).

    Firstly I tried to have one pair in which an element is from $$$V_1$$$ and the other one is from $$$V_2$$$ and the rest will pair with someone having the same colour as their own. For this I iterated $$$V_1$$$ and checked for the first element in $$$V_2$$$ >= $$$V_1[i]$$$ and the first element $$$V_2$$$ < $$$V_1[i]$$$ (if it exists). All this while updating the best answer achieved till now.

    Next I tried to have two pairs where one of them has elements form $$$V_1$$$ & $$$V_3$$$ and the other one has elements from $$$V_2$$$ & $$$V_3$$$. I did this by maintaining two prefix minimums which had the minimum cost of pairing an element of $$$V_3$$$ with an element of $$$V_1$$$ and similarly the minimum cost of pairing an element of $$$V_3$$$ with and element of $$$V_2$$$. I kept updating the best answer while making these prefix minimums.

    Can someone point out if they did something which made the implementation even better :)

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

      same i did bruhh.. but with binary search, but dont know where my code is failing :(

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

        I did the required binary search task but simply calling lower_bound and handling it with iterator. Did you also do it that way ?

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

          no, i did BS with while loop.

          but i think the case u might have missed is, if for a element x[i] u found lower bound as y[j] from other array. then u should check y[j-1] also because at last we have to take min(abs(x[i]-y[j]), x[i]-y[j-1]) as our target is to minimise this difference not to find lower_bound.

          I also missed this, i guess my code also failed because of this only.

          Hope this help ;)

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

      I went through this submission of someone and now I have a doubt , isn't it possible that the element of vector V3 which is responsible for having minimum answer for an element from vector V2 is also responsible for having minimum answer for an element from vector V1 , If possible then in that case wont this solution fail ?

      NEVERMIND , I understood its impossible to have such a case

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

        Why is it impossible??

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

          There are 2 cases , Suppose X is from V1 , Y is from V2 , and Z is from V3 , then if X<Y<Z then always (Y-X)<(Z-X)+(Z-Y) , Now if X<Z<Y , then (Z-X)+(Y-Z)=Y-X , and Y-X is already calculated

»
2 months ago, # |
  Vote: I like it +24 Vote: I do not like it

Am I the only one who felt like B's implementation was cancer? Can anyone share their neat implementation?

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

    My implementation gave runtime error on 15 cases. Can you share yours?

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

      Maybe you forgot one case.

      We check the freq of the colors, one color allways has even freq. If the two other colors also have even freq, ans=0. Else ans is minimum of

      cheapest pair of the two odd colors, or

      sum of cheapest two pairs with first even color and odd color, and second even color and odd color.

      submission which is, well, cancer

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

        Nah man, I had checked all the cases. Using INT_MAX gave me RE as the constraint was upto 10^15. I had a misconception that INT_MAX will change itself according to the data type. I was wrong :(. By the way, thanks a lot

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

        "Sum of cheapest two pairs with first even color and odd color, and second even color and odd color." How are you sure that the same dog (with even color) will not be matched with the other dogs with odd color?

        • »
          »
          »
          »
          »
          3 weeks ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          Well, this is the complecated looking part in the code, you actually have to construct the two cheapest pairs with not the same even dog.

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

    I find min difference of between B & G , B & R and R & G separately. Then we have to deal just for 1G & 1R or 1G & 1B or 1B & 1R.

    Idea
    Solution
  • »
    »
    2 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    submission
  • »
    »
    2 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    My solution is here

    Let $$$b_i$$$ store all $$$a_j$$$ with $$$c_j = i$$$ (with R = 0, G = 1, and B = 2)

    If all $$$b_i$$$ are even, we can pair dogs within the same color and have to left over, so the answer is $$$0$$$.

    Otherwise, there are two indices $$$i$$$ and $$$j$$$, with $$$b_i$$$ and $$$b_j$$$ even. We can try combining two dogs from $$$b_i$$$ and $$$b_j$$$ (with two pointers or binary search). Let $$$k$$$ be the other index that's not $$$i$$$ or $$$j$$$. Notice that combining two dogs from $$$i$$$ and $$$k$$$ and then two more from $$$j$$$ and $$$k$$$ might be better. So you can just try the best ones from $$$i$$$ and $$$j$$$, and the answer is the minimum of this sum and the previous answer.

    Also, there are no edge cases, you can prove that.

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

    Code

    We will end with one of 2 cases, all colors are even or 2 of them are odd.

    The first case has answer 0, but the second has one of two cases to find the minimum answer, you can try to match each element from any of the two odd sets with the nearest one to it in the other set or you can take two elements from the even set and try to match them with the nearest two from the odd sets.

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

    I felt that B was a pretty nice, Atcoder-quality problem. But they didn't have the other case in the samples, which probably screwed a lot of people over.

    For me, A was like cancer. Here's my wack implementation. Those whole 50 minutes were like "Why doesn't this work... Why does it work now?"

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

      Here is a neater one — did not manage to submit during the contest though.

      import sys
      from operator import itemgetter
      from itertools import chain, islice
      
      f = sys.stdin
      next(f)
      a = [tuple(map(int, s.split())) for s in f]
      t = (sorted(a, key=itemgetter(i)) for i in range(2))
      a = {id(x): x for x in chain(*(c[:2] + c[-2:] for c in t))}.values()
      r = sorted(max(abs(x-u), abs(y-v)) for i, (x, y) in enumerate(a)
                 for u, v in islice(a, i))
      print(r[-2])
      
  • »
    »
    2 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Mee toooo

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

    https://atcoder.jp/contests/arc121/submissions/22994246

    This legend really writes the neat code, worth to go through it.

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

solved B, but failed to solve A, and wasted the whole contest. does anyone have a similar experience?

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

What was the hand_01.txt test case for problem A

UPD : Hello camypaper sir, please give me that test file.

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

    Try: 3 1 1 2 2 3 3 the answer should be 1.

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

      Getting the answer as 1 still failing one TC idk what it is

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

      But sir, mine is also giving 1 as you said and expected.
      Submission Link — Click_1
      Test here — Link — Click_2
      lungualex00 give me the exact test case : hand_01.txt please.

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

        I think the ac code of A here can be easier to comprehend,bro: https://paste.ubuntu.com/p/8P9CdMdf4K/

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

        I don't have the testcase; I personally bypassed hand_01.txt using the example already provided. I saw in you code that you handle n=3 differently, which is odd as it shouldn't represent a special handling. The idea in the first place was not to consider the same pair of points twice (once for x-diff and once for y-diff). However, try to work with 4 1 1 2 2 3 3 5 5 which should be answered with 3.

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

    I guess it is that the pair with biggest x-diff also has biggest y-diff

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

      I guess there must be more similar test cases , cause I too got WA on just 1 test case and had to write a completely different code for AC. lol!

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

    Happened with me was trying to resolve it but nothing worked there's just one case always failing

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

    Atcoder TestCases DropBox Link

    Here are all the test cases of Atcoder, ARC 121 tests are also updated

    Hope this may Help u KGECian_23

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

Does anybody has any idea why this code tles in 2000ms in problem E on exactly one test file while this code passes in 20ms (just some small constant optimizations)? .It cost me 30 minutes of penalty

edit:found the mistake

»
2 months ago, # |
  Vote: I like it +15 Vote: I do not like it

What a dumbhead I am, my D's solution is equivalent to the standard one if all $$$a_i>0$$$, and is wrong otherwise. But my stress test data generator only generated data with $$$a_i>0$$$ so I couldn't find the mistake!

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

D has a nice idea but it really seems to be harder than standard-ish E.

D: If we choose which elements to use as part of a pair, then we should pair the first with last etc. That's because if $$$a \le b \le c \le d$$$, then $$$c+d,b+d \le b+c,a+d \le a+c,a+b$$$ — it gives us the tightest intervals [min,max] not just by max-min, but in each value separately. How to deal with $$$k$$$ unpaired elements? Just add $$$k$$$ elements equal to $$$0$$$, then everything is paired. We can bruteforce for each possible $$$k$$$.

E: Inclusion-exclusion DP. For each $$$k$$$, we're looking for the number of subsets of $$$k$$$ vertices which violate the given condition, while ignoring the condition on the remaining $$$N-k$$$. Merging DP for subtrees is convolution-like and when we have a subtree of $$$v$$$ with size $$$s_v$$$, where we put $$$k$$$ of its descendants into the subset, then there are $$$s_v-1-k$$$ values we can't use for $$$a_v$$$ in the permutation if we put $$$v$$$ in the subset too.

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

    And then there's LayCurse who goes and finishes D in 8 minutes.

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

      With that kind of short solution, I'm not surprised. It's the kind of problem where you can see it right away or stay stuck for 2 hours, even at high level.

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

    The idea of adding k zeroes explains why unpaired elements will form a contiguous subarray.

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

    Hi Xellos, I understand that we need to take (a, d) and (b, c). Then could you pls explain how to compute the final answer ? Also when you mention k, k can be only max of 3 right ? as we only 4 elements form a two pair ?

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

      The final answer is computed by bruteforce, $$$k$$$ can be up to $$$N$$$. Remember that $$$O(N^2)$$$ is enough.

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

        To reiterate on the solution, First sort the array. Then for each possible K (where n-K is even and K being the number of unpaired elements), you will select the 1st n-K elements and then pair them as above (1st with (n-K)th, 2nd with (n-K-1)th and so on), then compute the minumum and maximum among both the last K elements and the 1st ((n-K) / 2) pairs. Then print K where the difference is minimum ? Here we take the 1st (n-K) elemnts to form a pair as if we take any other element, either the minimum will be lesser or the maximum will be greater and hence the difference will not be lesser. Is this correct ?

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

          I don't see you using the part "just add $$$k$$$ elements equal to $$$0$$$" from my original comment.

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

            Ah! ok!, so instead of selecting the 1st n-k elements and making pairs, you add k zeros in the beginning ?

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

My C solution fails with 1 WA in small case 1. Can anyone help me debug? I tried all permutations up to size 10. It does the job within N*N.

My Code

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

My Idea For C : Besides The array Having Permutation , Used One More array for Storing Position . Now to Idea is to start Bringing the elements 1 2 3 ... respectively to their position i.e 1 2 3... one by one if(position[i]==i) move ahead for next i otherwise the position of i must Be greater Than i . Now if parity of step_number and position of i are same we can during this step select any index (definitely the one for which parity with step_number is same ,I selected position[i] +2 or position[i]-2) other than position[i] for this step without destroying the initial set sequence upto i-1 . After This the parity of step_number and position[i] become different and we can bring i to index i in position[i]-i steps .But what I said above is will be possible only if position[i]+2<=(n-1) or position[i]-2>=i Otherwise the initial set permutation upto i-1 will have to be changed . To Tackle this we can use the following 5 sequence steps : let x=position[i]-2. x x+1 x x+1 x after these five steps both i and i-1 will get their sorted Position . . we can Use This Examples Sequence to understand This : Permutation = 1 3 2 , steps = 5 indices 1 2 1 2 1. It converts into 1 2 3 (1 and 2 both get their Sorted Position) Here is my submission : https://atcoder.jp/contests/arc121/submissions/23010036 Very Sad That I solved It just by 19:30 submitted without compiling on my ide , It gave CE and just after correcting that it gave AC

»
2 months ago, # |
  Vote: I like it +59 Vote: I do not like it

A very simple observation on problem F:

It's always better to make AND operations first.

Thus a tree is good if and only if after all OR edges are removed, at least one component is all $$$1$$$.

You can also prove this by induction.

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

Allowing houses in problem A to have identical coordinates was a cruel and unusual punishment!

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

Can someone explain why there are at most 8 pairs for A? Thank you!

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

    editorial states 'house', not 'pair' we only need y-diff's max, second-max, x-diff's max, second-max. For y-diff's max, (y_max, y_min) For y-diff's second-max, (y_max, y_{second-min}), (y_min, y_{second-max}) as same for x-diff at most 8 houses can appear in 4 candidate pairs. and, we can calculate min, second-min, max, second-min in O(N)

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

Congratz!! Jiangly by winning 1925$ in the contest. jiangly orz

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

Code

What am I missing here? Please help.

Upd — Problem solved . I used 1e9 as INF :(

»
2 months ago, # |
  Vote: I like it +15 Vote: I do not like it

The official editorial for D is too good!