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$.

Line Empire Codeforces

We are given $N$ cities on an integer number line at positions $0<x_1<x_2<...<x_N$, where our capital is initially at position 0. Initially only the capital is conquered. We can make the following moves:

1. Move the capital at $x_i$ to any conquered city at $x_j$ for a price of $a\cdot |x_i-x_j|$,
2. Conquer an unconquered city at position $x_j$ where our capital is at $x_i$ for a price of $b\cdot |x_i-x_j|$ so long as all cities on path between capital and unconquered city are conquered already.

We are looking for the minimum price to conquer all cities. First let's make some observations:

• We are forced to conquer the cities in the order $x_1, x_2, ..., x_N$ because of the condition that all cities on the path from the capital to the unconquered city must be already conquered.
• The first move must be to conquer $x_1$.
• We never want to move the capital left.

Let's play with a scenario.

0 -- X1 -- X2 -- X3 -- X4

Suppose the sequence of moves which minimises the price payed ends with the capital at $X3$. Then, we must pay price $a\cdot X3$ for capital movement. Since the price function is linear, the moments  when we move the capital do not affect the cost payed for capital movement, i.e. if we move the capital from $0$ to $X1$, then to $X3$, this costs the same as moving the capital straight to $X3$ from $0$.

However, since having the capital closer to the right reduces the cost payed for conquering, we always want to move the capital right as soon as we can. Pictorially this is because if we do the conquering first we pay prices as follows

0 -- X1 -- X2 -- X3 -- X4

-------->

-------------->

--------------------->

----------------------------->

********************

Here --> is the conquering cost between the neighboring cities and *** is the capital moving cost. However, if we move the capital as soon as we can, then we have

0 -- X1 -- X2 -- X3 -- X4

------->

******

            ----->

            ******

                     ------>

                     *******

                                ------>

So, as already established the capital moving cost is the same, however, the conquering cost is much less, since we do not repeat the costs as in the first picture. In general, if the capital ends up at $X_i$, the total price payed is therefore 

$$X_i\cdot (a+b) + b\cdot\sum_{j=i+1}^{N}{X_j-X_i}=X_i\cdot (a+b)+b\cdot(S_{N}-S_{i}-(n-i)\cdot X_i)$$

We can precompute prefix sums $S_{i}$ on $X$ in $O(N)$ so that this value is computable in $O(1)$ for any $i$.

We are missing a detail: how do we know where the capital ends up at the end of a sequence of moves which minimises the price? Well we can just try every possible $0\leq i\leq N$ and keep whichever achieves the minimum price.

String equality

Hi, today I will be presenting my thoughts on a recent codeforces problem. In this problem, we are given two strings $s$ and $t$ of length $n$. We want to make $s$ equal $t$ by performing any number of the following moves on $s$:

1. if we see 'ab' we can change it to 'ba',
2. if we see 'bc' we can change it to 'cb'.

We are asked to print YES if $s$ can be made equal to $t$, and NO otherwise. Note that $n\leq 10^5$, so we need $O(n\log{n})$ or better.

Firstly, we note that both moves leave the number of occurrences of each letter in $s$ and $t$ invariant. Thus, we count the number of occurrences of 'a', 'b', and 'c' in $s$ and $t$ and check they are equal.

Obs 1: Move $1$ moves 'b' to the left, and move $2$ moves 'b' to the right.

So moves essentially shift around the 'b' 's.

Obs 2: Let $\text{pos_s}_i$ be the position of the $i$th 'b' from the left of $s$, and let $\text{pos_t}_i$ be the position of the $i$th 'b' from the left of $t$. If $s$ is made equal to $t$, then $\text{pos_s}_i=\text{pos_t}_{i}$ for all $1\leq i\leq \text{cnt}_b$. 

Since $\text{pos_s}_i<\text{pos_s}_{i+1}$, the observation follows.

