More programming problems

I kinda failed today's round. But oh well.

Problem A:

This is very simple implementation.

Problem B:

We just keep track of the sum of the differences between increasing columns for all intervals $[0,i]$ in an array $d$. Then we can get the jump damage for any $[i,j]$ interval using $d[j]-d[i]$.

Problem C:

A bracket sequence is regular (RBS) if and only if:

1. number of '(' = number of ')',
2. for every prefix: number of '(' $\geq$ number of ')'.

Idea 1: Iterate from left to right through $s$, whenever we meet a '?' determine if it may be replaced by a '(' and a ')'.

Replacing '?' with '(' can never break condition (2), however to satisfy (1) we need to ensure that we do not replace so that number of '( > number of ')'.

Replacing '?' with ')' requires that the current nesting depth is $>0$. Furthermore, we must not use too many such that we number of '(' < number of ')'. Additionally, we need to ensure that this replacement does not violate (2) which can occur even if the nesting depth is $>0$. For example in '(?)?' the first question mark is at nesting depth $1$, however if we replace it with ')', the sub-segment $[1,3]$ has more ')' than '('. However, I am not sure how to make this work.

In the end I used a hint from the editorial. Apparently problem D was easier than C, I noticed this in contest but was too stubborn to switch.

Reviewing codeforces 808

Problem A:

We observe that for $a_1$ to be turned to $0$, we need $a_1$ to be a multiple of $a_0$. If this is not the case then the answer is no. Else we can make $a_1=a_0$, so we can inductively repeat the argument. Hence we only need to check that $a_i$ is a multiple of $a_0$ for $1\leq i<n$.

Problem B:

We observe that $\gcd(i, a_i)\in\{1,...,i\}$. Then we must have $\gcd(i,a_i)=i$. Suppose not, then $\gcd(i-1,a_{i-1})$ has $i-2$ possible values, $\gcd(i-2, a_{i-2})$ has $i-3$ possible values, ..., $\gcd(1,a_1)$ will have no possible values. This means that $a_i$ must be any multiple of $i$ in the range $[l,r]$, for $1\leq i\leq n$.

Problem C:

We observe that if we can take $x$ tests, then we can take $x-1$ tests. Therefore, we can do a binary search. How can we check if we can take $\geq x$ tests? We iterate through $a$ maintaining the current IQ $k$ and current tests taken $c$. If $k\geq a[i]$, then it definitely won't hurt to take test $i$. If $k<a[i]$, then we should only take the test $i$ if we have $n-i\leq x-curr$, i.e. the number of tests remaining is at most the number of tests needed to hit our minimum target of $x$ tests taken. The intuition is that taking such a test earlier decreases our IQ, so it may prevent us from taking a test we could otherwise have taken.

Problem D:

I did not get very far on this problem. I will update this section later once/if I solve it.

Wrapping my head around network sharding

It is well known that traditional blockchains have all nodes store and verify the entire state, as well as process all transactions. As a result, the transaction throughput is much lower (<15 tx/s) than for transactions on centralised networks (visa ~1500 tx/s). Sharding is a promising concept which aims to improve this transaction rate for blockchains while upholding decentralisation and security.

The basic question is: do we really need all nodes in the network to verify every single transaction? 

Ideally, we want to partition the network into $K$ sets of validator nodes, each able to verify and add transactions securely in parallel, thus increasing the transaction throughput by a factor of $K$.

This is called network sharding, where we form groups of validator nodes in order to process transactions in parallel. However, if the groups are formed naively, it is possible to overpower a shard with fewer resources because the number of validators in a shard are < the total number of validators. To overcome this we can sample the validors in each shard at random, which means that the attacker can not force himself into a single shard so easily. In practice, we can achieve this by randomly shuffle the list of validators and allocating the first set of validators in the shuffled list to shard $1$, the next set to shard $2$ and so on.

To illustrate this, we analyse the scenario of having $N$ validator nodes in total (all of equal weight/power in the consensus mechanism, PoW/PoS/etc...) and $K$ shards of $X=N/K$ validators each. Suppose there are $M$ malicious nodes and that the rest ($N-M$) are honest. Fix a shard $1\leq i\leq K$, we want to know how large $M$ needs to be in order to have $>X/2$ malicious nodes in shard $i$.

We have ${N \choose X}$ validator groups possible for shard $i$, each of which is equally likely and

$$S=\sum_{j=0}^{X/2}{{M \choose j}{N-M \choose X-j}}$$

ways to choose validator groups for shard $i$ with $\leq X/2$ malicious nodes. This means that the probability of having $\leq X/2$ malicious nodes in shard $i$ is $\frac{S}{{N \choose X}}$.

Say $N=100$ and $K=10$ so that $N/K=10$. If we assume that $M=30$, then we have a

