chokudai's blog

By chokudai, history, 12 months ago, In English

We will hold AtCoder Beginner Contest 178.

The point values will be 100-200-300-400-500-600.

We are looking forward to your participation!

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

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

Love atcoder beginner contest

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

Reminder: Contest starts in 10 mins!

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

Are there any other contest on atcoder for beginner? ABC are very good but aren't that frequeant and i tried AGC and i shouldn't have... so any other recommendation

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

    The ARC's should be doable, they're gonna be frequent again soon.

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

deleted

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

    Inclusion Exclusion. Number of ways that we can pick any value from 0 to 9 = 10^N . Number of ways that 0 doesnt occur = number of ways to pick any value from 1 to 9 = 9^N. By same logic, number of ways that 9 doesn't occur anywhere = 9^N Number of ways that both 0 or 9 don't occur = 8^N Hence answer is 10^N — 9^N — 9^N + 8^N . Use mods wherever required

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

      mnist why u added 8^N instead of subtracting it from 10^N

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

        its because in both the the 0 and 9 case, the case of both 0 and 9 is considered and thus has been subtracted twice instead of just once.

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

        when you take [0,8] by missing 9 and [1,9] by missing 0 — you double counted and get minused the value [1,8] twice that's why add back 8^N

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

      I tried (nC2)*2*10^(n-2). nC2 to choose any two places for 0 and 9. 2 because {0,9} has two permutations. 10^(n-2) to fill remaining places with 0-9. I am still not sure why this approach is wrong. Could someone point out?

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

        You are counting duplicates

        for example,

        when 0,9 is fixed like this 0_9 and like this 09_ in both cases you are counting 099

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

        I also tried this same approach. Don't know what went missing :')

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

      I am not understanding the line "Number of ways that both 0 or 9 don't occur = 8^N.".Here we are finding the number of wayes without 0 and 9 so i think there may be 0 and 9. Can you help me to find out my error?

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

        Yes it's and, anyways understable from the calculation.

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

      I thought that we could first choose one 0 in the sequence so Nc1 ways to do that and then choose one position for 9 in N-1c1 ways and then for remaining N-2 positions each has ten options so 10^(n-2) ways so my final answer was n*(n-1)*10^(n-2) ..My answer got WA.Can anyone please point out what is wrong in my reasoning.Any help or feedback is appreciated

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

    Why so many downvotes he is just asking the approach didn't say anything wrong or asked anything wrong U can just use Inclusion exclusion

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

      He asked during contest which is not allowed

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

        I was just try to be first so i can get reply so i can get reply quickly without having intention to get solve yes i can give these immediate after contest but i have a online class during the contest for that i gave that during the contest to be honest i have no intention to get a solve from here during contest

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

          The issue is that even if you weren't going to cheat yourself, if someone answered you during contest, anyone else could have seen the answer too, which wouldn't have been fair.

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

    In this question you need to find all sequences so:

    1. There is some i such that Ai = 0 (count of such i may be > 1)
    2. There is some i such that Ai = 9 (count of such i may be > 1)

    (both conditions must be met)

    Let's iterate k — number of positions i such that Ai = 0/9

    Number of ways to create "good sequences" with 0/9 is 2^k — 2 (on every position you have 2 ways to put 0/9) (-2 because you don't need to create sequences 00..000 and 99..999)

    Let's count C(n, k) — the number of ways to select a set of i positions from n positions, where we want to put 0/9

    Finally we want to fill the remaining positions with number 1..8. It is equal to 8^(n — i)

    And final number of ways for some k equal to C(n, k) * (2^k — 2) * (8^(n — i))

    P.S. more details about Binomial Coefficients you can read here Binomial Coefficients

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

Any ideas on how to do F? If the frequency of any number in first array is greater than n — (frequency of that element in the second array) than answer is "No" else answer exists.

I made a logic that the maximum frequent number in the first array will get the least frequent number from the second array. If there are multiple numbers with the same frequency then the smallest number with the smallest frequency goes to the largest number with the largest frequency. I was not quite able to implement it.

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

    Contest has not finished yet

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

    I understand, I thought there's just 1 minute left which won't really make any difference. One cannot implement it that quick. Sorry though I should have been a bit more patient

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

Solved E but coudnt solve C and D :(.

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

    approach for e

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

      There are only two cases to consider, if we only consider results such that Xi <= Xj.

      1. If Yi <= Yj, then the distance is (Xj + Yj) — (Xi + Yi)
      2. Otherwise, the distance is (Xj — Yj) — (Xi — Yi)

      By breaking it down into these cases, I have gotten rid of the absolute value function making it much easier to reason about the distances.

      So, we simply pick points with minimum and maximum x+y, and compute the distance.
      Then pick points with minimum and maximum x-y, and compute the distance.
      One of those two distances is your maximum.

      This can be done in O(n).

      My submission

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

        Copy-pasted from: stackoverflow Why can't you provide the link directly instead of copy pasting the text XD

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

          So people dont have to visit stackoverflow and look for answer.

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

          its simple as you prob. dont want to jump from one site to another for a simple reason ,so posting a simple basic explanantion is not that big of issue

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

      The manhattan distance of two points is the distance of the parallel diagonals of these points.

      The points at a distance x from a given point p form a diamond.

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

How to do D?

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

    Simple DP. very similar to this

    Just coins here are {3, 4, 5 .. N}

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

      But using coin change dp method does not give us the different permutations right? Like for sum = 7. the answer = 3 ( {3,4} , {4,3} , {7} ). But dp gives us only answer = 2 ( {3,4} , {7} ). Please correct me if I'm wrong

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

        Imagine filling DP array for n = 7 by this code:

        Spoiler

        Hope you understood

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

          Awesome! I understood now...thanks for the efforts :)

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

          wow !! nice idea..

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

          can you please describe how can we implement it by top-down dp approach?

          I have implemented this but it isn't correct.

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

    As we cant take 1's and 2's, our number of ways to form i is : dp[i] = dp[i-3] + dp[i-4] + ....

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

    I did it using Combinatorics, Stars and bars. Divide the number into x sums, (1 to s/3) and for each, find all possible combinations, by keeping each of it exactly 3 initially.

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

      I also did the same,this approach is bit intuitive as this revises the P&C concepts :)

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

      Could you elaborate more on this approach?

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

        Sure.
        Firstly let's notice that we can only have sequences of size from 1 to s/3. (because each one should be at least 3)

        Then, let's call these "number of groups" as x,

        example: For s=9, we have,
        x=1, {3} ; (with 6 still remaining)
        x=2, {3,3} (with 3 still remaining)
        x=3, {3,3,3} (with 0 remaining)

        Now, we can distribute the remaining sum, for each x, among the x groups, in (n+r-1)C(r-1) ways,
        This is, distributing n identical objects among r people (stars and bars).
        So iterating over each x from 1 to s/3 by calculating the combination for each iteration, it's easy to find the answer.

        Submission

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

          thank u a lot

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

    It’s just a simple coin change dp problem.

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

