### Problem A - IQ Test

We can store two values,*count*

_{odd}and

*count*

_{even}, as the number of odd or even elements in the series. We can also store

*last*

_{odd}and

*last*

_{even}as the index of the last odd/even item encountered. If only one odd number appears --- output

*last*

_{odd}; otherwise only one even number appears, so output

*last*

_{even}.

### Problem B - Telephone Numbers

There are many ways of separating the string into clusters of 2 or 3 characters. One easy way is to output 2 characters at a time, until you have only 2 or 3 characters remaining. Here is a possible C++ solution:<code>

for( i=0; i<n; i++ )

{

putchar(buf[i]);

if( i%2 && i<n-(n%2)-2 ) putchar('-');

}

</code>

### Problem C - Roads in Berland

If you are familiar with the Floyd-Warshall algorithm, then this solution may be easier to see.Initially, we are given a matrix

*D*, where

*D*[

*i*][

*j*] is the distance of shortest path between city

*i*and city

*j*. Suppose we build a new road between

*a*and

*b*with length shorter than

*D*[

*a*][

*b*]. How do we update the rest of the graph accordingly?

Define a new matrix

*D*', whose entries

*D*'[

*i*][

*j*] are the minimum path distance between

*i*and

*j*while taking into account the new road

*ab*. There are three possibilities for each

*i*,

*j*:

*D*'[*i*][*j*] remains unchanged by the new road. In this case*D*'[*i*][*j*] =*D*[*i*][*j*]*D*'[*i*][*j*] is shorter if we use the new road*ab*. This means that the new path*i*,*v*_{1},*v*_{2}, ...,*v*_{n},*j*must include the road*a*,*b*. If we connect the vertices*i*,*a*,*b*,*j*together in a path, then our new distance will be*D*[*i*][*a*] +*length*(*ab*) +*D*[*b*][*j*].- Lastly, we may have to use the road
*ba*. (Note that this may*not*be the same as road*ab*.) In this case, we have*D*'[*i*][*j*] =*D*[*i*][*b*] +*length*(*ab*) +*D*[*a*][*j*].

*i*,

*j*within the graph. Then we must sum shortest distances between cities. Updating the matrix and summing the total distance are both

*O*(

*N*

^{2}), so about 300

^{2}operations. Lastly, there are at most 300 roads, so in total there are about 300

^{3}operations.

One thing to note is that the sum of all shortest distances between cities may be larger than an int; thus, we need to use a long when calculating the sum.

### Problem D - Roads not only in Berland

Before we start this problem, it is helpful to know about the union find data structure. The main idea is this: given some elements *x*

_{1},

*x*

_{2},

*x*

_{3}, ...,

*x*

_{n}that are partitioned in some way, we want to be able to do the following:

- merge any two sets together quickly
- find the parent set of any
*x*_{i}

Back to the problem: Every day we are allowed to build exactly 1 road, and close exactly 1 road. Thus, we can break the problem into two parts:

- How do we connect the parts of the graph that are disconnected?
- How do we remove roads in a way that does not disconnect parts of the graph?

*build*be the list all roads that need to be built, and let

*close*be the list of nodes that need to be closed. We can show that in fact, these lists are of the same size. This is because the connected graph with

*n*nodes is a tree if and only if it has

*n*- 1 edges. Thus, if we remove more roads than than we build, then the graph is disconnected. Also, if we build more roads than we remove, then we have some unnecessary roads (the graph is no longer a tree).

Now consider the format of the input data:

*a*

_{1},

*b*

_{1}

*a*

_{2},

*b*

_{2}

...

*a*

_{n - 1},

*b*

_{n - 1}

We can show that edge (

*a*

_{i},

*b*

_{i}) is unnecessary if and only if the nodes

*a*

_{i},

*b*

_{i}have already been connected by edges (

*a*

_{1},

*b*

_{1}), (

*a*

_{2},

*b*

_{2}), ..., (

*a*

_{i - 1},

*b*

_{i - 1}). In other words, if the vertices

*a*

_{i},

*b*

_{i}are in the same connected component

*before*we, add (

*a*

_{i},

*b*

_{i}) then we do not need to add (

*a*

_{i},

*b*

_{i}). We can use union-find to help us solve this problem:

<code>

for( i from 1 to n-1 )

{

if( find(

*a*

_{i})=find(

*b*

_{i}) ) close.add(

*a*

_{i},

*b*

_{i});

else merge(

*a*

_{i},

*b*

_{i});

}