$$\frac{\sum_{j=0}^{5}{{30 \choose j}{100-30 \choose 10-j}}}{{100 \choose 10}}=0.96$$

probability of shard $i$ having $\leq 50$ malicious nodes. This makes it almost infeasible to force ones way into a shard. Below is a graph showing the probability of malicious nodes overwhelming a shard as $M$ varies.

The next question is then: how do we allocate transactions to our validator groups/shards?

This question is decided by transaction sharding mechanisms, but I will end this post here.

Codeforces: The third problem

I couldn't take part in the round today because I was playing tennis =) . Anyway problem C had 2500 solves so I thought I would give it a go.

We are given a permutation of the numbers from $0$ to $n-1$ and are asked to find the number of permutations $b$, from $1$ to $n$ such that for every $1\leq l<r\leq n$, MEX$(a_l, ..., a_r)=$MEX$(b_l,...,b_r)$. Here the MEX of a sequence of numbers is the smallest non-negative number not in the sequence.

So we first observe that any sub-array which includes $0$ in $a$ must also include $0$ in $b$. Therefore, the position of $0$ in $b$ is the same as its position in $a$. Similarly, the position of $1$ is the same in both $a$ and $b$ since if it changes some sub-array whose MEX was $1$ will now be $>1$ or some sub-array whose MEX was $>1$ will now be $1$. This lead me to the following observation.

We want to make sure that all sub-arrays with MEX$=0,1,2,...,n-1$ keep their MEX unchanged. For MEX=0, this means the $0$ staying in the same position. For MEX$=1$, the same. Now for MEX$=2$, we observe that these sub-arrays must contain $0$ and $1$. Let pos$[i]$ be the position of $i$ in $a$. Then we have two cases.

Case 1: $\min(\text{pos}[0],\text{pos}[1])<\text{pos}[2]<\max(\text{pos}[0],\text{pos}[1])$.

Then the exact position of $2$, so long as it remains in this range, does not change MEX$=2$ intervals. This is because for a MEX of $2$, we need to include both $0$ and $1$ and so moving the $2$ around will not change the MEX of intervals which do not include either $0$ or $1$ in this case.

Case 2: $\min(\text{pos}[0],\text{pos}[1])>\text{pos}[2]$ or $\text{pos}[2]>\max(\text{pos}[0],\text{pos}[1])$.

Then $2$ cannot be moved at all in $b$.

In general for any $i$, we let $l=\min(\text{pos}[0],...,\text{pos}[i-1])$ and $r=\max(\text{pos}[0],...,\text{pos}[i-1])$. Then for case 1 we need $l<\text{pos}[i]<r$. 

So now we can easily find if an $i$ can be moved, and a rough range of positions it must stay within (namely $(l,r)$) . However, we need to figure out for each $i$, how many positions it can be moved to, i.e. how many elements it can swap with in $a$. Note that this will result in double counting, so we only consider for each $i$, the number of elements $>i$ that it can swap with.

If we have case 2 for some $i$, then the number of elements it can swap with is $0$. If we have case 1, then we have $r-l+1$ elements in the range $[l,r]$ of which $i$ of them are $<i$. The remaining $r-l-1-i$ elements are larger than $i$ and can be swapped with $i$ safely. Therefore, we can multiply our answer by $r-l+1-i$ every time we enter case 1.

This leads to an $O(n)$ solution basically using a two pointers method with $l$ and $r$ to maintain the range. Quite a nice problem! For me the hardest part was figuring out the correct approach to count the number of elements each $i$ can swap with.

Codeforces: Permutation Graph

We are given a permutation of $1,2,...,n$, $a_1, a_2, ..., a_n$. Construct the undirected graph with vertex set $1, 2, ..., n$ and $(i, j)$ an edge iff $\min_{k=i}\{a_k\}=a_i$ and $\max_{k=i}\{a_k\}=a_j$ or the reverse. Find the shortest path from vertex $1$ to $n$. Here $n\leq 2.5\times 10^5$.

The main idea:

Firstly, we observe that a $(1,n)$-path always exists since for any vertices $i$ and $i+1$ we have the edge $(i,i+1)$.

Consider the element with value $1$, say it is at position $i$. Similarly, the element with value $n$ at position, say $j$.

$$a_1, ..., a_i, ..., a_j, ..., a_n$$

We have the edge $(i, j)$. Additionally, there can be no edge $(x,y)$ with $x<i$ and $y>i$ or $x < j$ and $y>j$. Therefore, the shortest path must take the edge $(i,j)$, and we can apply a divide-and-conquer strategy on the sub-arrays $a_1, ..., a_{i-1}$ and $a_{j+1}, ..., a_n$. This can be implemented in linear time.

Happy days + learning cryptography

I'm pretty happy today since I managed to solve 3 problems in codeforces and had the idea for problem D (a binary search based solution) but could not figure out the implementation details in time.