How to solve E? I tried to find smallest and largest points on x and y axis(total 8 points) and found maximum among them.

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

      Thanks! Completely forgot to break mod, went in the wrong direction. :(

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

    I removed the mod (absolute value) by considering 4 cases.

    case 1 : xi > xj and yi > yj

    we need to find now max(xi-xj + yi-yj) = max((xi+yi)-(xj+yj)) = max(xi+yi)-min(xj+yj)

    for other cases I multiplied coords by -1 and solved by case 1 again

    case 2 : multiply all x by -1

    case 3 : multiply all y by -1

    case 4 : multiply all x and y by -1

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

    Manhattan distance between two points is: |$$$x$$$a — $$$x$$$b| + |$$$y$$$a — $$$y$$$b|.

    Now if can be evaluated in 4 ways:
    $$$dist$$$ = ($$$x$$$a — $$$x$$$b) + ($$$y$$$a — $$$y$$$b)
    $$$dist$$$ = ($$$x$$$a — $$$x$$$b) — ($$$y$$$a — $$$y$$$b).
    $$$dist$$$ = -($$$x$$$a — $$$x$$$b) + ($$$y$$$a — $$$y$$$b).
    $$$dist$$$ = -($$$x$$$a — $$$x$$$b) — ($$$y$$$a — $$$y$$$b).

    Now if you simplify them a little then the distance can be one of the two below:
    1) $$$dist$$$ = ($$$x$$$a + $$$y$$$a) — ($$$x$$$b + $$$y$$$b)
    2) $$$dist$$$ = (-$$$x$$$a + $$$y$$$a) + ($$$x$$$b — $$$y$$$b)

    Now the distance will be maximum from above expressions.
    submission link

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

    the approach to solve was same as this question.

    you were just given distance function instead of f(i, j)

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

    Alternatively, you can calculate the convex hull of the given points and brute force the vertices of the polygon.

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

      This will TLE if to much points are on the convex hull, it could be all.

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

        Yes, you're right. However, I got an Accepted verdict. I guess the test cases are not strong enough.

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

