chokudai's blog

Aising Programming Contest 2022（AtCoder Beginner Contest 255） Announcement
By chokudai, history, 2 years ago, In English

We will hold Aising Programming Contest 2022（AtCoder Beginner Contest 255）.

The point values will be 100-200-300-400-500-500-600-600. We are looking forward to your participation!

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

Comments Comments (54)
| Write comment?
»
2 years ago, # |
  Vote: I like it +6 Vote: I do not like it

Wow, this ABC feels so different(looking at B and C's unusual difficulty). Took 20 min for C, but 5 min for D...

E is really nice. How to solve E better than $$$O(N.M^2)$$$? My solution surprisingly TLEs on 12 cases with that complexity

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

    Did you try treemap? $$$O(NM^2logN)$$$ is enough for E. My submission

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

      Maybe its unordered map constant factor

      → Reply
      • »
        »
        »
        »
        2 years ago, # ^ |
          Vote: I like it +10 Vote: I do not like it

        Actually no. It's probably because [] operator inserts the element into the map if it's not already present, with default value 0. So you should first check the element's presence and then only access it using [].

        → Reply
        • »
          »
          »
          »
          »
          2 years ago, # ^ |
          ← Rev. 3   Vote: I like it 0 Vote: I do not like it

          Thanks, it removes the TLE. Lesson learnt. Solution

          Edit: This is me from 13 months into the future. It's better to use M.find(x)!=M.end() instead of M.count(x) as the latter is actually O(number of elements in map)

          → Reply
  • »
    »
    2 years ago, # ^ |
      Vote: I like it +25 Vote: I do not like it

    There are two main observations:

    • If we fix the value of any element of $$$A$$$, then the value of all other elements can be determined easily.

    • Let us say we fixed the value of index $$$A_0$$$ = $$$0$$$, then if we increase $$$A_0$$$ by $$$1$$$, then all $$$j$$$ such that $$$j mod 2$$$ = $$$0$$$, value of $$$A_j$$$ will increase by $$$1$$$ and for other elements their value will decrease by $$$1$$$.

    Now since we've already fixed the value of $$$A_0$$$, we can easily find the value of other elements of $$$A$$$. Now, to maximize the answer we will find the value by which $$$A_0$$$ should be increased (or decreased) such that $$$A_i$$$ becomes equal to $$$X_j$$$. After finding this for every possible $$$i,j$$$, we will just increase(or decrease) $$$A_0$$$ by the most frequent value and calculate our final answer.

    Submission

    → Reply
    • »
      »
      »
      2 years ago, # ^ |
        Vote: I like it +6 Vote: I do not like it

      Personal lesson from this contest: Read statements carefully. At first I tried to solve Problem E assuming $$$A_{i+1} = A_i + S_i$$$. When I was done, the sample didn't match and I realized my error. $$$head \rightarrow desk$$$

      Went on to solve F instead, to forget my wrong assumptions.

      Turned back to E, realized how to solve it when reading it correctly, but then the contest was over. Upsolved 10 minutes after the contest: Submission — It's basically the same idea as your's. I'm not entirely sure why your's takes only 668ms compared to 861ms from my cleaned-up version

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

    As a 900-rated on AtCoder, I took 20 min for B, 40 min for C and 10 min for D. I think something must be wrong:(

    → Reply
»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Hey, guys! Could any of you help me and find a mistake in my code? 67 AC and 1 WA for problem C :)

Submission: https://atcoder.jp/contests/abc255/submissions/32404305

Thanks in advance!

→ Reply
  • »
    »
    2 years ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    \sout{Your mn can be greater than mx.}

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

      How come? They can be at most equal.

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

        oh, sorry. You are right. But you only check negative operation for remainder. Didn't check for the positive operation.

        → Reply
        • »
          »
          »
          »
          »
          2 years ago, # ^ |
          ← Rev. 2   Vote: I like it 0 Vote: I do not like it

          long long num works for a positive operation if I have got you right.

          i.e. x-a = 7 and d = 3: the answer in the else statement will be min(1, 2).

          → Reply
  • »
    »
    2 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it 
    -2 10 -5 5

    Your answer gives -7. Correct answer is 2.

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

      It gives 2 in my compiler however..

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

      Do you have atcoder / CF setting (or whatever it is called) in your workspace? Probably my compiler skips this error, but I am not sure.

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

        I ran your code on Leetcode Playground. Please give it a try there to see if you also see -7.

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

          Even there it gives 2 :)

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

            You have multiple submissions. The last submission or the link provided gives -7. When I clicked on another submission of yours and I can see the result is 2.

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

              Oh, for some reason it linked different one, sorry.

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

    Just use d = abs(d) before calculating "num" and you'll be fine

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

    I am not quite sure but maybe your 27/28 lines may lead to wrong answers if d<0.

    → Reply
