Hey!

Polish Collegiate Team Programming Contest (AMPPZ 2016) took place today, organized by University of Wroclaw. This is my first ACM experience, and I want to share with you my impressions.

To begin with, I'm still a high schooler (2nd grade). However, thanks to generosity of UWroclaw organizers team and some charity institutions, a few best high school teams were able to participate.

Now let's talk about the contest. My teammates were Paweł Burzyński(pawelek1) and Kacper Kluk (wonrzrzeczny). None of us is a really fast coder, so we just decided to focus more on accuracy than speed. As we'll see later, this was kind of a good idea.

The contest started with no delays. I was not expected to be the coding monkey, but somehow it happened that three first and easiest tasks were accepted by me. These were not really challenging, so let's just ignore this fact. Some time later, Kacper scored the "ifologic" problem C. Then, the difficulty has risen.

Meanwhile, teams of UWarsaw1 and 2 were skyrocketing, grabbing quite outstanding scores of 7 problems per 90 minutes and 9 problems after the first half of the contest. After 2,5 hours there were 2 problems with no solves. The problemset was rather on the technical side and at this stage it was only a matter of time who will manage to implement more tasks correctly. As for our team, Paweł scored an interesting F and Kacper was implementing G. B was still unsolved, but we were giving it a try, because it looked like a problem which requires just careful cases handling for which probably most top teams had no time.

There were still two number theory problems left, two graphs, two implementations G and (super awful) B and a something-with-convex-hull-problem E. At that point we had an accuracy of 0 incorrect tries, which gave us a good position even though our solving times was average. Paweł got into E and Kacper finished G, and at 3:15 we had 7 (+20 penalty).

After this, we got quite stuck on harder problems. Because we couldn't solve anything harder, I was chosen to code some clever backtracking for B. A similar problem was already on AMPPZ 2014, named pillars (http://main.edu.pl/en/archive/amppz/2014/fil). While I was adding new and new ideas to the solution, other guys were thinking on EIHL. 30 minutes left, and Paweł sat to code his I solution. Unsurprisingly, it had some bugs. There was little time left, so we had to speed up. We were working together, but I barely knew what the solution should do. We debugged the samples and... WA. 10 minutes before the end, we still had WA and Paweł had basically no ideas what could be wrong. I still don't know how I came up blindly with the right idea, but three mintues later we were happy with the AC. 8 problems with 2 incorrect tries during the whole competition -> that was rather well. At that point we knew we were going to be top10, and we were really satisfied.

After the contest, we had some time to discuss the problems with friends and meet some famous people. We've even managed to have a picture taken with Petr! :)

Then, the solutions presentation and final ceremony took place. The organizers prepared amazing piece of work which simulated the ranking in a really cool way. The final results :

1. UWarsaw1 (mnbvmar, Marcin_smu, Swistakk) 11.

2. UWarsaw2 (Radewoosh, Errichto, mareksom) 10.

3. *Google (Petr, Franken, Kwasnicki) 10.

4. UWroclaw2 (Lowicki, Syposz, Michalak) 9.

5. UWarsaw3 (znirzej, tabasz, tribute_to_Ukraine_2022) 8.

6. *III High School Gdynia (kpw29, pawelek1, wonrzrzeczny) 8.

• means unofficial participation. I'll post the official data (statements, results) as soon as they're published. Right now, you can enjoy live ranking from the first 4 hours of contest at : http://solve.edu.pl/~amppz/chartcode2016/ranking.html.

Our results were really satisfactory. And what about you? How was your first ever ACM contest? I'm not talking about such programming legends as [Bredor] and his http://codeforces.me/blog/entry/45106 ACM story, just average people. I'm writing this mostly for myself to remember this event, but I will appreciate any answers :)

One more thing. I want to thank the organizers for an interesting problemset and a reaaaally cool event. Thank you, and thank all people who contributed to it. Looking forward to seeing you in @amppz2017!

Have you ever seen a problem connected to graphs diameter, where it is used in complexity?

For example: http://main.edu.pl/en/archive/oi/21/tur .

