chokudai's blog

UNIQUE VISION Programming Contest 2022 Summer (AtCoder Beginner Contest 268) Announcement
By chokudai, history, 2 years ago, In English

We will hold UNIQUE VISION Programming Contest 2022 Summer (AtCoder Beginner Contest 268).

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

We are looking forward to your participation!

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

Comments Comments (24)
| Write comment?
»
2 years ago, # |
  Vote: I like it +34 Vote: I do not like it
Problem D >_<
→ Reply
  • »
    »
    2 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    $$$>3$$$ literally took my $$$5-6$$$ submissions :(

    Ended up with some cringe implementation :(

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

I didn't understand the meaning of problem E all the time ！

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

Problem E can be solved with heuristics.

Let f(x) be the sum of frustrations after x rotations, we can notice that f(x) is non-increasing till some point, and non-decreasing after that point.

I did ternary search which passed all except 2 tests, and added some randomization, which got AC.

Here is my ugly code: https://atcoder.jp/contests/abc268/submissions/34747256

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

    I think F was easier than E.

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

      Exactly True.I can solve the F after getting a glance,however,I can not think of an excellent solution to E at all!!!

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

That problems where basically all like "avoid off-by-one-errors, then you'll be fine", which felt even for abc a little one dimensional.

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

There I go...

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

how to solve c?

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

    Count the no of happy persons if we rotate the array by $$$k$$$. Take the maximum over all values of $$$k$$$.

    for dish $$$i$$$:

    • $$$k$$$ would be $$${(n + i - 1 - id[i])}$$$ % $$$n$$$ for person $$$(i - 1)$$$.
    • $$$k$$$ would be $$${(n + i - id[i])}$$$ % $$$n$$$ for person $$$i$$$.
    • $$$k$$$ would be $$${(n + i + 1 - id[i])}$$$ % $$$n$$$ for person $$$(i + 1)$$$.

    $$$id[i]$$$ denotes the index of dish $$$i$$$ in the array.

    AC Code

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

      how you came up with this great intuition?

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

        Firstly, I tried fixing a dish (say $$$i$$$) for a particular person so that person $$$i$$$ became happy! thereafter I got the logic to count the no of happy persons who become happy if I rotate the array by $$$k$$$.

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

Can someone tell me what is wrong in my submission for D?

Looks, like my code is not finding solution in some cases, but not sure how it is possible as I am doing all perms + all combination of dashes after it.

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

    Shouldn't the "under" string start being empty? it seems to me you're only considering two underscores and more...

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

How to solve F?

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

    Let $$$x$$$ be the number of 'X' characters in a string and $$$d$$$ be the sum of the digit characters in a string. Then sort in order of decreasing $$$x / d$$$ and compute the answer.

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

      Interesting. Thank you! How do we prove such a claim?

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

        I saw it by considering when it’s advantageous to swap adjacent elements and arrived at the above comparator. I recommend this resource for practicing exchange argument style problems: https://codeforces.me/blog/entry/63533

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

        I proved this with exchange arguments.

        Consider two strings that are adjacent in s, let them be $$$s_1$$$ and $$$s_2$$$.

        Let the number of X in $$$s_1$$$ be $$$d_1$$$, sum of digits in $$$s_1$$$ be $$$x_1$$$. Let the number of X in $$$s_2$$$ be $$$d_2$$$, sum of digits in $$$s_2$$$ be $$$x_2$$$.

        The change in the score when you swap $$$s_1$$$ and $$$s_2$$$ in s will be $$$d_2 x_1 - d_1 x_2$$$.

        If this change is positive, we swap $$$s_1$$$ and $$$s_2$$$.

        So sort in order of decreasing $$$x/d$$$.

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

        Let there be two strings with index $$$i,j$$$.So lets say placing $$$i$$$ before $$$j$$$ gives us a better answer than placing $$$j$$$ before $$$i$$$ so it means that $$$xi{*}dj$$$ $$$>=$$$ $$$xj{*}di$$$ $$$=>$$$ $$$xi{/}di$$$ $$$>=$$$ $$$xj{/}dj$$$ as $$$x$$$ and $$$d$$$ are non-negative. Therefore placing $$$i$$$ before $$$j$$$ gives a better answer iff $$$xi{/}di$$$ $$$>=$$$ $$$xj{/}dj$$$. We can extend this idea and just sort the strings in order of decreasing $$$x/d$$$ and compute the answer.

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

Can someone tell me what is wrong with my submission for D?

submission link

→ Reply