Pure Mathematics Contest!!

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

Maybe E is just a too well known problem, but F solution was more obvious to me than E solution.

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

    how to solve F ? It seems easy at first.

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

    how to solve F ? Think about 70 mins and more but still fail to figure

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

    What was the approach for F?

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

    Can you please explain your solution to E, I don't know which one test case was failing, I got 17 AC and 1 WA

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

      This might help https://atcoder.jp/contests/abc178/submissions/16705345 I sorted the points considering points to be equal if they lie in the same circle centered at the origin

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

      Put three comparators. one comapring x1-y1 other with x1+y1 one with y1-x1 Take the max of difference of the end terms and max of three would be the answer.

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

      Here is my take on E,

      ans=(x2-x1)+abs(y2-y1) ,x2>x1

      Now we have two options for answer

      ans1=(x2+y2)-(x1+y1) ==== max(x+y) -min(x+y) for optimal answer

      ans2=(x2-y2)-(x1-y1) ==== max(x-y) -min(x-y) for optimal answer.

      Final answer would be the max of two.

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

        Hey can you please suggest which one test case is failing for this solution

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

          Try this

          2

          392850397 652442710

          430284160 923935256

          Correct answer:308926309

          Your answer:493651095

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

          Sorry for prvious wrong case.I updated it. Please check it,

          Sorry for my bad English.

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

        I have a doubt. The two cases are coming from assumptions, like case 1 comes from y2 >= y1. So how is it that when we calcuate the answer, we don't check for these restrictions and still get the correct answer. Can't it be that for i and j which gives max(xi + yi) — min(xj + yj), yi is actually less than yj which makes that pair invalid?

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

          Actually I have this same doubt and I have used the same assumptions that invalid pairs wont affect the best answer for the problem and got a AC, I was really trying to find a intuitive or mathematical proof for the same but havent got one, I would really appreciate if someone comes up with a proof for the same.

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

          Here we are only concerned about the largest value

          Lets get our definitions clear first

          option1 = (xj-xi) + (yj-yi) for yj>=yi

          option2 = (xj-xi) + (yi-yj) for yi>=yj

          Now for yj>=yi we can never have option2>option1 and vice versa.

          So though we are considering some invalid pairs our answer is never going to be affected

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

    Can you check why I am getting WA on F. here is submission

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

    More than being well known, E is pretty easily searchable I think.

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

MathCoder literally :V

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

What are the solutions for problems E and F?

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

    e is well-known, u can google it

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

      I googled couldn't find the same problem, can you please provide a link where solution of this problem is explained. like gfg or something?

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

Hi, this is my code for F problem

I am failing in 3 test cases and I couldn't figure out those TCs,

you can find my code in this link please help me

https://ideone.com/7PaZ9k

My submission link https://atcoder.jp/contests/abc178/submissions/16710181

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

    can I get any test case for which my code is failing?

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

      there is dropbox link to all atcoder test cases in one of the rng_58's blog

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

Can someone share his approach for solving F?

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

