# Palindrome

This post is in reference to CodeForces Palindrome.

The question is: given a string, can you find the longest palindrome sub-sequence?

N.B. A sub-sequence of a string is what remains after removing any characters you’d like, keeping the order unchanged. Sub-sequences of are , , , , etc. The following are not: , , , .

The solution uses dynamic programming on a 2D vector, with input string along both the top and side. The number of cells is .

Grid[row][col] means “longest sub-sequence within input sub-string [col…row]”. The grid is calculated from top to bottom, each row from right to left.

Example input =

Explanations:

N.B. LCPal is Longest Common Sub-Sequence Palindrome

1. LCPal of “” is “
2. LCPal of “” is “
3. LCPal of “” is “” (taken from row above)
4. LCPal of “” is “” (take the match plus row/column above/beside, which is empty)
5. LCPal of “” is “” (taken from column beside)
6. LCPal of “” is “” (taken from row above)
7. LCPal of “” is “” (take the match plus row/column above/beside), and that’s the final answer

And an implementation note: because each row only requires the previous, I don’t keep all rows in memory — just two.

My solution is in git and below:
Continue reading

# Stadium and Games

This post is in reference to CodeForces Stadium and Games.

Let’s look at a subset of inputs, and see what shakes out.

N.B. From problem description

– Phase 1: total of halves removed
– Phase 2 input: number of teams minus phase one
– Phase 2 output: phase-2-input * ( phase-2-input — 1 )/2

```x (binary)  phase-1 phase-2-input
1 (1b)      =  0       1
3 (11b)     =  0       3
5 (101b)    =  0       5
7 (111b)    =  0       7
9 (1001b)   =  0       9
11 (1111b)  =  0       11

x (binary)  phase-1 phase-2-input
2 (10b)     =  1       1
6 (110b)    =  3       3
10 (1010b)  =  5       5
14 (1110b)  =  7       7
18 (10010b) =  9       9
22 (11110b) =  11      11

...

x (binary)  phase-1 phase-2-input
8 (1000b)     =  7       1
24 (11000b)   =  21      3
40 (101000b)  =  35      5
56 (111000b)  =  49      7
72 (1001000b) =  63      9
88 (1111000b) =  77      11
```

First, notice the phase-2-input in each case: it’s strictly increasing. And phase-2-output (on this strictly increasing input) is strictly increasing. And phase 1 is strictly increasing too. Therefore, it’s safe to say that the total result on any series of inputs having the same number of ending-zeroes is strictly increasing.

This means we can perform a binary search on each group of partitioned inputs, for the given result. So, explicitly:

– Series 0: 1, 3, 5, 7… with no zeroes attached to the back
– Series 1: 1, 3, 5, 7… with 1 zero attached (yielding 2, 6, 10…)
– Series 2: 1, 3, 5, 7… with 2 zeroes attached
– etc.

Also notice that any number is part of exactly one series: if it ends in 1 zero it’s in series 1, ends in 14 zeroes it’s in series 14, etc. Therefore, all possible answers are searched.

(Also, notice the phase-1 to phase-2-input ratio in each series is the same. This is useful during implementation.)

With that, here it is in git and below:
Continue reading

# Long Jumps

This post is in reference to CodeForces Long Jumps.

You have a ruler of length with various distances marked off. Any distances between two markings/endpoints can be measured exactly.

You are given two lengths J1 and J2: can they be measured by the ruler exactly? If not, can we get there by adding a single marking?

To solve:

1. Iteration is done over each marking. With each marking we ask the following:

1a. Does exist?
1b. Does exist?

If both 1a and 1b check out, it’s solved: no additional markings required.

2. Iterate again as before, asking the following:

2a (Stacking): Does exist? If so, it is solved: we make our additional marking at (or ).

2b (Subtracting): Making sure > , does exist? If so, it might be solved: we make our additional marking at or if that exists on the ruler. (However it might fall off one or both ends.)

And finally, the “does it exist” test takes using binary search. The total time is .

My solution is in git and below:
Continue reading

# Table Decorations

This post is in reference to CodeForces Table Decorations.

You have 3 piles — of size A B & C — and you can take a triplet from them as long as you take from more than one. So what is the maximum number of triplets?

e.g.
Piles : take ,, and .

N.B. we have left over which can’t be used.

I must admit, when I began to work on this, I took the wrong track. I tried to iterate over the input, pulling out triplets in a greedy fashion. This pile is biggest so take from that. But do I take 2 plus 1 from the next? Or take from all? And because the inputs are so large, how many triplets do I pull at once? How do I guarantee I’m making the best next move? etc.

But no, we aren’t calculating a list of triplets, just how many. So the question becomes: which inputs can’t be used? Then everything else can be, it doesn’t matter how exactly.

If > , we can’t use anything above . And the same for B &  C. So, after these are chopped off, we get the following:

# Dreamoon and WiFi

This post is in reference to CodeForces Dreamoon and WiFi.

We must move to a given position in the given number of moves; each move is either to the left or right. How many distinct paths are there?

E.g. We must move one to the right in 9 moves. One path is shown here:

So, to move over one spot in 9 moves requires 5 right (RRRRR) and 4 left (LLLL). The question simplifies down to the following:

How many different strings can be made by rearranging RRRRRLLLL?

This simplifies even further to this: How many different ways can we assign 5 R’s to 9 spots? Since once the R’s are given, the L’s positions are known — the places remaining. And we can go from the other way: How many ways can we assign 4 L’s to 9 spots? It’s the same thing, again because assigning L’s is assigning R’s.

The solution is found using the binomial coefficient function .

The factorial form is .