Problem B: Hamro and Array

We first calculate array d with d[i] = a[1]-a[2]+a[3]-a[4]+...+a[i-1]*(-1)^(i+1) in O(n) (if i is odd, d[i] = d[i-1]+a[i], else d[i] = d[i-1]-a[i]). Then, for each query, if l is odd then ans = d[r]-d[l-1], else ans = -(d[r]-d[l-1]).

Complexity: O(n+q).

My code

Problem D: Hamro and Tools

We can solve this problem by using Disjointed-Set Union (DSU). Beside the array pset[i] = current toolset of i, we'll need another array contain with contain[i] = the toolset that is put in box i. If no toolset is in box i, contain[i] = 0.

For each query that come, if box t is empty, then we'll put the toolset from box s to box t (contain[t] = contain[s] and contain[s] = 0). Otherwise, we'll "unionSet" the toolset in box s with the toolset in box t (unionSet(contain[s], contain[t]) and contain[s] = 0).

Finally, we can find where each tool is by the help of another array box, with box[i] = current box of toolset i. Finding array box is easy with help from array contain. The answer for each tool i is box[findSet(i)].

Complexity: O(n).

My code

Problem E:

Our solution consists of 2 parts: preprocessing and answering the queries in O(1) time.

So, in preprocessing part we are calculating the answers for all possible inputs.

How to do that? Let's iterate through all possible left borders of the segments. Note, that moving the right border of the segment do not decrease the LCM (LCM increases or stays the same). How many times will LCM increase in case our left border is fixed? Not many. Theoretically, every power of prime, that is less than or equal to 60 may increase our LCM, and that's it.

So for each left border let's precalculate the nearest occurrence of each power of each prime number. After that we'll have an information in the following form: if the left border of the segment is i, and the right border is between j and k, inclusive, LCM is equal to value. So, for each segment with length between j - i + 1 and k - i + 1 answer is not bigger than value. We may handle such types of requests using segment tree with range modification. In a node we will keep two numbers — double value of the LCM (actually, it's logarithm: note that log(a * b) = log(a) + log(b), so instead of multiplying we may just add the logarithms of our powers of primes) and the corresponding value modulo 1000000007.

After performing all the queries to segment tree we may run something like DFS on the segment tree and collect the answers for all possible inputs.

The overall complexity is O(n * log(n) * M), where M is a number of prime powers that are less than or equal to 60

Code

By the way, shouldn't we move this discussion to the Hunger Games group?

Problem K

We consider a number to be the sum of some powers of two

X = (2ⁱ + 2^j + 2^k + ...)

+ Similar terms for 2^{2 * i + j} and 2^3 * i

Where g[i][j][k] = the number of subsequences with bits i, j and k set. We can use the Mobius DP similar to that described in this soln http://www.usaco.org/current/data/sol_skyscraper.html to calculate f[i] = # of elements in the input array which are "supersets" of i in O(nlgn). Then, to calculate g[i][j][k], we can calculate how many elements of the array contain bit i but not j,k or bit i,k but not j etc (call these types of requirements classes) through inclusion exclusion with f[] in O(3 * 2³ * 2³). Then by iterating over subsets of the classes to be included in our subsequence and doing some simple math we can determine g[i][j][k] in O(2²³ * 2³ * 2³). The overall complexity is thus O(nlgn + log³n) See code for details.

Edit: Fixed link to code

Problem A: Good Numbers.

Call LCM(i, j) the lowest common multiple of i and j.

First, we should analyse that if x is divisible by LCM(p^i, q^j), then x is divisible by p^i and q^j at the same time.

Call set s(i, j) the set of number x in range [l, r] that x is divisible by LCM(p^i, q^j). Call |s(i, j)| the size of s(i, j). We can find out that:

|s(i, j)| = |s(1, j)| - |s(1, i-1)| = r/LCM(p^i, q^j) - (l-1)/LCM(p^i, q^j)

Call set d(i, j) the set of number x in range [l, r] that x is divisible by LCM(p^i, q^j) and doesn't belong to any set d(ii, jj) (i <= ii, j <= jj, i != ii or j != jj and LCM(p^ii, q^jj) <= r). Call |d(i, j)| the size of d(i, j).

Our answer is sum of |d(i, j)| with i > j and LCM(p^i, q^j) <= r.

We also find out that |d(i, j)| = |s(i, j)| — sum of |d(ii, jj)| (i <= ii, j <= jj, i != ii or j != jj and LCM(p^ii, q^jj) <= r). So we can use recursion with memorize to this.

Our biggest problem is now checking for overflow (since LCM(p^i, q^j) can exceed int64). I found a pretty easy way to do this in Pascal:

function CheckOverflow(m, n: int64): boolean;
const e = 0.000001;
      oo = round(1e18)+1;
var tmp, tmpm, tmpn, tmpu, tmpr: double;
begin
 tmpm:=m; tmpn:=n; tmpu:=GCD(m, n);
 tmp:=tmpm/tmpu*tmpn;
 tmpr:=oo;
 exit(tmp-e < tmpr);
end;

I wonder if there is a way to do this in C++ (without bignum)

Complexity of whole solution: O((log l)^2 * (log r)^2 * (log l + log r))

My code

Here is an explanation for problem O. I don't want to include my code though since it's really ugly :).