Model solution goes O( (1 + sqrt(2)) ^ T) * (n + m) ), where n is number of vertices, m — edges and T is the longest path which we can encounter in it. However, longest path is not a diameter. I've just wanted to show what I am talking about.

Any help with finding such a problem would be highly appreciated. Thanks in advance!

Today (April 1st) our school announced : "Glider meeting on 7th lesson". Everyone found it as an april fools' joke, but...

LOL ^^

And what is the best April Fools' joke you've ever taken part in?

This is the second part of Hunger Games Editorial, hope you'll enjoy it :) And again, thanks for stuff for awesome contest, congratz for survivors too!

UPD: Problems B, D, E, Q, T, W are now available, more soon :)

Editorial Hall of Fame:

Radewoosh .I. Chameleon2460 sepiosky adamant xuanquang1999 rnsiehemt Fcdkbear JoeyWheeler

Problem A: Good Numbers.

Tutorial by: xuanquang1999

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)

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

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

Code; http://ideone.com/R1AgnQ

Problem B: Hamro and array

Tutorial by : xuanquang1999

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).

His code: http://ideone.com/kMalCH

Problem C:

Problem D: Hamro and Tools

Tutorial by : xuanquang1999

We can solve this problem by using Disjoint — 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).

Code: http://ideone.com/Te3wS9

Problem E: LCM Query

Tutorial by: Fcdkbear

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: http://pastebin.com/7zcYTced

Problem F: Forfeit

Tutorial by: sepiosky

First we make an array F[] for each edge , for an edge like e if after deleting it we have two components C₁ and C₂ , then f[e] = |C₁| * |C₂| , It's easy to undrestand that if we increase weight of edge e by 1 the total sum of distances will increase by F[e].

Now we consider Sum as minimum total sum of distances , from where Min(Sum) = (N - 1)² We can be sure that for answer is 0 .

Now we can solve the problem with DP Where DP[E][S]=number of ways we can weight tree with sum S using first E edges.Note that first we subtract Sum from K and we use dp for collecting K - Sum