</code>

In other words, we treat each connected component as a set. Union find allows us to find the connected component for each node. If the two connected components are the same, then our new edge is unnecessary. If they are different, then we can merge them together (with union find). This allows us to find the edges that we can remove.

In order to find the edges that we need to add to the graph, we can also use union-find: whenever we find a component that is disconnected from component 1, then we just add an edge between them.

<code>

for( i from 2 to n )

if( find(

*v*

_{i})!=find(

*v*

_{1}) )

{

then merge(

*v*

_{1},

*v*

_{i});

build.add(

*v*

_{1},

*v*

_{i});

}

</code>

We just need to store the lists of roads that are unnecessary, and the roads that need to be built.

### Problem E - Test

The way I solved this problem is with a hash function. Hash functions can fail on certain cases, so in fact, my solution is not 'correct'. However, it passed all the test cases =PLet the input strings be

*s*

_{0},

*s*

_{1},

*s*

_{2}. We can build the shortest solution by permuting the strings and then trying to 'attach' them to each other. I.e., we need to find the longest overlapping segments at the end of string

*a*and the beginning of string

*b*. The obvious brute force solution won't run in time. However, we can use a hash function to help us calculate the result in

*O*(

*n*) time, where

*n*is

*min*(

*len*(

*a*),

*len*(

*b*)). The hash function that I used was the polynomial

*hash*(

*x*

_{0},

*x*

_{1}, ...,

*x*

_{n}) =

*x*

_{0}+

*ax*

_{1}+

*a*

^{2}

*x*

_{2}+ ... +

*a*

^{n}

*x*

_{n}. This polynomial is a good hash function in this problem because it has the following useful property:

Given

*hash*(

*x*

_{i}, ...,

*x*

_{j}), we can calculate the following values in

*O*(1) time:

*hash*(*x*_{i - 1},*x*_{i}, ...,*x*_{j}) =*x*_{i - 1}+*a*×*hash*(*x*_{i}, ...,*x*_{j})*hash*(*x*_{i}, ...,*x*_{j},*x*_{j + 1}) =*hash*(*x*_{i}, ...,*x*_{j}) +*a*^{j + 1 - i}×*x*_{j + 1}

*a*,

*b*, we can calculate the hash functions starting from the end of

*a*and starting from the beginning of

*b*. If they are equal for length

*n*, then that means that (maybe)

*a*and

*b*overlap by

*n*characters.

Thus, we can try every permutation of

*s*

_{0},

*s*

_{1},

*s*

_{2}, and try appending the strings to each other. There is one last case: if

*s*

_{i}is a substring of

*s*

_{j}for some

*i*≠

*j*, then we can just ignore

*s*

_{i}. We can use hash functions to check that one string is contained within another one.

I don't quite understand the problem statement in problem A. Or maybe I don't understand the editorial. What about test cases like 5 1 5 7 9 11 which should have the output as 1 but the AC solution gives 5. Also what about test cases like 5 5 9 13 15 21 which should give the output as 4 but gives 5. Please help me understand the problem. I have spent quite a lot time in this.

Yeah, I also Don't understand the problem statement in problem A. Also I Don't understand the editorial of A.. Pls help..

Russian editorial is quite clear: there's only 1 odd or even number (1 even and e.g. 10 odd; 1 odd and e.g. 2 even). You have to find pos of it. My solution pass all tests: 50928772

Yeah, I understand the problem, and got AC.. But I think the statement was quite unclear..

And Thanks a lot.. #MrReDox

The author especially didn't even bother explaining the "different in evenness".

https://codeforces.com/contest/25/submission/58229465

Task D. You can also use bfs for each connectivity component and find "useless" edges for each component. Now we have number of edges and number of components(they are equal). Now iterate for(int i = 1; i < components_count; ++i) build_road(component_vertex[0], component_vertex[i]); Where component_vertex is one of the vertexes for each connectivity component. Time complexity O(N). UPD: (O(V+E), but E = n — 1 and V = n, so O(V+E) = O(N + N — 1) = O(N))

Can we use Z algorithm in E ? Cause I got TLE on test 24[submission:58414744]

KMP works fine. my_sub

For D

Alternative solution: Keep track of nodes visited. Detect cycles by dfs-ing into each seperate tree (using nodes visited). Store each cyclic edge into an array. Then itterate through the array and connect each seperate tree to create one tree.

Soltuion for D. Just find self loops,multiple edges and cycles and remove all those edges. 89373449