Problem O: Cheque

Naive solution: For each query, use Dijkstra to count the number of vertices within distance k. Keep track of already visited nodes so we don't count them twice. Complexity is O(n²log(n)) , which is way too slow.

How to improve this? Every time we visit a node, remember the distance from the starting node. If we come across this node again but with an equal or greater distance, then there is no point in visiting this node again.

Isn't complexity still O(n²log(n))? The distance to a node must be a non-negative integer less than k, and there are only k of these, so we only need to visit each node at most k times. Complexity: O(k * n * log(n)) , which works since k is small.

I think in problem A best way for getting out of owerflows is Python !

Problem R:

You can pick any spanning forest F you want and increase edge weights in such a way that F is the unique MSF. Just increase the weight of all edges that are not members of F by a very large number.

So, if there exists a spanning forest F which is not an MSF, the graph is adorable: just make F the unique MSF. If not, then the graph can't be adorable: after increasing, there must be some MSF, and it was an MSF before increasing as well.

So, the question is whether there is a spanning forest which is not minimal, i.e. which has a higher weight than the weight of a MSF. To find the answer, compute the maximal spanning forest and check if its weight is same as the MSF weight. You can find the minimum and maximum SF using https://en.wikipedia.org/wiki/Kruskal%27s_algorithm

Now we know how to calculate the answer for a single graph, but we need it for many graphs. The important observation is that adding an edge to an adorable graph can't make it non-adorable, for the following reason: if the edge connects two different components, then every SF must contain that edge, and the weight of both the minimum and maximum SF increases by exactly the new edge weight, so the difference between the maximum and minumum stays the same. Otherwise, the edge connects two vertices in the same component, so it's optional to put it in the tree, so the minimum SF weight either decreases or stays the same, while the maximum SF weight either increases or stays the same — this time, the difference between the max and min can either stay the same or grow.

So we know that the answer has the form 000...000111...111, we just need to find the location of the first 1. Use binary search.

Problem S:

XOR is a very special operation. If you XOR the same number twice, it is the same as not XORing it at all. This means the sum of two pretty numbers is another pretty number.

Let us denote the set of pretty numbers and our set of integers .

Given this fact, we can make some useful observations. Firstly, if we add a new integer x to , will not change if x was already in . Moreover, if x is not a pretty number, then the size of will increase by a magnitude of 2. This means that we can only have log₂(10⁹) ≈ 30 numbers we need to keep track of in our set.

This leaves us with two questions. How do we determine whether or not a number is pretty, and how do we determine the kth prettiest number? The answer to both of these is row reduction (or Gaussian Elimination). We will construct a matrix where each row corresponds to the binary representation of a number in , and row reduce this matrix to obtain a new set of integers that will have the exact same set of pretty numbers as before the transformation.

After row reduction, we will be left with a set of integers where each one has a distinct leading bit positions (bits of high value). Moreover, if a leading bit appears in a certain position in one of our numbers, no other numbers will have a 1 in that position.

With our modified set of numbers, we can now solve our two questions.

To determine whether or not a number q is a subset XOR of , we look at the binary representation of q. If there is a 0 in a certain position, then our subset XOR cannot contain the number from which has a leading bit in that position (if it exists). And if there is a 1 in a certain position, then our subset XOR must contain the number from which has a leading bit in that position (if it exists). If at any point we need to include a number that does not exist in , then q is not pretty. Additionally, if after including and excluding numbers, our subset does not equal q, it is not pretty either. If we add q to our set of numbers, then we need to perform row reduction again.