»
2 years ago, # |
  Vote: I like it +3 Vote: I do not like it

B irritating statement, and C much more difficult than expected.

My E runs in O(N*M*log(N*M)) submission

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

    Why do you use strange define cini?

    That's 6 characters, but cin>> is 5.

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

      cini also includes the variable definition, so its one whole statement less.

      → Reply
  • »
    »
    2 years ago, # ^ |
      Vote: I like it +6 Vote: I do not like it

    Can you please explain your solution in detail. It looks so clean!!!

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

      It looks clean because of using cini, thanks ;)

      Well, it is more or less same as explained above. The sequence A[] is determined by a[0]. If we increase/decrease a[0], all other elements change accordingly.

      Since there are only max M=10 good numbers, we can check foreach A[i] the max 10 values for A[0], so that A[i] becomes a good number, and collect the frequency of these values.

      Then we choose that value for a[0] that has the max frequency.

      → Reply
»
2 years ago, # |
  Vote: I like it +9 Vote: I do not like it

F is a common interview problem https://leetcode.com/problems/construct-binary-tree-from-preorder-and-inorder-traversal/

→ Reply
»
2 years ago, # |
  Vote: I like it +3 Vote: I do not like it

B, C, and D are binary search. Nice!

→ Reply
»
2 years ago, # |
  Vote: I like it +88 Vote: I do not like it

The condition in F about the fact that the root of the tree must be node 1 does not make any sense. The check is trivial and does not affect the solution in any way, but you can accidentally skip it and get WA

Why add weird checks to the task?

→ Reply
  • »
    »
    2 years ago, # ^ |
      Vote: I like it +11 Vote: I do not like it

    I agree with you. But why do you get wa if this case is present in 2nd sample?

    → Reply
    • »
      »
      »
      2 years ago, # ^ |
        Vote: I like it +6 Vote: I do not like it

      Sent in the last minutes and did not have time to check the samples)) It's my fault, I agree

      → Reply
»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

How to solve problem D? I have no idea.

→ Reply
»
2 years ago, # |
  Vote: I like it -13 Vote: I do not like it

Do atcoder count rank of unrated people too? like my rank was 2120 during the contest and after the system testing it still same

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

    Atcoder don't have the system testing. And unrated people does count. If yuo want to remove them, select Standings — Standings — Customize — Show Rated Only.

    → Reply
»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

I kept getting WA for problem F during the contest, and finally find the mistake after contest ends. I should always use array-P to construct both left and right child nodes. But unfortunately, I used array-I to build at least one of left/right child nodes in my every submission.

Anyway, the problems are quite great and really appreciate the work from atcoder team.

→ Reply
»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

I have different solution for problem F and i think it's worth mentioning .

For each $$$P_i$$$ let's find it's parent node and it belongs to the left/right of parent node . Let $$$pos[P_i]$$$ denote position of $$$P_i$$$ node in array $$$I$$$ , then i'll do following :

  • If there exists $$$j<i$$$ such that $$$pos[P_j]>pos[P_i]$$$ and has left child untaken , pick such $$$P_j$$$ with smallest $$$pos[P_j]$$$ and assign $$$P_j's$$$ left child to $$$P_i$$$

  • Else if there exists $$$j<i$$$ such that $$$pos[P_j]<pos[P_i]$$$ and has right child untaken , pick such $$$P_j$$$ with biggest $$$pos[P_j]$$$ and $$$P_j's$$$ right child to $$$P_i$$$

Those operations can be done in $$$log(N)$$$ with set , so final complexity will be $$$O(Nlog(N))$$$ . During contest i didn't waste time on proving this , but now i think it's provable .

link to submission

→ Reply
»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Link Getting wrong answer HELP me to debug for problem C


my approach :
if x is good number ans is 0
binary search on good number
left < x
right > x
ans = min(x-left,right-x)
→ Reply
  • »
    »
    2 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    D, the difference, may be negative. For this test case:

    -2 10 -5 5

    your solution gives 8. Since the good numbers are 10, 5, 0, -5, -10, the closest number to -2 is 0. The answer should be 2 instead of 8.

    → Reply
»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Any idea about how to solve constrained nim ?

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

    You are aware of the editorial?

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

      yes, but i guess this mathematics is beyond my scope. Can you please explain in a bit simpler manner, perhaps without the use of grundy numbers if possible.

      I went through some codes but not able to get what is happening.

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

        Sorry, I have no solution that is less complecated than the editorial.

        → Reply