CP Interesting Simple Problems

Some problems that don’t require coding, just logical thinking / some math

1. Finding $n$ distinct numbers such that $\max (a_1,a_2,...,a_n)-\min (a_1,a_2,...,a_n)=\sqrt{a_1+a_2+...+a_n}$ https://codeforces.com/problemset/problem/1758/D

Short problem statements

Problem: Find if the array has two numbers $a_i$ and $a_j$ such that $gcd(a_i,a_j)\ne 1$ in time better than $O(n^2)$.

• If any numbers share a prime, then their gcd will be greater than 1
• So just compute the primes, but be careful about time complexity
• You get a time complexity of $O(n\ast \sqrt{(}A)/log(A)))$
• My worry was that A (the largest possible number) would be so big that the constant term could not be ignored
• Also wait what? lets say you have a prime $a_i$ = ~1e8, and then $a_j=a_i$, this algo wouldn’t be able to catch it. You’d need to check duplicate numbers

My own questions

Combinatorics

Probability question

From squid game season 2 episode 1, do you have a better chance of survival if you go first for roulette, or second? Like assume you alternate russian roulette for the gun with 1 bullet in a barrel of 6, not resetting

Probability of not dying if you go first: 5/6 * 4/5* 3/4 * 2/3* 1/2 Probability of not dying if you go second: 5/6 * 4/5 * 3/4 * 2/3 * 1/2

But why does it feel like going second is worse?

• The first shot, the person has to deal with 1/6 chance dying
• The second shot, the person has to deal with 1/5 chance of dying
  • This is incorrect, because its actually 5/6 * 1/5 = 1/6 (them surviving, and you dying)
• first …, 1/4
• second 1/3
• first, 1/2
• second: 1/1

Counting

Derived from https://codeforces.com/problemset/problem/1912/K

how can you constructive build something like this? what is the relationship?

• Given an array $a$, If up to index $i$, there are $k$ subsequences with only zeros and length >=3, what can you say about the number of subsequences with only zeros at index $i+1$?
  • If $a[i+1]$ is not zero, then there are still $k$ subsequences
  • If $a[i+1]$ is a zero, then you have $k\ast 2$ subsequences of length greater or equal …?
    • But that is actually not correct

Consider the array $a=[0,0,0,0]$

At $i=2$, you have $k=1$ subsequence with length >= 3. At $i=3$, you have more than $k\ast 2=2$. You actually have 5 subsequences (first 3, first 4, first + last 2, first 2 + last, last 3), because its 4 choose 3 + 4 choose 4 different ways.

like if it was 101, it would be different…?