To determine the element, notice that because of the distinct and exlusive nature of the leading bit positions, when determining the rank of a pretty number, we need only consider the position of the leading bits. Moreover, if we sort , the elements we choose will correspond the the binary representation of k - 1.

Complexity is O(log³k + nlogk), where k is the size of the query numbers, up to 10⁹.

Could anybody explain, why complexity in F is O(n * k)? We have n * k states in DP and counting each costs O(k) in the worst case, so it looks like O(n * k^2). Actually, because F[i] >= n — 1, we have

O(n * k * (k / n)) = O(k ^ 2), but this is also to much.

I don't want to sound self serving (although I really am), but isn't the solution I presented to A clearly better than the one added to the main post? Perhaps there is a little bit of bias since kpw29 seems to have had the same solution as the one chosen? :P

Problem T: The ranking

To do it without extra log in complexity, we can calculate dp values for every prefix and for every suffix of competitors. Then we we multiply prefix i - 1 and suffix i + 1 to get dp for all competitors except i-th one.

Let's check if p*q = ret gives overflow. We can check if ret divides q and ret / q = p.

In competition I couldn't prove correctness of that. So I did this : first find Maximum possible coefficient for p that no exceed the MaximumNumber . then check it with q. I think this is easy , safe and self-proof.

int r = MAXINT / p;
if ( q > r ) { /* Overflow */ }

this is my Accepted solution : http://ideone.com/YVbmOt

Problem S: Godzilla and Pretty XOR

Totally a linear algebra problem :) To solve this problem we should keep the minimal set of numbers (let's call it basis) such that every pretty number can be obtain as xor of sum elements from basis. Also as we want to get the k-th number we should keep basis in some simple form. Let's say there are n elements in basis. Then we want every element to has its mots significant bit not to appear in any other element. It is simply to do with Gauss method. After that let's query k-th number we can obtain. Easy to see that if k = 2^a₁ + 2^a₂ + ... + 2^a_t then the answer is xor of a₁, a₂, ..., a_t elements of basis. Total complexity is .

My code (it is much more simple then explanation): #0KF9Ra

Can anybody explain why these two submissions don't work?

http://pastebin.com/KQNyW5NZ
^This goes into an infinity loop while binary searching.

http://pastebin.com/GYHtBc48
^This gets a wrong answer on a systest, but I can't find which edge case its failing on.

Thanks

C:

We'll be counting all indices modulo N. By subtracting two successive sums, you get A_i + 3 - A_i = D_i = B_i + 2 - B_i + 1. Now, there are two cases for N divisible and not divisible by 3; let's describe the latter case first.

If we fix A₀, we can successively find A_3k for all k, which (in this case) means we'll find the values of all elements of A[] before reaching a cycle when trying to "find" the value of A₀ for k = N. If this "new value" a of A₀ doesn't coincide with the one we initially chose, then there's no solution, since adding any number to A₀ means adding that same number to all elements of array A[] and also to a, which always leads to a contradiction. For the same reason, if there's no contradiction once, then any solution obtained this way satisfies all equalities for B_i — except one (which vanished due to subtracting for D_i), w.l.o.g. B₁. In order to satisfy it, we can see that we need to add (B₁ - A₀ - A₁ - A₂) / 3 to all elements of A[]. If that's not an integer, there's no solution for the problem in integers; otherwise, we found one!

when it's divisible, just split the given array into three based on remainders of indices mod 3 and apply an approach similar to that for N non-divisible by 3 on each of them to find a solution that satisfies the equalities for D_i. We need to satisfy w.l.o.g. B₁ again — we can arbitrarily choose A₀, A₁ and assign a suitable value to A₂ to satisfy it, because this time, changing A₀ or A₁ doesn't affect A₂.

The problem statement contained strange requirements (|A_i| ≤ 10⁹ and B_i ≤ 10¹⁸); in reality, any solution is acceptable (there are multiple solutions for N divisible by 3, a single solution for non-divisible) and B_i are much smaller, so there's no need to worry about overflows. Time complexity: O(N).

I:

All non-deleted roads should form a minimum spanning tree, so the answer is the sum of all roads' weights minus sum of MST's roads' weights. The answer is -1 iff the initial graph isn't connected. Time complexity: O(N²).

J:

This is an excercise in centroid decomposition. The right vertex to ask is a (there can be two, in which case either one works) centroid of the given graph. If that's the special vertex, we're done; otherwise, we can remove it, which splits our tree into several disconnected trees and we're told which tree we should look for the special vertex in — which we can handle recursively. One of the most basic properties of the centroid is that each of those trees has at most N / 2 vertices, so there are at most centroid searches and questions necessary.

Since a centroid can be found using DFS in O(N) time, the actual time spent on this is O(N + N / 2 + N / 4 + ...) = O(N).

L:

First, let's consider all edges with weights containing 1 as their 29-th bit. If all paths from S to T require taking one of them, then the answer is at least 2²⁹. Otherwise, it's less than 2²⁹. In the latter case, we should discard all those edges and repeat with the 28-th bit. In the former, we can add 2²⁹ to the answer, set the 29-th bit of every edge's weight to 0 (as in: we should ignore that bit forever, since we already know it's 1 in the answer and OR works bitwise) and again repeat with the 28-th bit, without discarding any edges.

