Editorial of MindCoding 2015 Round 2

100 - nc1c2

A simple string operations problem. Replace c1 with c2 in the string n, then cast n to an integer and print it.

Basic C solution (Marius Gavrilescu)

    1 #include<stdio.h>
    2 #include<stdlib.h>
    3 #include<string.h>
    4 
    5 int main(void){
    6     while(1){
    7         char c1, c2, n[100], *ch;
    8         scanf("%s %c %c ", n, &c1, &c2);
    9         if(n[0] == '0' && n[1] == 0 && c1 == '0' && c2 == '0')
   10             break;
   11         for (int i = 0 ; i < strlen(n) ; i++)
   12             if(n[i] == c1)
   13                 n[i] = c2;
   14         printf("%d\n", atoi(n));
   15     }
   16     return 0;
   17 }

Slightly shorter C solution (Marius Gavrilescu)

We can use the strchr function to simplify the for loop.
    1 #include<stdio.h>
    2 #include<stdlib.h>
    3 #include<string.h>
    4 
    5 int main(void){
    6     while(1){
    7         char c1, c2, n[100], *ch;
    8         scanf("%s %c %c ", n, &c1, &c2);
    9         if(n[0] == '0' && n[1] == 0 && c1 == '0' && c2 == '0')
   10             break;
   11         while((ch = strchr(n, c1)))
   12             *ch = c2;
   13         printf("%d\n", atoi(n));
   14     }
   15     return 0;
   16 }

Perl solution (Marius Gavrilescu)

We can further improve the solution by switching to another programming language.
    1 #!/usr/bin/perl
    2 use v5.14;
    3 use warnings;
    4 
    5 while (<>) {
    6     my ($n, $c1, $c2) = split ' ';
    7     exit if $n == 0 && $c1 == 0 && $c2 == 0;
    8     $n =~ s/$c1/$c2/g;
    9     say int $n;
   10 }

250 - Keitai

Keitai can be solved by generating all possible solutions and then counting them. Basically, we need to add exactly one digit to any valid position in the original number. This method grants one possible number at a time, not necessarily unique. After having generated all numbers, the duplicates can be easily erased, using a specialized data structure (C++'s set or Python's set).

    1 def solve(s):
    2     possible = []
    3 
    4     for pos in range(2, 10):
    5         for digit in range(0, 10):
    6             new = s[:pos] + str(digit) + s[pos:]
    7             possible.append(new)
    8 
    9     return len(set(possible))
   10 
   11 print solve(raw_input())

At a closer look, we start to notice that the code above outputs 73 for any given input. This is due to the fact that Keitai is not an input-dependant problem. In order to see why, try to simulate (on a piece of paper) the process described, for a shorter input number.

For all the tractor fans:

    1 print 73

500 - The Oddest Tree

In order to solve this problem, we need to use the properties of binary operation XOR. More concisely, the XOR sum of N bits provides the parity of N.

In each node we will store a binary array of length SIGMA (26 - the size of the alphabet). The ith bit is 1 if the ith letter appears an odd number of times, and 0 otherwise.

Let's take two nodes x and y. Let us use the following notation:

  • x(1), x(2), …, x(L1) - the array of nodes on the chain from 1 to x , where x(1) = 1 and x(L1) = x.
  • y(1), y(2), …, y(L2) - analoguely.

Also, let mask[x] = info[x(1)] ^ info[x(2)] ^ … ^ info[x(L1)]. The same goes for mask[y].
Let lca = LCA(x, y) (the lowest common ancestor of x and y). There exists one pair (i, j) such that:

  • 1 ≤ i ≤ L1
  • 1 ≤ j ≤ L2
  • x(i) = lca = y(j)

We take a number A. We know that A ^ A = 0, so:
mask[x] ^ mask[y] = XOR_SUM(x(p), i < p ≤ L1) ^ XOR_SUM(y(q), j < q ≤ L2)

lca lies on the chain from x to y, so the answer would be mask[x] ^ mask[y] ^ info[lca].

For any update, the mask can be calculated in contant time. The only problem left is finding the LCA in a changing tree.
This can be achived in O(sqrt(N)) or O(log(N)) (see: Stramosi).

1000 - Undo Graph

First of all, let's take a look at the 3 types of operations defined in the statement. The first operation adds and edge in the (multi)graph, the second type reverts type one operations and the third one asks whether or not two nodes are in the same connected component.

Trying to build a suitable algorithm from scratch looks tricky, so we will begin by making some observations.
Firstly, we can analyse a simpler problem, the one in which we don't have any undo operations. This would be solved using a Disjoint-set data structure. Adding an edge is equivalent to merging two disjoint sets and answering a question reduces to verifying whether or not two nodes are in the same set.

Now let's get back to the original problem. Suppose we're dealing with a small number of undo operations. In this case, it would be enough to store the entire input, and then mantain a back-up disjoint-set structure before the update. Of course, that would solve any undo operation in linear time. However, the key observation is that not all elements necessarily have to be updated (e.g. when there is just one unde operation, instead of changing just a few values, you update the whole data structure).

To enhance the performance we have to observe that a type one operation modifies O(log* N) values (on average) from the disjoint data set. This means that going one step backwards also modifies O(log* N) values. When we update we can just retain in a stack the values that we have changed. When we want to go backwards, we restore the old values mantained in the disjoint data sets. This brings our final time complexity to O(M log *N) as one operation can be done once and reversed only once, implying a constant factor of 2.

Questions?

Sponsors Gold