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 abcd are acd, bd, abcd, d, etc. The following are not: acb, da, abcde, dcba.

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

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 = abbca
subseqpal

Explanations:

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

1. LCPal of “a” is “a
2. LCPal of “b” is “b
3. LCPal of “ab” is “a” (taken from row above)
4. LCPal of “bb” is “bb” (take the match plus row/column above/beside, which is empty)
5. LCPal of “abb” is “bb” (taken from column beside)
6. LCPal of “bbc” is “bb” (taken from row above)
7. LCPal of “abbca” is “abba” (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 L with various distances marked off. Any distances between two markings/endpoints can be measured exactly.

Ruler = delim{lbrace}{0, D1, D2, D3, D4, L}{rbrace}

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 M_curr we ask the following:

1a. Does M_curr + J1 exist?
1b. Does M_curr + J2 exist?

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

 

2. Iterate again as before, asking the following:

lj2

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

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

 

And finally, the “does it exist” test takes O(log{n}) using binary search. The total time is O(n log{n}).

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 delim{lbrace}{10,2,1}{rbrace}: take delim{lbrace}{2,0,1}{rbrace},delim{lbrace}{2,1,0}{rbrace}, and delim{lbrace}{2,1,0}{rbrace}.
Max triplets = 3

N.B. we have left over delim{lbrace}{4,0,0}{rbrace} 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 A > 2(B+C), we can’t use anything above 2(B+C). And the same for B & ┬áC. So, after these are chopped off, we get the following:

max triplets = floor({A_chopped + B_chopped + C_chopped}/3)

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:
rrrll

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 (tabular{000}{00}{R+L R}).

The factorial form is {(R+L)!}/{R! * L!}.

{9!}/{5! * 4!} = 126