F solution: Reverse array B, then A will be in ascending order and B will be in descending order. If we now look at positions where A[i] == B[i], they will form a segment [l, r], and will all have equal element A[i] == B[i] == C. Then you just need to swap all positions i from this segment with such positions j that A[j] != C and B[j] != C. And if there are not enough such positions j then I think it's not hard to prove that reordering is not possible at all.

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

    I think reordering is not possible only in the case where lets say x occurs m times in A and k times in B and both k>=(n+1)/2 and m>=(n+1)/2. By pigeonhole principle!

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

      No consider A = [1 1 1 1 2] B = [1 1 2 3 4], maybe we can say that frequency of some element must obey $$$f_A + f_B <= n$$$ ...

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

        Ya I missed it thanks , Amazing F!

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

        How to prove that answer is always Yes when every f_A + f_B <= n

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

          That is shown from answer of madn. When A is ascending and B is descending, and lets say $$$f_A + f_B = N$$$ for boundary condition, maximum intersection is possible if both A and B have near equal frequencies, intersection will be of length $$$\lfloor N/2 \rfloor$$$. So we have adequate numbers ($$$\lceil N/2\rceil$$$) to put in this positions of overlap, so answer is always possible

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

            oh,actually its very obvious...what am i thinking...Thanks!

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

    This is the best solution I have ever read!!

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

      Yeah I find it very simple and easy to see correctness. In my contest I was just wondering why they gave A, B in sorted order, maybe it was hint toward this solution

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

      Yes, key insight is that only a[i] = b[i] = c will be the only value, and form an interval

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

        Can you prove it ?

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

          if there are two different value that a[i] = b[i], let a[i] = b[i] = c, a[i+1] = b[i+1] = d, and c != d

          a[i] < a[i+1], so d > c

          b[i] > b[i+1], so d < c

          contradiction

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

    I am not claiming following is correct but I also cannot see why it is wrong. It must be wrong because it gives runtime error. The process was:

    1. Find net frequency of each element in the two arrays. If it is greater than n, then it is not possible to rearrange.
    2. Otherwise we use a max-heap to store pair of {"frequency in B", "number"}. Now we loop A from 1 to N and simply pop from heap and check it with A[i]. If not equal then we place it in our final array. Otherwise we pop another value and place it in final array. We push back the changed frequency.

    I think it runs into dead end where it no longer finds a suitable pair, but why it happens? Thanks!

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

    i think thats the easiest code to read and understand.

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

    I thought of the exact same idea but it gave WA.
    check this: https://atcoder.jp/contests/abc178/submissions/16969818
    Can you help me to find what is wrong? I think this method isn't right.

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

Man problem C ruined the round for me!:) Can anyone please explain the approach for it?

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

    10^n-2*9^n+8^n Inclusion exclusion

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

      Wow, thanks! Very interesting!

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

      Can you please help me to understand what wrong with this approach.

      Take two numbers and assign 0 and 9 to them , ways=n*(n-1)

      remaining (n-2) numbers can be arranged in 10^(n-2) ways making

      ans=n*(n-1)*10^(n-2)

      Thanks.

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

        The 10 ^(n-2) replicates in many cases when n>=3 see lets say you place 0,9 at 1 2 so possible values are 0 9 1, .....0 9 9

        SImilarly suppose in another permutation you fixed 0 9 at position 1 3 and other 10 values accordingly at remaining position .Observe both the vectors carefully.

        0 1 9........0 9 9.

        You can clearly see 0 9 9 appearing common in both thus WA!

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

        There will be repeation, like in your solution you will count (2 1 9 2) twice.

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

      Intuition behind this:

      There are $$$x$$$ ways of choosing which of $$$x$$$ numbers to place in a spot, each choice is independent of each other, so for $$$n$$$ places there are $$$x^{n}$$$ ways.

      Number of ways of placing numbers in the range $$$[0, 9]$$$ -> $$$10^{n}$$$.

      Number of ways of placing numbers in the range $$$[0, 8]$$$ or $$$[1, 9]$$$, that is the number of ways of generating an array that is guaranteed to be missing either a $$$0$$$ or an $$$8$$$ -> $$$9^{n}$$$ each.

      But note that we have double counted the number of ways to place $$$[1, 8]$$$ (both missing) while removing the bad array count, so add back the number of ways of doing that which is $$$8^{n}$$$.

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

    You can use DP for accounting for double counting

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

      Thanks! I tried to do a dp approach but i didn't manage to solve it during the contest! In my opinion, D was easier than C.

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

        Exactly! I was stumped by C as well. Here's my DP solution to C

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

          Nice solution!

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

          Please, can you explain your solution? I couldn't get it.

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

    Answer = (total sequence with length n and all element <= 9) — (total sequences such that it contains neither 0 nor 9)

    first term above is simply pow(10,n) for the second term I used inclusion exclusion:

    A = Set of sequences that doesn't contain 0

    B = Set of sequences that doesn't contain 9

    n(A union B) = n(A) + n(B) - n(A intersection B)

    n(A) = n(B) = pow(9,n)

    n(A intersection B) = pow(8,n)

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

      Nice explanation, thank you!

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

      I am still confused with duplicates. Can anyone please write all the sequences if n = 3 ? Thanks in advance.

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

        answer for 3 is 54 which is too big to enumerate manually. But if you are asking why pow(10,n-2)*C(n,2) is not right answer, I'll try to show duplicates. Suppose n = 3 and you decide to fix first and third position one of the sequence you get is 009 which is repeated when you fix second and third position, thus counting same sequence twice.

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

      thanks, it helped.

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

      nice explanation!!

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

    deleted

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

