chokudai's blog

By chokudai, history, 19 months 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

| Write comment?
»
19 months ago, # |
  Vote: I like it +34 Vote: I do not like it
Problem D >_<
  • »
    »
    19 months 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 :(

»
19 months ago, # |
  Vote: I like it +16 Vote: I do not like it

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

»
19 months 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

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

    I think F was easier than E.

    • »
      »
      »
      19 months 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!!!

»
19 months 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.

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

There I go...

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

how to solve c?

  • »
    »
    19 months 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

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

      how you came up with this great intuition?

      • »
        »
        »
        »
        19 months 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$$$.

»
19 months 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.

  • »
    »
    19 months 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...

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

How to solve F?

  • »
    »
    19 months 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.

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

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

      • »
        »
        »
        »
        19 months 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.com/blog/entry/63533

      • »
        »
        »
        »
        19 months 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$$$.

      • »
        »
        »
        »
        19 months 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.

»
19 months 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