chokudai's blog

Aising Programming Contest 2022（AtCoder Beginner Contest 255） Announcement
By chokudai, history, 22 months 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?
»
22 months 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
  • »
    »
    22 months 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
    • »
      »
      »
      22 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Maybe its unordered map constant factor

      → Reply
      • »
        »
        »
        »
        22 months 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
        • »
          »
          »
          »
          »
          22 months 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
  • »
    »
    22 months 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
    • »
      »
      »
      22 months 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
  • »
    »
    22 months 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
»
22 months 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
  • »
    »
    22 months ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

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

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

      How come? They can be at most equal.

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

      It gives 2 in my compiler however..

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

          Even there it gives 2 :)

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

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

              → Reply
  • »
    »
    22 months 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
  • »
    »
    22 months 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
»
22 months 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
  • »
    »
    22 months 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
    • »
      »
      »
      22 months 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
  • »
    »
    22 months 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
    • »
      »
      »
      22 months 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
»
22 months 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
»
22 months ago, # |
  Vote: I like it +3 Vote: I do not like it

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

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

How to solve problem D? I have no idea.

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

    Binary search + prefix sum

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

      thanks, bro. But I still don't understant :) wating for the editorial...

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

      oh! I undertand now! How stupid I am !

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

Any idea about how to solve constrained nim ?

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

    You are aware of the editorial?

    → Reply
    • »
      »
      »
      22 months 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
      • »
        »
        »
        »
        22 months 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