what's wrong in my solution of F? getting wrong answers on 6/50 test cases?

https://atcoder.jp/contests/abc178/submissions/16721049

UPD: I did some changes in my above code but still it's giving wrong answer on 3 test-cases :( https://atcoder.jp/contests/abc178/submissions/16724818

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

Anyways to do C or D without DP ?

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

    C is simple inclusion — exclusion. My one line code :

    cout << sub(add(power(10, n), power(8, n)), add(power(9, n), power(9, n)));

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

    10^n-2*9^n+8^n

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

    D could be solve by brute force the number of elements in the sequence and the do a star-and-bar-like counting trick.

  • »
    »
    12 months ago, # ^ |
      Vote: I like it +5 Vote: I do not like it
    My approach of D (Without dp ) :
    First of all fix the length of the sequence .
    Suppose length is 5 ;
    so a1 + a2 + a3 + a4 + a5 = S ; now for all i , a[i]>=3 ;
    using stars and bars technique  ,
    no of solution  of that equation is ncr(s-3*length +length -1 , length-1);here length = 5 ;
    final answer = sum of solutions for each fixed length .
    
    Code
  • »
    »
    12 months ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    I did D using combinatorics. It is the modified version of distributing n balls into r urns such that each urn contains at least 1 ball.

    Solution of standard problem: (n-1)C(r-1).

    Here problem can be reformulated as if you can use any number of urns (because the length of sequence can vary) and each urn should contain at least 3 balls.

    Solution: summation of (n-1-2*i)C(i-1) for all i, where i is the number of urns and n is the sum we want. The term -2*i because we first put 2 balls in every urn so that problem is now transformed into a standard one containing at least 1 balls, for each i.

    https://atcoder.jp/contests/abc178/submissions/16705277

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

For problem C: I'm thinking like this, place 0 and 9 in any two places (nC2) then other n-2 places will have 10 possibilities hence (10^(n-2)). So overall answer is nC2 *(10^(n-2)).

Can anyone say what fact am i assuming wrong/missing. Thanks :)

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

    nC2 * 10^(n-2) will duplicate

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

      can you give correct combination formula for this problem ?

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

        I used dp https://atcoder.jp/contests/abc178/submissions/16709001 Here,

        • dp[n][0][0] means sequence of length n and 0 zeros and 0 nines,

        • dp[n][0][1] means sequence of length n and 0 zeros and atleast 1 nine,

        • dp[n][1][0] means sequence of length n and atleast 1 zero and 0 nines,

        • dp[n][1][1] means sequence of length n and atleast 1 zero and atleast 1 nines

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

      so the 0's and 9's are getting duplicated?

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

        In cases when you put 9, 0 like this: ab90 09cd sequences may coincide, when a = 0, b = 9, c = 9, d = 0: 0990 0990

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

    There are repetitions in your formula. For n = 4 the answer is 974. Check with your submission

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

    I also thought of it at first but if you think about it cleary it will have places with repetitive counting.

    for example, consider n = 5 and you choose places 0 9 8 0 9 will be a valid sequence but it will be counted twice (as nc2 will include 1&2 and 4&5 ).

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

    in this way you will count some sequences more than once
    lets say that n=3

    one of possible way is to put 10 as a first element and 9 as a last element and lest say that the element in middle is 10 so the sequence is 10 10 9

    another possible way is to put 10 as a second element and 9 as a last element and lest say that the first element is 10 so the sequence is 10 10 9 again and we already count it

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