DP[E][S] = DP[E - 1][S - (L[E] * F[E])] + DP[E - 1][S - ((L[E] + 1) * F[E])] + ... + DP[E - 1][S - (R[E] * F[E]]

This DP is O(K * N²) but we can reduce it to O(K * N) (where N < 400 )

Source code: http://ideone.com/WOZfbg

Problem G: Hamro and Izocup

Tutorial by: sepiosky

let S₁ be the area of SECTOR BOC and S₂ be area of TRIANGLE BOC Answer = S₁ - S₂

We can calculate OH using pythagorean theorem and length's of OB & HB( = α / 2) . so we can calculate area of triangle BOC .

for calculating the area of sector BOC first we should find . We name as

in triangle BOH according to Law of sines : = sin(O / 2) = = 2 *

So area of sector BOC = * π R²

Now we have S₁ & S₂ So we have answer !

Source code: http://ideone.com/Zkvh6p

Problem H: Hamro and circles

This problem is basically the same as G. First, imagine that second circle is a square and solve G. Then, swap the circles, solve G again and add results.

Source code: http://pastebin.com/ZvJJcAKP

Problem I:

Problem J:

Problem K: Pepsi Cola <3

There are at least 2 different solutions for this problem, I'll try to explain them.

Chameleon2460's solution:

Let's define A as log of the biggest value in sequence T. By the problem constraints, A ≤ 17. I'll describe an O(3^A) solution, which will pass if implemented without additional log factor.

We'll try to find for all possible values of OR how many subsequences have that OR. (Taking the result is pretty easy then).

Define X contains Y iff (XORY = X). Notice, that OR X might be created only from values, which X contain.

We'll write subset DP in a quite standard way. For all values of X, we'll first assign dp[X] = 2^L, where L is number of values, which X contain. (L can be computed the same time we write DP, just for all subsets of active bits in X, we'll add L[x] += L[subset]). Then, we will just subtract all values, because not all the subsets have OR equal to X. But we'll have this computed before entering X, so we can remove them without any additional effort.

Source code: http://pastebin.com/R6B2a41u

My old code, which is O(3^A * A), and gets TLE, but it's quite easier to understand: http://pastebin.com/7GNLJQ7E

JoeyWheeler's solution:

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 solution: 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  *  23  *  23). 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(223 * 23 * 23). The overall complexity is thus O($n lg n + log^3 n) See code for details.

Source code: http://pastebin.com/Hphc3k2y

Problem L:

Problem M: Guni!

Tutorial by: sepiosky

We can solve this problem using 2 segment trees. In first tree we keep array a and after processing each query of type 1 on it we add score of g_i to second tree and for queries of type 2 we process this query on second tree and add result to it.

In first tree we keep negative of array a and for queries of type 1 we apply RMQ on it for finding minimum element in the g_i's interval , its obvious that absolute value of minimum element in that interval is maximum element in g_i , cuz we kepp negative of a_i's . also only information needed from g_i's are their maximum element( their score ) , so after getting answer of queries of type 1 from first tree we only add max element of g_i( that is negative also ) to the second tree .

for queries of type 2 we use RMQ again this time on second tree and now we have answer for query . answer of this query is needed information for this Guni!(g_i) so we add this number to second tree again .

In the end the answer is sum of all elements in second tree (scores of Gunis).

Code: http://ideone.com/n00BPJ

Problem N:

Problem O:

Problem P:

Problem Q: Mina :X

We can preprocess answers for each set size with the following DP: dp[0] = dp[1] = 0

dp[i] = min(max(dp[j] + 1, dp[i — j] + 2) for each 1 ≤ j < i.

Also, we should find what j gives optimal answer, we'll need it later.

Therefore, when we'll get a set S of size i, we'll already know what is correct answer for it.

When we know which j gives optimal answer, we can just query first j elements from our set and query them.

If the answer is "Yes", we should take those elements (and extract every other from S). Else, we should extract those j elements.

Solution: http://pastebin.com/cQ9vFkPc

According to sepiosky this may be done with Fibonacci search. His code: http://ideone.com/3dTmfO

Problem R:

Problem S:

Problem T: The ranking

rnsiehemt's explanation:

Consider the simplified case where we know that, for some interval, every competitor is either before the interval (say there are S of these competitors), after the interval, or somewhere inside the interval with uniform probability over the whole interval (say there are K of these). Then if this arrangement happens, each of the K competitors then has a chance to come each of S  +  1th, S  +  2th, ..., S  +  Kth.

Note also that if we consider all endpoints together and then take the intervals between consecutive endpoints: then for each interval, every competitor will either not cover that interval at all, or will completely cover that interval (and thus if they are in it, they will have a uniform probability of being anywhere in that interval). Also, there are O(N) of these intervals.

This gives us the simple algorithm: for each interval (O(N)), for each competitor i, (O(N)), calculate dp[S][K] = the probability of S other competitors appearing before this interval and K other competitors appearing inside this interval (which we can do in O(N³) with DP). However, this is overall O(N⁵) which is too slow. So we need to try and calculate "dp[S][K] for all competitors except i", for every i. One idea is to calculate dp[S][K] for all competitors, and then "subtract" each competitor with some maths. Overall this would be O(N⁴). Theoretically this is possible but in practice it is too inaccurate.

Instead we can calculate this with divide and conquer (overall O({N⁴}lgN), or buckets . For example, for divide and conquer we can calculate f(l,  r) = the dp[S][K] for all competitors outside of the range [l,  r), and then recurse on f(l,  mid) and f(mid,  r).

Problem U:

Problem V:

Problem W: Palindrome query

Consider strings S and S', to make implementation easier. We'll use hashing to comparing their substrings. We'll store their values in a Fenwick or Segment Tree. Suppose we change position x. (Do not forget to remove previous value!) Then, instead of p1[x] * pot[x] we'll have p2[x] * pot[x] at this place. We add this value to our data structure, and we're done.

For each query we'll use binary search to answer it, as when there's palindrome of length K, we're sure there are palindromes of length K-2, K-4, ....

Source code: http://pastebin.com/gn4wNe6a

Source code by adamant : http://ideone.com/8kLke7

Problem X:

I'll try to write all solutions as soon as possible :)

Here's the first part of Hunger Games Editorial prepared by community. There are only my hints, see also the second blog, which will be soon published, with different, more detailed solutions written by many people :) I'd like to thank problemsetters team (PrinceOfPersia, keyvankhademi and aliasadiiii) for such wonderful contest. Hints will be probably updated when I'll learn more beautiful solutions for these problems :) Enjoy!

Problem A: Good Numbers

Suppose first integer is multiplied A times and second — B times. How many ways are there to complete the big number? Did we count something more than once?

Problem B: Hamro and array

Try to count numbers on even and odd positions separately.

Problem C: Hamro and Vampire Diaries

Suppose A[1] = x. How do we calculate A[1 + 3]? How to calculate next and all other values of A? What happens if n mod 3 = 0?

Problem D: Hamro and tools

Read about how STL can merge lists in O(1) or consider all queries in reverse order.

Problem E: LCM query

Suppose right end of our interval is i. How many different LCM's can we reach in the left? Many? Not many?

Problem F: Forfeit

What is the minimum weight of our tree such that it satisfies constraints? How does the sum change when we increase one edge by 1?

Problem G: Hamro and Icozup

//lel maths

Problem H: Hamro and Circles

//lel maths again, how to explain maths? :D Does this problem differ much from G? What should we change to get AC in H?

Problem I: Hamro and Khikhland's map

We will get the most cash if we take all adges except MST. Google MST if you don't know what it is :)

Problem J: Special Vertex

Suppose we've queried vertex X. Then, we get answer which subtree contains the special vertex, we can forget about all other subtrees of X and do this recurvisely on this subtree. How to choose X such that our solution becomes fast?

Problem K: Pepsi Cola <3

Let's count for each OR how many subsets have this OR. Try to think which OR-es affect which others. How to calculate it fast?

Problem L: It's not that bad (seriously, why does this task has such title?)

Go through all powers of 2 from largest to smallest (2^30 -> 1). For every visited power we'll try to build new graph. For every edge: if its value does not containthis power (value OR power != value) add it to the graph. Then, check if end is reachable from start. What if so? What if not?

Problem M: Guni!

Associate each Guni with maximum value in it? Do we have to maintain any other values in it?

Problem N: Demiurges play again

Try thinking in DP categories. Count dpmin[x] and dpmax[x] for each vertex. Suppose we've counted them for all subtrees of x, how to count them for x?

Problem O: Cheque

Do it "with induction" by K. Suppose we know minimum values for all vertices that are in the distance <= V from marked points. How to count them for V+1?

Problem P: Godzilla and Candies

Choose vertex x. Consider all queries in the graph. For each query only count those vertices which DO NOT belong to the same subtree of x. Then, extract x from graph and do it recursively on all sons of x subtrees. How to choose vertex x such that our solution becomes fast? (See also problem J).

Problem Q: Mina :X

Try to come up with DP which counts minimal number of questions for subset of size X. When we will enter X, we'll have already counted all possibilities, so consider all of them once more and see which of them we may check.

Problem R: Makegraph

Suppose we have answer 1 at some point. Do we already know all the future answers?

Problem S: Godzilla and Pretty XOR

Try to build S optimally. What will be maximal size of S? How to check whether we should insert new value or not?

Problem T: The ranking!

I still do not know how to solve it :( But look at sth cool instead ^^ https://piwoicydr.files.wordpress.com/2015/03/dsc_1126am.jpg

Problem U: Godzilla and chess

Will n^3/32 solution be efficient enough? How to write it easily?

Problem V: Godzilla and ugly XOR

Consider max and min values separately, let's build MIN. Start from the most significant bit. Do we have to add it now or we may later?

Problem W: Palindrome Query

We may use hashing for checking if two substrings are equal. For all updates it's easy to modify our hash. How to answer queries if there were no updates? Does something really change when they are?

Problem X: Tree Query

Use divide and conquer on tree, think in the same way as P. Choose vertex x, perform some queries, extract x from graph, do it recursively. How to choose x? (compare with P and J).