ErvinK's blog

COCI round #2
By ErvinK, 11 years ago, In English

Hello everyone,

Now that the competition is over, let's discuss the problems here. I would be thankful if someone shared some ideas about the last two problems.

  • Vote: I like it
  • +19
  • Vote: I do not like it

»
11 years ago, # |
← Rev. 8   Vote: I like it +22 Vote: I do not like it

By the way, I have made preliminary results available outside of the system here.

Regarding 5th:

Imagine you know for every cycle length how may ways there are to colour them (basically, that was 50% condition — in those cases there are only cycles).

Now, the whole graph could be split into components, where every component has a cycle (possibly of length 1) and reverse-oriented trees attached to it. Now for every cycle we multiply precomputed answers, and each of the remaining points (which are all in trees) can be coloured in one of (K-1) ways.

So the only problem left is to calculate the possible colourings for cycles. This can be done linearly.

Imagine we fix one arbitrary vertice and its colour L. Now, we'll make DP: a[i] is number of possible colourings if 0-th vertice is coloured in L and i-th vertice is coloured in L as well. If we have a cycle of length len, we'll be interested in a[len] * K (* K is from unfixing the colour L, we don't need to unfix the vertice).

Initilization: a[0] = 1, a[1] = 0 (two neighboring colors aren't allowed).

Now, for a[i], we can iterate over the last appearance of color L in [0..i-1]. It cannot be in i-1 though, so we'll have the sum over all possible j from 0 to i-2. For a fixed j, it gives us a[j] * (K-1) * (K-2)^(amount of spots in [j+2..i-1]). K-1 is colouring of spot j+1, while all other spots have to differ from 2 distinct colors (previous one (not L) and L (because j is the last colour L)). Since in every step we'll multiply most of our parts by (K-2), we can do it in O(1), and so all precomputing will take O(N).

I understand that this is might be not clear, so here's part of my code (with all of typecasting removed), which is relevant for this:

	a[0] = 1;
	a[1] = 0;
	cur = K-1;
	for (i = 2; i <= N; i++)
	{
		a[i] = cur;
		cur = (cur * (K-2) + a[i-1] * K-1) % MOD;
	}
	a[1] = 1;
	for (i = 1; i <= N; i++)
	{
		a[i] = (a[i] * K) % MOD;
	}

Hope it helps!

UPD: Also read explanation by Chortos-2 few comments below. It's way better than my rushed attempt at explaining.

→ Reply
  • »
    »
    11 years ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

    Thank you!

    → Reply
  • »
    »
    11 years ago, # ^ |
    ← Rev. 8   Vote: I like it +25 Vote: I do not like it

    Okay, let me try to explain things. I also have a simpler derivation of the loop algorithm. (Frankly, I have little idea what eduardische is talking about in his and how it corresponds to his code.)

    Let’s start from the start. So we have N pictures and K colours. For each picture, we also have a constraint that says its colour must differ from that of picture fi. We can see this data as a graph: each picture is a vertex, each constraint is an edge, and we want to paint each vertex in a colour distinct from those of all its neighbours. This is well-known as the graph colouring problem. The problem we have here differs from the usual in two ways: first, we need to find the number of ways to produce a colouring, not an actual colouring; second, we have interesting restrictions on the edges that our graph contains.

    Let’s think about what edges we are dealing with. We have one fi for each vertex, and we can represent it as an outgoing directed edge. If we do this, we see that each vertex has exactly one outgoing edge (but possibly many incoming edges).

    Can our graph contain cycles? Yes, but every cycle member’s sole outgoing edge will need to participate in the cycle, so any cycles we get will have to be simple, directed cycles, and no cycle will have any edges going out of it.

    What if some edges point into the cycle? Well, let’s just imagine one such edge. It comes from some vertex outside of the cycle. That vertex can have more edges pointing to it from other vertices. But one thing is clear: all these vertices have used up their sole outgoing edge on the path leading to the cycle, so we can’t encounter any edges that point in the other direction. This means that these vertices and edges form a tree, and by extension that there can’t be any other cycle connected to this structure.

    Thus each connected component of the graph (note that there may be many of them) is a single simple, directed cycle with any number of directed trees rooted at members of the cycle. Do we always have a cycle? Yes, with this problem’s input format, we do. Some cycles might have length 2 (a multiple edge) or 1 (a loop), which is unusual, but in this case we actually want to keep them. This is why fi = i is allowed.

    Clearly we can colour each connected component independently from all others, so the total answer for the whole graph is the product of the answers for all individual components. We can now focus on a single component.

    We know we have a cycle, so let’s start colouring from there. If we can colour the cycle somehow, we’ll be left with the trees hanging off to the side. Each tree’s root will have a fixed colour, so each of its children will have K - 1 colour choices. Each of their children, too, will have K - 1 choices, because they are only directly connected to their parent, which is only one. So for each vertex in a tree we have K - 1 choices (any colour that’s different from that of its parent), and of course we multiply these numbers together.

    How do we deal with cycles then? This is what eduardische focuses his explanation on.

    Pick an arbitrary vertex in the cycle to start with. Nothing else has a colour yet, so give it an arbitrary one: K choices. The next vertex now has K - 1 choices, and, similarly to tree nodes, so does the one after that and the one after that. So does every vertex except the last one: the last one has two neighbours that have colours! Is it K - 2? But the neighbour colours might be the same. So if the next to last vertex has a colour that matches the first vertex, the last factor is K - 1, but if it doesn’t, then it’s K - 2.

    How do we know whether it has a colour that matches the first vertex? We can just alter the way we compute the product to make sure we know this. Instead of counting the number of possibilities to colour the first i vertices of the cycle, let’s compute two numbers: the number of possibilities such that the ith vertex matches the colour of the first vertex and such that it doesn’t. We can easily do this using the code at the bottom of this post (Codeforces doesn’t format it properly if I use any formulæ later in the post). To match the colour, we have to use the same colour as that of the first vertex (1 choice) and the previous vertex must have a different colour. To have a mismatch, we can either take the preceding match and add an arbitrary mismatching colour (K - 1) or take one that’s already a mismatch and add another colour that matches neither the previous vertex nor the first vertex of the cycle (K - 2).

    What’s the answer for the whole cycle? Well, it’s the number of possibilities to colour all vertices such that the last does not match the colour of the first. Here’s a catch: what if the last vertex is the first? Then we can colour it however we want, so the answer is K. In all other cases it’s mismatch[loop length].

    This code can be further simplified by noting that match[i] is always equal to match[i-1]. We can replace match[i-1] in the mismatch calculation with mismatch[i-2] and get rid of match altogether.

    Now we know how to calculate everything! But we need to know where the cycles and the trees are. We can achieve this by doing a depth-first search on the graph: whenever we encounter a vertex that we’ve already started but not yet finished processing, we know we’ve hit a cycle. Note that the memory limit on this problem is quite tight, and I had to rewrite my DFS without recursion to pass one particular test case. The DFS eduardische has is also non-recursive.

    The code promised above:

    match[1] = K
mismatch[1] = 0
for i = 2 to N:
	match[i] = mismatch[i - 1] * 1
	mismatch[i] = match[i - 1] * (K - 1) + mismatch[i - 1] * (K - 2)
    → Reply
    • »
      »
      »
      11 years ago, # ^ |
        Vote: I like it +5 Vote: I do not like it

      Very clear explanation, thank you!

      → Reply
»
11 years ago, # |
  Vote: I like it +5 Vote: I do not like it

Any advice for 4th ( Putnik).

→ Reply
  • »
    »
    11 years ago, # ^ |
    ← Rev. 2   Vote: I like it +12 Vote: I do not like it

    I think I can do way better at explaining this than what I did on 5th :)

    Imagine our sequence of visiting cities. Where is city #1 in this sequence? Could be anywhere.

    Now, where is the city #2? It's clear to see that it has to be immediately next to 2 (from either side) — if there is a free space between 1 and 2, there will be a number > 2 between them, and hence for it we'll get a situation where smaller number are on both sides.

    In general, let's have an inductive claim. If we have placed city from #1 to #N in our sequence, where can city #(N+1) be? We can't put it inside the segment, because all existing numbers are smaller than it, so we'll violate the property. This leaves two possibilities, in the beginning or in the end.

    So, let a[l][r] be the minimum amount travel needed to travel from l to r, using all cities from 1 to max(l,r). Now from a[l][r] we have to put next number d = max(l,r)+1, and we can update two values: push (dist[d][l] + a[l][r]) to a[d][r] and (a[l][r] + dist[r][d]) to a[l][d].

    The answer is in a[1][N]. If we process values a[l][r] in order of increasing max(l,r), we'll have no problems as well. The only initialization is a[1][1] = 0.

    If you're interested, my code is in edit.

    → Reply
    • »
      »
      »
      11 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Maybe a simpler way to look at it is to understand that the problem asks to cover 1, 2, 3 .... n with at most 2 not intersecting paths starting at 1

      → Reply
      • »
        »
        »
        »
        11 years ago, # ^ |
        ← Rev. 2   Vote: I like it +8 Vote: I do not like it

        Another way to put it: a good path is one that consists of a descending sequence of numbers (down to 1) followed by an ascending sequence.

        But this alone doesn’t help much. It’s just a simplification the problem statement. Which is a good first step but is merely a first step towards the solution.

        → Reply
        • »
          »
          »
          »
          »
          11 years ago, # ^ |
            Vote: I like it -9 Vote: I do not like it

          If one does not distinguish between ascending and descending sequences but considers just 2 not intersecting sequences starting from 1 then the rest is 'obvious' dynamics

          → Reply
    • »
      »
      »
      11 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      My approach is similar to yours. In my code d[i][j] (j<i) indicates the optimal path length from j to i using all cities from 1 to i. The answer is then the smallest of d[n][i] i=1...n-1

      here is my code: http://pastebin.com/iQRQhvNa

      → Reply
»
11 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Results are available.

→ Reply
»
11 years ago, # |
  Vote: I like it 0 Vote: I do not like it

How can I submit solutions for the tasks of COCI 2013/2014 round #1 ????

→ Reply
  • »
    »
    11 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    You probably can't. The contests in analysis mode are removed from the contest site after several weeks, probably to avoid having a looong list of contests to choose from.

    You can download the testdata and try running your program on them, though.

    → Reply
  • »
    »
    11 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    You can. Go to dl.gsu.by register there. Choose the course "olympiad in informatics" and solve COCI #1 there.

    → Reply