atdynamicprogrammer

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

lose again because of my speed

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

Was trying to do D , using DP but gave TLE... https://atcoder.jp/contests/abc178/submissions/16721075 Can someone pls help what is wrong

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

    Index is not necessary in the state.

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

      Damn I messed up !!!, after removing the index state got AC....Thanx

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

Editorial:

A
B
C
D
E
F

All codes:https://atcoder.jp/contests/abc178/submissions?f.User=Gary

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

    In $$$C$$$ constraints are smaller, so if someone has weak combinatorics(like me) then dp is more intuitive imo. here is my sol using dp:

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

    Hey, in problem D, I think you also need to add 1 to dp[i].

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

Is there a case to be handled for mod of negative numbers in C ?

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

    if a<0 then use mod-abs(a) will work.

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

    Don't forget to add mod when you are subtracting two numbers under mod.

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

      I just have learnt a very valueable lesson.

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

    we can do this : ans = (a-b+MOD)%MOD;

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

      How does it work?Can you please explain or give me any reference?

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

        I'll leave that for you to figure out :)

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

And.. AtCoder becomes MathCoder.

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

c explanation ?

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

    Total Number: 10^n

    Without digit '9': 9^n

    Without digit '0': 9^n

    Without both: 8^n

    Final Result: 10^n — 9^n — 9^n + 8^n

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

    Total numbers you can make using all digits (10^n) — numbers with all digits but 9 (9^n) — all but 0 digits (9^n) + all but 0 and 9 (8^n) (because they were deleted twice);

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

    Total possible sequences = 10^N. Sequences with no 0 = 9^N. Sequences with no 9 = 9^N.

    Subtract sequences with no 0 and sequences with no 9 from total possible combinations. But observe after doing so you will remove sequences with no 0 and no 9 twice. So add sequences with no 0 and no 9

    Sequences with no 0 and no 9 = 8^N.

    Ans = 10^N — 2*9^N + 8^N.

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

Maybe this is an off-topic.

I think Atcoder should show counts of solve for each problem in dashboard/tasklist(like CF). I know it is in the standings page, but viewing standings itself some number of times is well-disgusting.

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

I have tried to solve F using bipartite graph matching but it failed just in test 16 :)))

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

I found my solution for F is realy complex(Though it is right)!!

