20240501

1966A - Card Exchange

My mistake

As far as I remember, my approach was a greedy one like

# THIS APPROACH DOES NOT WORK

from collections import defaultdict

for _ in range(int(input())):

    # process input
    n, k = map(int, input().split())
    cards = list(map(int, input().split()))
    counter = defaultdict(int)

    # create a map (card number, count)
    for card in cards:
        counter[card] += 1
    cards_with_counts = [[k, v] for k, v in counter.items()]

    # for each card, reduce the number and put the remaining to the next card
    for i in range(len(cards_with_counts)):
        if i < len(cards_with_counts) - 1:
            if cards_with_counts[i][1] >= k:
                cards_with_counts[i][1] = 0
                cards_with_counts[i + 1][1] += k - 1
        else:
            cards_with_counts[i][1] = min(k - 1, cards_with_counts[i][1])

    result = sum(map(lambda x: x[1], cards_with_counts))
    print(result)

The problem of my approach is that it can pick the wrong iteration order that is not the optimal one. For this case, “2” needs to be picked first to get the answer, but the approach above does not guarantee that.

7 2
4 2 1 100 5 2 3

---

# Optimal
4 (2) 1 100 5 (2) 3
4 4 1 100 5 3
1 1 100 5 3
100 100 5 3
5 5 3
3 3
3

What I've missed

Editorial

I browsed some YouTube videso talking about this problem. They look at sample input/output and seem to notice that there are two cases

1. if there are any cards with >= k copies => The answer is k - 1
   • Let's say we have three cards; x, y, and z. if we have more than or equals to k copies of x, we can remove the copies and add k - 1 copies to y. As a result, the number of copies of y exceeds k (the number of copies of y is at least 1 + k - 1 converted from x). Now, we can remove all the copies of y and convert k - 1 copies into z. The number of z copies is more than or equals to k, and by doing the operation, the number of z copies can be reduced to k - 1.
2. if there is no cardd with k >= copies <=> all cards have only < k copies => The answer is n
   • Because we cannot do the operation

from collections import defaultdict


t = int(input())

for tc in range(t):
    n, k = map(int, input().split())

    cards = list(map(int, input().split()))
    ct = defaultdict(int)

    ans = n

    for c in cards:
        ct[c] += 1
        if ct[c] >= k:
            ans = k - 1
        break

    print(ans)

I'm not confident I can solve this problem the next time I encounter it, but maybe I can start with carefully observing sample input/output before thinking about algorithms.

I finished Grind75 with my friends, but I feel that LeetCode problems and competitive programmiings are totally different. I'm not good at both of them and might be wrong with the feeling tho.

What is Apache server

Read official documentations

• About Apache

Apache is a server software used to run a HTTP server. I’ve been using Nginx, so this is the first time I touched this.

$ brew install apache2  # install Apache in Mac OS
$ brew services start httpd  # run the server
($ brew services restart httpd  # restart)
($ brew services stop httpd  # stop the server)

$ pwd
/opt/homebrew/etc/httpd
$ vim httpd.conf  # Change DocumenrRoot or Listen as you want

$ curl localhost:8080
<h1 id="index">Index</h1>
<p>Hello, world!</p>

I've been thinking about how to host this nippo. GitHub Pages is the easiest option, but using it does not provide me with experience of managing infrastructures.

Hosting a Mastodon instance was interesting.

Protein chips 150 Yogurt 650 Coffee 100 Avocado rolls 300 Poke 600 Bubble tea 300

Total 2100 kcal

TODO:

• Codeforces Round 943 (Div. 3)
  • Let's carefully observe sample input/output before jumping onto implementation

index 20240430 20240502