JOIN
 Match Editorial
SRM 255
Thursday, July 28, 2005

Match summary

In Division 1, after some time spent working on the easy problem, most coders divided into two distinct groups. The first group opened the medium problem (600 points) next, while the second went for the hard (800 points). At first glance the second group seemed to have the better approach, but many of the hard problem solutions turned out to be wrong. bladerunner took the 1st place with the help of 7 successful challenges, lovro was 2nd and Savior finished in 3rd. sabbir_yousuf became yellow by taking the 4th place. Interestingly, dexter_bg gained 297 rating points without passing any problems.

In Division 2, the top performer was Protean, followed by crem and xaep. More than 70 coders finished with all three problems correct.

# The Problems

SequenceOfNumbers
Used as: Division Two - Level One:
 Value 250 Submission Rate 278 / 308 (90.26%) Success Rate 264 / 278 (94.96%) High Score DamnEcuadorian for 249.50 points (1 mins 17 secs) Average Score 215.27 (for 264 correct submissions)

We can convert all elements of the given string array to integers and put them into some numerical array. After that we can sort new numerical array in a usual way and convert its back to the string array.

```   int[] tmp = new int[sequence.length];
for(int i = 0; i < sequence.length; i++)
tmp[i] = Integer.parseInt(sequence[i]);
Arrays.sort(ret);
for(int i = 0; i < sequence.length; i++)
sequence[i]=""+tmp[i];
```

Another way to solve this problem is to use a sort function which receives a comparing function (called 'comparator') as an argument.

```   Arrays.sort(sequence,
new Comparator<String>() {
public int compare(String a, String b) {
return new Integer(a).compareTo(new Integer(b));
}
});

```
WordCompositionGame
Used as: Division Two - Level Two:
 Value 500 Submission Rate 264 / 308 (85.71%) Success Rate 246 / 264 (93.18%) High Score agray for 488.25 points (4 mins 25 secs) Average Score 389.23 (for 246 correct submissions)
Used as: Division One - Level One:
 Value 250 Submission Rate 242 / 246 (98.37%) Success Rate 236 / 242 (97.52%) High Score antimatter for 249.20 points (1 mins 36 secs) Average Score 228.72 (for 236 correct submissions)

First, we can count how many times each word appears in the player lists. This information can be stored in associative array (like hash map). After that we can iterate over the words of each player and calculate his score. Here is antimatter C++ solution who have made this problem in 1.5 minutes.

```   string score(vector <string> a, vector <string> b, vector <string> c) {
map<string,int> C;
for (int i = 0; i < a.si; i++) C[a[i]]++;
for (int i = 0; i < b.si; i++) C[b[i]]++;
for (int i = 0; i < c.si; i++) C[c[i]]++;
int AA=0,BB=0,CC=0;
for (int i = 0; i < a.si; i++) AA += 4-C[a[i]];
for (int i = 0; i < b.si; i++) BB += 4-C[b[i]];
for (int i = 0; i < c.si; i++) CC += 4-C[c[i]];
char buf[100];
sprintf(buf, "%d/%d/%d", AA,BB,CC);
return string(buf);
}

```
KthElement
Used as: Division Two - Level Three:
 Value 1000 Submission Rate 155 / 308 (50.32%) Success Rate 75 / 155 (48.39%) High Score xaep for 854.77 points (12 mins 8 secs) Average Score 545.36 (for 75 correct submissions)

The example 2 hints how to solve this problem. Function F(N) can take a very few values within the problem limitations. So the sequence X will be repeated in first 10-25 elements and we can find its period. If we know that sequence X has a period of length L starting from the index i (i > K) the XK will be the same as the element with the index (K-i) mod L + i. Here is a sample Java code.

```   Map<Integer, Integer> seen = new HashMap();
List<Integer> sequence = new ArrayList<Integer>();
int X = 0;
for (int i = 0;; i++) {
if (seen.containsKey(X)) {
if (i > K)
return sequence.get(K);
int L = i - seen.get(X);
int ind = seen.get(X);
return sequence.get(ind + (K-ind) % L);
}
seen.put(X,i);
X = A*F(X)+B;
}

```
PluCodeGenerator
Used as: Division One - Level Two:
 Value 600 Submission Rate 59 / 246 (23.98%) Success Rate 46 / 59 (77.97%) High Score loopy for 507.11 points (12 mins 38 secs) Average Score 314.39 (for 46 correct submissions)

It is quite easy to write solution that iterates from 1 to N-1 and checks each number if it is a valid PLU code. This solution works much slower than required 2 seconds, but it is acceptable to generate all answers and hardcode each 100000th answer into array inside a solution source. After that we can start counting invalid PLU codes not from 1 but form the index that closer to N.

Another (more honest) way to solve this problem is a dynamic programming. Let function A[d1,d2,L,N] be a number of invalid PLU codes of length L that less or equal N. Moreover this function allows PLU code to start from the '0' digit and considers PLU codes started from d2 as invalid if d1=d2. Let n0 be a first digit of N and N1 be a number N without a first digit.

Now A[d1,d2,L,N] can be calculated using following algorithm (pseudocode):

```A[d1,d2,L,N] = 0;
for(char ch='0'; ch<n0; ch++)
A[d1,d2,L,N] += (d1==d2 && d2==ch) ? 10L-1 : A[d2,ch,L-1,10L-1-1];
A[d1,d2,L,N] += (d1==d2 && d2==n0) ? N1+1 : A[d2,n0,L-1,N1];

```

Using this folmula it is clear how to solve the task.

OddDigitable
Used as: Division One - Level Three:
 Value 800 Submission Rate 125 / 246 (50.81%) Success Rate 10 / 125 (8.00%) High Score Savior for 738.94 points (8 mins 18 secs) Average Score 625.64 (for 10 correct submissions)

How are the odd-digitable numbers produced? There are five one-digit odd-digitable numbers. To produce the odd-digitable number of length L (L > 1) we should get the odd-digitable number of length L-1, multiply it by 10 and add one of the one-digit odd-digitable numbers.

Let put all one-digit odd-digitable numbers into the queue, then put all odd-digitable numbers produced from 1, all odd-digitable numbers produced from 3 and so on. This way we'll get all odd-digitable numbers in the increasing order. Finally, take all numbers in the queue modulo N.

There are no sense to put duplicates into the queue because they will generate the same numbers, so we'll skip produced numbers which are already in the queue. Here is the sample Java code.

```   List<Integer> al = new ArrayList();
List<String> as = new ArrayList();
boolean[] mark = new boolean[N];
for (int i = 0; i < al.size(); i++) {
int c = al.get(i);
if (c == M && i > 0) return as.get(i);
for (int j = 1; j <= 9; j+=2) {
int x = (c*10+j)%N;
if (mark[x]) continue;
mark[(c*10+j)%N] = true;