Can you share your idea for F?

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

    Resulting ordering of B array is some cyclic shift of itself. (If no shifting is possible, no solution).

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

      Thank you for your reply:)

      But can you prove it?And how to achieve it?

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

        I did not scratch a full proof yet.

        For each element in B, we find what shifts are not possible. This can be done using set/segment tree.

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

        my F solution

        Whenever there exists index i where A[i] is equal to B[i], shift array B one time. Loop until there are no such indices in one interation. I use two pointers to maintain the shift

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

          Can you prove it?

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

            Sorry, I didn't prove it during contest. I generate all possible cases for small N and it seemed work.

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

              alvinvaja , I really like the quality of your profile picture. May I know which camera was used?

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

                It wasn't mine. Got it from pinterest

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

            I think mine is similar where I take a number, x, in both a and b and if the start of b's interval of x isn't over the end of a's interval of x, I calculate how many shifts it would take to make b's start over a's end of x's interval (if b's start isn't already over a's end) and take the maximum shift for all numbers that are both in a and b. Maybe there's a counterexample but I couldn't find one.

            After the greatest shift needed is done, for that number x in b that needed the largest shift, all the numbers < x in b should be assigned to a number bigger than it in a and all the numbers >= x in b are shifted up to match numbers bigger than it in a until n, and then they match to lower numbers that are <= x because the shift circles it to the beginning of a. Unless the array is impossible I don't see how any numbers can conflict yet.

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

        I used the same approach, but I also can’t prove it. But I know how to achieve it. Each position of B can be expressed as "not shifting in range [l, r]" which is equivalent to

        ~[x >= l and x <= r] = (~(x >= l) or (x >= r + 1)).

        Now the requirement is just AND product of all boolean clauses which is nothing, but 2-SAT. I thought that they put some problems to practice Atcoder library, turned out that I overcomplicated things up. lol (They didn’t add library yet, so I got compile error.) code

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

    you can see this solution I just tried to solve F using this and got AC. Logic is simple as well as code. Here is my code for this approach

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

Can someone check why I'm getting WA on C . here is my submission

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

    Result of a1 — a2 + b1 may be negative, so just add MOD to it before taking remainder

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

    "ll ans = (a1 — a2 + b1)%M" should be ll ans = (a1 — a2 + b1 + M)%M;

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

    ll ans = (a1 - a2 + b1 + MOD)%M;

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

Just 2 min short to get AC in problem F. Nice F anyway

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

    What was your idea behind F? Was it greedy?

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

      The idea is tough to explain for me. I try. 1.A is in ascending order and B is in ascending order. So, just try to pick up elements like two pointer from start to end. Then, pick the unpicked elements too. Now, check the answer. If its OK then print.
      2. Otherwise, reverse B once again and go like 1. Check the answer. If OK then print it, else there is no answer.

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

A Combinatorics solution for D — Redistribution

Recall that, by the famous Stars and Bars Theorem, the number of non-negative integral solutions of

$$$ x_1 + x_2 + \dots + x_r = n $$$

is

$$$ {n + r - 1} \choose {r - 1} $$$

Let us denote this value as $$$stars(n, r)$$$. Clearly, the value is 0 if $$$n$$$ is negative.

Moreover, if we add a constraint that $$$x_i \geq t$$$, then, we can replace $$$x_i$$$ by $$$y_i$$$, where

$$$ x_i = y_i + t $$$

This transforms the problem to finding the non-negative integral solutions of

$$$ y_1 + y_2 + \dots + y_r = n - r \cdot t $$$

Clearly, the number of valid solutions is $$$stars(n - r \cdot t, \ r)$$$

So, for each $$$r$$$ from 1 to $$$n$$$, we sum up the values of $$$stars(n - 3 \cdot r, \ r)$$$.

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

DP Solution for Problem C — Ubiquity

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

A great contest.

Unfortunately,I nealy AK(AC 5 problems),but I'm in trouble with the sixth problem.

All of them are Math problems(.(xiao xue ao shu in Chinese)

And there's Chinese in English task:配点。

Hope the abc will be better!

:)

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

So I did a randomized solution for F. I try three ways:

  1. Reverse $$$B$$$.

  2. Random shuffle $$$B$$$ for $$$T$$$ times.

  3. Rotate $$$B$$$ randomly for $$$T$$$ times.

$$$T = 20$$$ is sufficient to get AC, and it runs in 61 ms. Of course, I have no proof (well not even an intuition) for this. :D

So, I'll be glad if someone can hack this solution or give some proof/intuition for it.

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

    Assume odd n, and n/2 '1' in a[], and n-n/2 '1' in b. Then we need to rotate exactly n/2 positions.

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

      Reversing B works in this case.

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

        Ok, let the sympobls be '2', not '1'. And a '1' in first position of both arrays. Then the reverse of b[] does not work, but still we need to rotate exactly n/2 positions.

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

          Yeah it prints No for this case.

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

give us editorial please..

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

How to prove that on F, if a solution exists, one of the cyclic shifts of b is also a solution?

I wrote my solution based on it and it passed.

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

My Unofficial tutorial (A-F) for this contest.

And the Chinese version.

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

Just a thought: How to solve F if the elements are unsorted in both the arrays?

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

    You can look at my solution, which does not depend on whether the arrays are sorted or not.

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

    You can always sort them and use your solution for the sorted input...

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

Can somebody please help me find the only test case that is failing for my solution of problem E?

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

    Changing the initial value of your variable ans1 to LLONG_MIN should solve your problem, because it's not necessary that x+y or x-y is always greater than -1.

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

What's wrong with my solution of D?

I used dp, $$$dp_{ij}$$$ means the sequence‘s length is $$$i$$$ and its sum is $$$j$$$.

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

    The elements of the sequence can be arbitrary positive integers rather than digits.

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

      Yes, I get it! Thank you so much!

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

    Can be simplified using a 1D dp array. Starting from i=4, dp[i]=dp[i-1]+dp[i-3] and then take the mod.

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

Why do you have the problem whose solution is available in CPH? The most popular book on CP, talking about problem E.

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

For atcoder editorial I search always on codeforces.lol.. xD..

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

Sry for a newbie question, how to we see the test cases at atcoder???

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

How to solve E??

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

Can someone Tell me the approach for E ?

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

Can someone plz tell me why my code for task C is failing for 5 test cases?

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define mod 1000000007

ll help(ll a,ll b){
    if(b==0)return 1;
    if(b==1)return a;
    ll ans = 1;
    if(b&1){
        ans = help(a,b-1)*a;
    }
    else {
        ans  = help(a,b/2);
        ans = ans * ans;
    }
    return ans%mod;
}

int main(){
    ll n;
    cin>>n;
    ll x = help(10,n);
    ll y = help(9,n);
    ll z = help(8,n);
    ll res = x-2*y+z;      // error in this line
    cout<<res;
    return 0;    
}

UPD : Error found The error is, it should be replaced with ll res = (x- 2*y + z + 2*mod ) % mod;

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

    I guess you forgot to take mod from the res at the end

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

      I have changed it after you said, but still those same 5 test cases are failing. I'll update the latest code in my comment. Can you plz look into it again. Thanks!

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

        Since it is c++, mod can also give negative result, you need to handle this

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

I got wrong answer in problem E my approach is : my approach is getting the distance between each point and point(0,0) then sort these distances ascending and the answer will be the distance between the point which has the longest distance and the point which has the smallest distance. May anyone tells me why this approach fails.

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

    Consider (1,1),(100,1),(1,2).Here (1,1) is at min from (0,0) and (100,1) is at max from (0,0) so,according to you, answer should be |(100-1)|+|(1-1)|=99 but the point (100,1) and (1,2) gives |(100-1)|+|(1-2)|=100. There are lots of such points.

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

F can be solved by maintaining an invariant as follows:

Hint1
Hint2
Hint3

Thanks to Yousef_Salama for showing me this idea, you can check his submission.

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

I have written unofficial English editorial, you can find it at: editorial

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

For F, I am reversing B and then checking if B[i]=A[i]. If so at index=p, I am reversing the array from B[0] to B[p] and from B[p+1] to B[n-1]. This works as for the reversed B, all numbers left of B[p] will be >= B[p] and to right of B[p] will be <= B[p]. Whereas in A, all numbers left of A[p] will be <= A[p] and to right of A[p] will be >= A[p]. Theoretically it should work but I am getting wrong answer in 3 of the 60 test cases and I cant figure out why. Can anyone point out the fault in my algo? Submission: https://atcoder.jp/contests/abc178/submissions/16733148

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

Problem F is EXACTLY the same with Perm Matrix (just with smaller constraints).

I've seen this problem,so I got an unexpected high rank.

My atcoder account: sjcsjcsjc

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

    It's nothing new at atcoder, many time I got the exact questions which I had previously solved or seen somewhere. Problem E was also copied in the same contest.

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

      Problem E is just a standard problem of changing Manhattan distance to Chebyshev distance.

      Problems using this technique are everywhere.

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

How can I solve D using top-down?

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

Hi can someone please tell why my submission for problem C is working in atcoder c++ compiler but not in my local compiler.

I have tried recursive dp solution for this problem and it is working well . But in some large input example for n = 869121 it gives segmentation fault in local compiler as well as in online cpp compiler but works well upon submitting can some please tell why this happening ? Can this be due to memory limit or recursion depth ? please help

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

Can someone point out the error in this solution of F? Basically to print array B after validation, I reverse it (that is, descending order) then there will be an interval where there might be some common elements. I m swapping those with elements on either side since on left, elements will be greater and on right will be smaller. There is just one test case which is giving WA here which I cannot crack.