How to find out if all paths from S to T require taking one of the specified edges? Lol BFS. On the given graph without the specified edges.

So, we need to run BFS 30 times (actually times). The total time complexity is therefore ; the answer is -1 iff there's no path from S to T in the initial graph.

N:

http://codeforces.com/blog/entry/17612

O:

This is a pretty standard problem. All you need to do is maintain the min. distance of any city from any one containing a killer, or distance K in case that minimum is  ≥ K. When adding a killer, we can run a BFS starting from this vertex. When we check an edge during the BFS and see that the min. distance of a killer that goes to v through u is strictly better than the one we had before, then we can update the minimum and add v to the BFS queue. Meanwhile, we can keep count of the number of vertices with distance from a killer  < K.

This way, each vertex is added to the BFS queue O(K) times and each edge is checked O(K) times, so the total time taken is O((N + M)K + T).

P:

This is the first problem for centroid decomposition (therefore, it should be solvable with HLD, but the first idea I had was centroid decomposition). The idea and implementation are extremely similar to problem P.

After finding a centroid c, we can split the tree into its sons' subtrees and assign each query to the subtree in which its vertex v_q is and add its value p_q to the centroid if appropriate (apart from queries for which v = c, for which we just add p_q to the centroid; adding it to the remaining vertices is handled in the following automatically). Then, we can recurse to the subtrees and only need to add p_q from each query to all vertices that lie in a different son's subtree than that query's v_q and have depth  ≤ d_q - dep(v_q) = d'_q. Of course, we should calculate depths dep() of all vertices in a tree rooted in c.

A good way to do this is with one BIT; depths only go from 0 to N, so there's no need for compression. We should put all queries into the BIT, then for each son's subtree, remove the queries in that subtree, check all vertices in it, add to each of them the sum of p_q of queries in the BIT whose d'_q is  ≥  to the depth of that vertex — from this, we can see that we should be adding/subtracting p_q at the index N - d'_q for each query — and add the removed queries back to the BIT before continuing on to the next son's subtree.

This way, we only consider each query and each vertex in trees in the decomposition, and each time, we only need a constant number of BIT queries; also, the total size of constructed BITs is no more than the number of vertices, since it has size O(N) for a tree with N vertices — alternatively, we can work with a single BIT and remove all queries after processing the last son's subtree — so the time complexity is .

U:

The bruteforce solution to this problem would be: for each player v, check each player w who beat him, then check if v beat someone who beat w. If you can't find anyone for some w, then don't add 1 to the answer for v.

This runs in O(N³), but it can be optimised by a factor of around 30 using the fact that bitwise operations with integers are very fast. The right thing to do is coding all people beaten by u and all people who beat u for each u as 1-s in binary representations of integers — make an array B[][], where the -th bit of B[u][x / 30] is 1 iff u beat x and another similar array Bi[][] for "x beat u". Then, checking if there's someone beaten by v who beat w becomes just checking if the bitwise OR of B[v][i] and Bi[w][i] is non-zero for some i, which takes around fast operations. With a time complexity of O(34N²), it's easy to get AC.

T:

So, we have the (reasonably obvious) DP that finds the probability P_x, R[S][K] that, if we know that competitor x is in one of the minimum interesting intervals (I) and when we consider a subrange R of all people except x, then S will be before I and K inside I. We can compute P_x, R'[][], where R' is R extended by one person, in O(N²) time as P_x, R'[i][j] = aP_x, R[i][j] + bP_x, R[i][j - 1] + cP_x, R[i - 1][j], where a, b, c are some constants that only depend on the person that's added and I. This way, an O(N⁴) way to enumerate P for all x and corresponding maximum R simply by adding N - 1 people consecutively for each x, but that's too slow. We need something better.