I am trying to learn some cryptography so that I can better understand blockchain technology. I am following Prof. Shafi Goldwasser's (a legend in computer science) lectures to do this. I will use this post to record some notes on the first lecture.

First some important notation is introduced. We define an encryption scheme as a triple $(G,E,D)$ where

• $G(1^k)$ outputs a secret key of length $k$.
• $E(sk, m)$ takes a secret key and a message and outputs ciphertext.
• $D(sk, m')$ takes a secret key and a ciphertext and outputs plaintext.

We also assume a message space $M$ which defines a probability distribution over all possible messages, a key space $K$, and a ciphertext space $C$, which is just a probability distribution which is dependent on $M$ and $K$.

Note that $G$ must be probabilistic in the sense that its output must define a probability distribution. If not our adversary could easily decrypt any ciphertext since there exists only one secret key for each $k$. If we allow $E$ to be probabilistic then we could have many possible ciphertexts for the same message. Similarly, if $D$ is probabilistic, we allow for a ciphertext to have many possible plaintexts. For this to make sense, we demand that w.h.p the decryption is correct.

By correctness, we mean the following: $D(sk, E(sk, m))=m$. Additionally, we need security, i.e. it should be hard for our adversary to decrypt the ciphertext. Usually, this is done by reduction to some "hard" problem.

Shanon secrecy is demanding that $\mathbb{P}[M=m]=\mathbb{P}[M=m \mid C=c]$, where $c=E(sk, m)$. This basically says that the attacker does not learn anything new about the message by looking at the ciphertext.

The notion of perfect indistinguishability is the condition that $\mathbb{P}[C=c \mid M=m]=\mathbb{P}[C=c \mid M=m']$. This says that for any pair of messages, by looking at the ciphertext, we cannot learn/distinguish between which message, $m$ or $m'$, was sent.

It turns out that these two concepts are equivalent. The lecture concludes by giving an example encryption scheme which achieves Shanon secrecy. This scheme is called the one-time pad:

• $G(1^k)$ outputs a random string from $\{0,1\}^k$.
• $E(sk, m)$ outputs $m \oplus sk$.
• $D(sk, m')$ outputs $m' \oplus sk$.

This works because $(m \oplus sk) \oplus sk = m$. Additionally, it can be shown that one-time pads achieve Shanon secrecy, however, a one-time pad can only send one message with the same secret key, if it sends two we no longer have Shanon secrecy.

Some codeforces problem + a little puzzle

We are given some array $a$ of length $n$ which is initially populated with only $0$'s. We also have a pointer which starts pointed at the first element of $a$. Given the pointer is at position $i$, we can make the following moves:

• add $1$ to $a[i]$ and move the pointer one to the right, or
• subtract $1$ to $a[i]$ and move the pointer one to the left.

We are given some target array of length $n$. Can we transform $a$ into the target array such that the pointer also ends at the first element in $a$?

We first note that because the pointer must start and end in the first position of $a$, the target array sum must be $0$. Additionally, if we look at what a move is actually doing on the following example:

$a_1, a_2, a_3, a_4, a_5$

+     +     +     + 

       -     -     -     -

The overlapping + and - just cancel out and so the operation actually has the form +...+_____-

We observe that whenever we have a - we must also have at least one + preceding it by the move's anatomy. Thus the prefix sums must be non-negative. It turns out this condition is also sufficient.

Extra puzzle:

Imagine $n$ glasses upside-down on a table. In one move, we can flip any group of $n-1$ glasses. For which values of $n$ can we turn the glasses up? For these values of $n$ devise an algorithm for doing so in the minimum number of moves.

So first we note that when $n=1$ it is clear that it is impossible. For $n=2$ it is trivially possible. For $n\geq 3$, we need to think a little bit.

In order to flip every glass over, we need to flip each glass an odd number of times. Consider the following procedure.

• number the glasses from $1$ to $n$.
• for every $g=1$ to $n$, flip all glasses except for glass $g$.

Fix any glass $g$, it is flipped $n-1$ times by this procedure. Thus if $n$ is even, all glasses will be turned over. The remaining questions are:

1. What about $n>1$ odd? (Conjecture, it is not possible)
2. Is our algorithm for even $n$ optimal. (Conjecture, yes)

Note that we will never flip the same set of $n-1$ glasses twice. Since the second will undo the effects of the first. Thus if it is possible it is always possible in $\leq n$ moves.

Consider odd $n$. At any given moment there must exist at least one upside-down glass. After $1\leq i<n$ moves suppose WLOG we have excluded $1, 2, ..., i$. Each of these glasses will have been flipped $i-1$ times and all others will have been flipped $i$ times. Thus for all $i<n$ we have glasses which are flipped and unflipped. Thus we need at least $n$ moves and it is impossible for odd $n$.