20240622

1945A. Setting up Camp

Each introvert wants to live in a tent alone.

I can really sympathize with this. I don’t want to share a room or tent at a hotel, even with my close friends.

def solve(intr: int, extr: int, univ: int) -> int:
    while univ > 0 and extr % 3 != 0:
        univ -= 1
        extr += 1

    if extr % 3 != 0:
        return -1

    return intr + extr // 3 + (univ // 3 if univ % 3 == 0 else univ // 3 + 1)


for _ in range(int(input())):
    a, b, c = map(int, input().split())
    print(solve(a, b, c))

1944A. Destroying Bridges

def solve(n: int, k: int) -> int:
    if n - 1 > k:
        # it's impossible to isolate any islands
        return n
    else:
        return 1


for _ in range(int(input())):
    n, k = map(int, input().split())
    print(solve(n, k))

SSH and Git repositories (GitHub/BitBucket)

I thought SSH is only used to send shell commands to remote computers securely because of the name “Secure Shell,” but it can be generally used for secure authentication and communication.

RFC 4253 - The Secure Shell (SSH) Transport Layer Protocol

Abstract

The Secure Shell (SSH) is a protocol for secure remote login and other secure network services over an insecure network.

This document describes the SSH transport layer protocol, which typically runs on top of TCP/IP. The protocol can be used as a basis for a number of secure network services. It provides strong encryption, server authentication, and integrity protection. It may also provide compression.

Key exchange method, public key algorithm, symmetric encryption algorithm, message authentication algorithm, and hash algorithm are all negotiated.

This document also describes the Diffie-Hellman key exchange method and the minimal set of algorithms that are needed to implement the SSH transport layer protocol.

When used to communicate with Git repositories,

Authentication: Instead of using passwords, SSH uses cryptographic keys for authentication. I generate a pair of keys (private and public) and the public key is uploaded to the Git hosting service whereas my private key stays in my local. When interacting with remote repositories, the SSH protocol is used to verify my identity securely without sending my private key over the network.

Data Transmission: All data transmitted between my machine and Git repositories will be encrypted with the protocol, ensuring that my code will be transferred securely.

Diffie-Hellman Key Exchange

Diffie-Hellman algorithm is used to share the same secret between two parties (In my case, my computer and the GitHub server). After sharing the same secret, that can be used to communicate data.

  1. Asymmetric key exchange (the operation is expensive, so will be done only once)
  2. data transmission with a symmetric cryptography

Diffie Hellman - OpenSSLWiki

In static-static mode both Alice and Bob retain their private/public keys over multiple communications. Therefore the resulting shared secret will be the same every time. In ephemeral-static mode one party will generate a new private/public key every time, thus a new shared secret will be generated.

There are a number of standards relevant to Diffie-Hellman key agreement.

It seems there are variants of the algorithms.

Reddit: Does modern SSH always use ephemeral session keys after authentication?

IIRC, yes it’s always ephemeral. SSH does it’s “KEX” thing to generate a new symmetric key per connection and employs a re-key interval to provide forward security.

I googled a little bit, but this is the only web page referring static vs ephemeral.

I suspect that the SSH communications with GitHub (and other platforms) does not reuse the same secret for a symmetric cryptography due to security concern (ephemeral-static mode), but I'm not confident as I couldn’t find resources of that at the moment.

1942A. Farmer John’s Challenge

I'm still not confident with tackling problems with difficulty 800 no matter how many problems I solved. No matter how many problems I solved, I’m still not confident about tackling problems with difficulty 800. Maybe more experience can give me the confidence and courage to move on to more difficult problems.

I want to update the dashboard with a breakdown (like, showing the number of problems with difficulty 800 I solved), but I've been quite busy these days.. will consider adding the feature in the next long day offs.

def solve(n: int, k: int) -> list[int]:
    # all the elements have the same number => n sorted patterns
    # non-decreasing => 1 pattern
    if n == k:
        return [1] * n
    elif k == 1:
        return [1] * (n - 1) + [2]
    else:
        return [-1]


for _ in range(int(input())):
    n, k = map(int, input().split())
    print(" ".join([str(a) for a in solve(n, k)]))

Eggs 100 Bubble tea 800 Salad 500 Protein shake 500 Bagel 400 Luchable 300

Total 2600 kcal (will try to go back to the normal state tomorrow)

TODO:

index 20240621 20240623