Once all 'b' 's are correctly positioned (if possible), i.e. $\text{pos_s}_{i}=\text{pos_t}_i$, then we cannot perform any more moves without moving a 'b' to the wrong position. Therefore, it only remains to check that the strings are equal, if so then we return YES, else we return NO.

This can be implemented in $O(n)$.

Kickstart: Ants on a stick

This is a twist of the well known ant problem, whereby we can view ants as walking through each other when they meet. In this case, we do not seek the latest time for an ant to fall off the stick, instead we want the order by which they fall off.

The first thing I noticed was that one of the leftmost or rightmost ants, $l$ and $r$ respectively, will fall off first. This is because they will either walk straight off, or they will walk into some ant and then walk towards the end of the stick. Now we just need to decide which of the two falls off first. 

Since, we can view the ants as walking past each other when meeting, we know that the $n$ ants fall off the stick at times $t(1),t(2),...,t(n)$, where $t(i)$ is the time that the $i$th ant falls off the stick when it is alone on the stick. Then the first ant will fall off at time $\min_{i}\{t(i)\}$. Let $x$ be the ant which has this minimum value of $t(x)$. If $x$ and $l$ are facing each other, then $l$ will fall off first since $x$ and $l$ will meet at some time, forcing $l$ to fall off the stick first. There are other cases to examine, but we have now made the main observations.

Binary string

 The problem link is here: https://codeforces.com/contest/1680/problem/C.

My approach and thoughts:

Let b start with $x$ zeros. We simplify the problem to only have deletions from the left side.

Let $s[i]$ denote the number of $1'$s in positions $[0,i)$. We want to delete prefix $[0,i)$ which minimises $\max\{x-(i-s[i]), s[i]\}$.

Say prefix $[0,i)$ meets these conditions, then we delete it. Let $b'$ be the remaining binary string but reversed, where the prefix array $s$ is recomputed as $s'$. We apply the exact same method to $b'$, taking into account that we have already deleted $s[i]$ $1$'s, so the cost after deletion of prefix $[0,j)$ will be $\max\{x-(i-s[i])-(j-s'[j]), s[i] + s[j]\}$. We can repeat the same process starting from deleting the right side of $b$ and then the left.

However, this fails on input $1000110110001$. In this case it is not the case that greedily deleting the prefix which yields the lowest score is best. This is because we may use our deletions inefficiently if we restrict ourselves first to the prefix and then the suffix. In some cases, it is best to delete a bit from both sides.

So we try a binary search over the set of possible costs $[0,x]$ since if we can achieve a cost of $c$, we can certainly achieve a higher cost. The problem then becomes: how can we efficiently check if a cost of $c$ can be achieved? For a cost of $c$, we need our remaining string to have $\leq c$ zeros in it and for this string to be reached with $\leq c$ deletions of ones. Therefore, we look at the substrings with $i$ ones deleted from the left and $c-i$ deleted from the right for every $0\leq i\leq c$ and check that for at least one of them, the number of zeros is $\leq c$.

If we pre-compute an array $p$, where $p[i]$ is the position of the $i$th one from the left, we can find the substring with $i$ ones deleted from the left and $c-i$ ones from the right between positions $p[i+1]$ and $p[c-i-1]$. Also pre-computing array $z$, where $z[i]$ is the number of zeros in positions $[0,i)$, we can check in $O(1)$ time if the substring $[p[i+1], p[c-i-1]]$ has $\leq c$ zeros by checking $z[p[c-i]]-z[p[i]]\leq c$. Thus we have a $O(n\log{x})$ solution since we need $O(n)$ time for this pre-computation of arrays $p$ and $z$, and then perform $O(\log{x})$ binary search rounds each taking $O(n)$ time.

To recap, the main observations used are that binary search is an option and that by pre-computing relevant information about the ones and zeros, we can determine in $O(n)$ time if $b$ can have cost $\leq c$. Perhaps there is a faster solution although I am unaware of it.