Блог пользователя chokudai

Автор chokudai, история, 2 года назад, По-английски

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!

  • Проголосовать: нравится
  • +62
  • Проголосовать: не нравится

»
2 года назад, # |
  Проголосовать: нравится +6 Проголосовать: не нравится

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

  • »
    »
    2 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

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

    • »
      »
      »
      2 года назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      Maybe its unordered map constant factor

      • »
        »
        »
        »
        2 года назад, # ^ |
          Проголосовать: нравится +10 Проголосовать: не нравится

        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 [].

        • »
          »
          »
          »
          »
          2 года назад, # ^ |
          Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится

          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)

  • »
    »
    2 года назад, # ^ |
      Проголосовать: нравится +25 Проголосовать: не нравится

    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

    • »
      »
      »
      2 года назад, # ^ |
        Проголосовать: нравится +6 Проголосовать: не нравится

      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

  • »
    »
    2 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

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

»
2 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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!

  • »
    »
    2 года назад, # ^ |
    Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

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

    • »
      »
      »
      2 года назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      How come? They can be at most equal.

      • »
        »
        »
        »
        2 года назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

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

        • »
          »
          »
          »
          »
          2 года назад, # ^ |
          Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

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

  • »
    »
    2 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    -2 10 -5 5
    

    Your answer gives -7. Correct answer is 2.

    • »
      »
      »
      2 года назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      It gives 2 in my compiler however..

    • »
      »
      »
      2 года назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      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.

      • »
        »
        »
        »
        2 года назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

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

        • »
          »
          »
          »
          »
          2 года назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится

          Even there it gives 2 :)

          • »
            »
            »
            »
            »
            »
            2 года назад, # ^ |
              Проголосовать: нравится 0 Проголосовать: не нравится

            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.

  • »
    »
    2 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

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

  • »
    »
    2 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

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

»
2 года назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

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

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

  • »
    »
    2 года назад, # ^ |
      Проголосовать: нравится +5 Проголосовать: не нравится

    Why do you use strange define cini?

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

  • »
    »
    2 года назад, # ^ |
      Проголосовать: нравится +6 Проголосовать: не нравится

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

    • »
      »
      »
      2 года назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      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.

»
2 года назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

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

»
2 года назад, # |
  Проголосовать: нравится +88 Проголосовать: не нравится

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?

  • »
    »
    2 года назад, # ^ |
      Проголосовать: нравится +11 Проголосовать: не нравится

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

    • »
      »
      »
      2 года назад, # ^ |
        Проголосовать: нравится +6 Проголосовать: не нравится

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

»
2 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

How to solve problem D? I have no idea.

»
2 года назад, # |
  Проголосовать: нравится -13 Проголосовать: не нравится

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

  • »
    »
    2 года назад, # ^ |
      Проголосовать: нравится +3 Проголосовать: не нравится

    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.

»
2 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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.

»
2 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
2 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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)
  • »
    »
    2 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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.

»
2 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Any idea about how to solve constrained nim ?