One might have an idea to use something like a segment tree, where we can merge ranges easily. In this case, it doesn't work — merging ranges with lengths L and 1 is easy by adding 3 terms per person, but merging ranges for L and M people takes adding 3^M terms directly and at least even when not counting duplicates. That won't work.

What we can do, however, is reverse the process of adding a person to R — from P_x, R'[][], we can get P_x, R[][] in O(N²). There are generally 3 ways to do this, but some of them can give NaN-s if some of a, b, c are zero — but since a + b + c = 1, all three won't fail at once. The formulas are quite lengthy to write here, you can find them in my code.

In addition, why are we even using ranges?! For what we want to describe, making some magic order for competitors is obsolete, so they should be sets! In other words, merging ranges is commutative.

Now, notice that P_x, R[][] is just P_{x, R + x}[][] — person x doesn't have a particularly special place. If we denote the full set of all N people by R_m, then we really just want to always remove x from P_·, Rm[][] (if the second index is R_m, the array is the same for any x) to get P_{x, Rm - x}[][]; that's N times an O(N²) process. After processing, we can add the appropriate numbers to the output array by adding P_{x, Rm - x}[i][j] / (j + 1) to the probabilities that x will be at each place from i-th to i + j-th inclusive; that also works in O(N³) by brute force, but can be easily optimised to O(N²). And here we have an O(N⁴) algorithm by repeating this for each of the minimum intervals.

If only the precision wasn't so awful.

There are no trouble with calculating P_x, R'[][] from P_x, R[][] thanks to only multiplying and adding small numbers, but when doing the reverse, we use division by one of a, b, c, and they can get small (or 0) sometimes, which quickly nukes the code. The problem is that small precision errors may appear when dividing, but since we use previously computed values of P_x, R[][] when computing new ones, those precision errors pile up, causing further precision errors and the values we compute progress exponentially to bullshit (probabilities of minus billion, for example).

The first trick to employ here is... well, not dividing by small numbers if that's so bad. Just pick the maximum of a, b, c or something and use the method that divides only by that; you can always pick a number  ≥ 1 / 3 to divide with, which is pretty big. While it eliminates the errors very well, it doesn't have to eliminate them fully. So we should look for something more.

The second trick is even stupider, just check if there are people with strange-looking probabilities and do the bruteforce (O(N⁴) per person) on them. This does lead to AC, but you can't pick too many people to bruteforce, so you should pick the right people and if necessary, make your bruteforce constant-efficient (you don't need to compute N² elements when merging two sets of size N and 1, just roughly N² / 2). What I used was adding up all probabilities for everyone and bruteforcing the people for which that sum differs from 1 too much, but there are simpler things to try, like checking if you've computed some strange-looking probability.

Of course, this way doesn't guarantee running time better than O(N⁵), but it's a really fast O(N⁵) :D.

V:

We'll go down by bits. If the 59-th bit of l and r is the same, then the 59-th bits of all numbers in the range [l, r] will be the same and we don't need to do anything. If those bits are different, we can split the range [l, r] into two non-empty subranges such that one of them has numbers with 59-th bit equal to 0 and the other has it equal to 1, so we can find a number (any number from one range xor-ed with x) that has the 59-th bit equal to either 0 or 1. Based on whether we want the min. or max. ugly number, we pick the right subrange, discard the other one and continue on with the 58-th bit.

The important thing is that we'll always get a range of consecutive numbers for each value of the current bit thanks to starting with the largest bit, so we can continue in the same way for the 58-th bit etc., always cutting down the current range to a single number. We can find the final answer by xoring it with x again. Time complexity: .

Speaking of xor, what's the point of using an operator and then defining it to mean xor? Wouldn't you save space by writing l ≤ (x xor a) ≤ r to being with?

X:

This is the second problem for centroid decomposition (therefore, it should be solvable with HLD, but the first idea I had was centroid decomposition). The idea and implementation are extremely similar to problem P.

The recursive part is done in the same way as in problem P, but since we want to sum up vertices at a distance of at most something from each query vertex and not query vertices at a "distance" of at least something from each tree vertex, we should reverse what we put into the tree (+-1 for each vertex at the index given by its depth) and what we ask for.

Also, we need to compress the distances, since they can get large. One prior use of STL map<> is sufficient. Time complexity is again.

Can someone explain P in detail, not getting what is being done after constructing centroid tree.