GP of Poland - Codeforces

7 years ago, # ^ |

+15

G : We can decompose the grid into O(N + M) strips which have height or width 1 — If we build a graph for a crossing strips, the minimum number of mirrors for a cell equals to the length of shortest path.

However, the graph have too many edges (O(N²)), so we should reduce it. We can do it with a tricky application of binary trees — Build a segment tree over a [1, N] interval, which every node in a tree is some auxiliary node of a graph, and there is a directed edge from parent to vertex for each node. Now, if we want to add a edge to all vertex in interval [L, R], we can just find a relevant O(lgn) node, and add an edge to the selected O(lgn) node.

Now if we use a sweep line to make a graph, we just have to handle two queries : * Adding an edge to an interval. If the tree is appropriately constructed, then this is same as above. * Updating the vertex in the position. This can be dealt in a "persistent" manner — we can make new segment tree, with only that vertex changed, by introducing only O(lgN) new vertex.

So, we constructed a graph with |V|, |E| = O((N + M)lg(N + M)) in a reasonable time. But the story doesn’t end… we should calculate the sum of cost for each cell, which is eventually the intersection of strips. With another sweep line, this reduces to the following query problem:

a[x] = v
$\text{[math]}$

This can be done by 2d segment tree, which can be implemented as a vector of fenwick trees. Phew!

In the contest I had to implement this in only 50 minutes. I miraculously got an implementation that passes sample, 30 seconds before contest, but it unfortunately got WA :/ It turned out that changing 3 line was enough for AC, while finding the bug from 264 lines of code is a different story. Code

→ Reply

7 years ago, # ^ |

+10

Model solution also goes like that, but it uses a fact that for each cell if the distance to its row is x then the distance to its column is either x - 1 or x + 1 (different parity for rows and columns). So if for each row and column we'll take sum of its_length·distance_to_it then it'll be equal to result·2 + number_of_reachable_cells. So we second sweeping is not needed.

→ Reply

7 years ago, # ^ |

Nice observation! Now I don't need almost half of my code (including that problematic 3 line)

→ Reply

7 years ago, # |

← Rev. 2 →

+38

I've solved C in O(N * log²(N)

Note that sum of answers ≤ N * log(N) and then we can use some greedy strategy maintaining current_subtree_size - index in segment tree.

My code: https://pastebin.com/hz5wWNEd.

→ Reply

bertho_coder

7 years ago, # |

+10

How to solve E?

→ Reply

pranjal.ssh

7 years ago, # ^ |

For each vertex, we must find matchings of paths. We can pick two edges of different neighbours and match them. Almost perfect matching(depending on parity) is possible only when maximum element is no more than sum of rest. Otherwise, match everything to largest edge.

→ Reply

ainta

7 years ago, # |

How to solve A? I thought about it about 2 hours, and still have no idea..

→ Reply

7 years ago, # ^ |

We need to find minimal subset with AND equal to 0 and number of these subsets, it can be solved with AND-convolution.

→ Reply

dragoon

7 years ago, # ^ |

← Rev. 2 →

My implementation was: 20*20*2^20 (max answer 20, and nlogn = 20 * 2^20) which got tle.

→ Reply

7 years ago, # ^ |

+10

So you can use binary search by answer and get log(log)*nlog (i've solved it this way):))

Or you can find A[0] in O(n), just avoid calculating useless values, and it will be n+n/2+...+1 = O(n)

→ Reply

dragoon

7 years ago, # ^ |

How to calculate it in O(n)?

→ Reply

7 years ago, # ^ |

+10

If you know what do these values after transformation mean, then it can be deduced that you have to take sum of a_v·( - 1)^{parity of number of bits in v} and it will be equal to A₀.

300iq, what do you mean by $\text{[math]}$ ?

→ Reply

MrDindows

7 years ago, # ^ |

← Rev. 2 →

I think it's something like:

ll restore(int *y, int n) {
    if (n == 1) {
        return *y;
    } else {
        n /= 2;
        return restore(y + n, n) - restore(y, n);
    }
}

Or same, but not recursive implementation. This is obtained explicitly from the inverse transformation function.

→ Reply

7 years ago, # ^ |

But anyway you have to do transformation for first time, don't you? So complexity remains O(n·log(n)), yea?

→ Reply

MrDindows

7 years ago, # ^ |

Yes, I think he wrote O(n) about A₀ calculation part, which should be done log(n) times.

→ Reply

7 years ago, # ^ |

Yup

→ Reply

jqdai0815

7 years ago, # |

How to solve F and J?

For problem J, I see many Russian team solved it easily. I can't squeeze my solution into TL.

I also have a question about the intended solution of problem I. I implemented a solution with time complexity $\text{[math]}$ . I also spent many time on optimization.

→ Reply

7 years ago, # ^ |

You don't need log(m) in I I think, you can precompute all gcds and all powers of k. When you have fixed partition you should calculate some dp with m states, each of them in O(m) time. Calculating this dp goes as follows: iterate over length of cycle (in permutation of m elements) which contains 1, denote it by i and take dp[m - i] multiplied by something. This "something" is multiplication of some factorials and a value assigned to i. You can precompute all these assigned values once when you have fixed partition of n, just by iterating over i, then over cycle in partition of n and then taking proper power of k. Precomputing these values takes O(number_of_cycles_in_partition·m) time and then dp takes O(m²) time.

Are you sure that you have no logs in complexity of J? If you have, then there is a hint: values are up to 2²⁰ so you are able to have $\text{[math]}$ bitsets, each of size 2²⁰. I'm assuming that you already know that we want to split whole array into $\text{[math]}$ arrays. Also note that calculating Dijkstra doesn't need O(2^k·k) calls of data structure, it needs only O(2^k), because you should consider only first time when you try to get into some XOR/subset/vertex.

In F you should iterate over a turn and maintain big array which stores the information "in which sets of cards (with their assignment to players) some player would already say that he knows". When the turn is fixed you also know which player should now say something. So you can iterate over possible sets of cards. In each of them look at every other proper set which differ only by the current player's card. Some of them aren't possible to still be in the game because somebody would already end the game (you have this information in your big array). If in each of possible sets current player has this same rank then he'd end the game right now. It turns out that every game ends in at most 13 turns.

→ Reply

7 years ago, # |

← Rev. 2 →

+33

Using the opportunity: I'm the author of all tasks, so I hope that you found them interesting. :)

→ Reply

7 years ago, # ^ |

← Rev. 2 →

I really liked problem C / G. Thanks for the great problems! However, our team had complaints over D. I thought it was too much to implement for a nondeterministic (risky) solution.

By the way, was it a part of some official Polish contest? (If that's true, I'm interested in the scoreboard)

→ Reply

ksun48

7 years ago, # ^ |

Our solution to D was quite simple, actually. We did the following: first randomly shuffle array b, then split array b into two halves of size c and d. Then consider all permutations of the first min(8,c) elements of array 1 and all permutations of the first min(8,d) elements of array 2 and find the two that result in the lowest matching. Repeat until you run out of time.

→ Reply

mahathirichiro

7 years ago, # ^ |

+10

The problems were really interesting. Could you please share the solution of problem H?

→ Reply

dotorya

7 years ago, # |

What is the intended solution for G? Our team upsolved it after contest using O(N log^2 N) time and O(N log N) space using sort of 2D segtree, with lots of optimizations. I wonder this is a right way to do it.

→ Reply