Is it the first round set by so many high schoolers? Excited for this round :) tons to learn

Chinese legends' round, but Chinese night owls' round as well.

I smell geometry and a lot of meth!

I think he will appear in problems just like Alice and Bob. :-)

Not all of them: 1088D - Ехаб и еще одна очередная задача на xor

Not all of them (2): 1075D — Intersecting Subtrees

Total point value is 35931, so:

6 7 12 26 28 39 40 54 84 97 

And winners:

And of course congratulations to top30:

Sorry about that, but an opencup will end half an hour before the contest, so we can do nothing :(

Read careful the round announcement, the second sentence specifies that it is rated for both divisions.

%%%

You can go to Australia to make the T-shirt useful.

Think in terms of mst. Consider all the edges which directly or indirectly connects any 2 special nodes. Among all such edges find the one with maximum wight. This passed system test for me.

Find the MST, and then choose the relevant subtree that contains all the special nodes. The answer is going to be the maximum edge weight in this subtree repeated k times.

The MST has the property that it minimizes the maximum edge between in a path between nodes a to b.

I did using a binary search to find the maximun edge that is necessary to contains all special nodes. The answer will be this maximun edge for all nodes.

--

I tried something similar.

I made the pallindromic tree for both strings, now, to find the number of such y's, I calculated, for each reversed suffix links in A, the number of suffix links in B, so I made hashes of all these suffix links and inserted them in a multiset. But I had a bug in the code. Also, I cannot prove the suffix link idea is correct, so most probably it's wrong since it has 0 solves :p.

Basically you'd pass them if you compute the maximum distance between any 2 points, not necessarily special

Really? Why would you even do that? I saw people getting hacks on D but nothing happened in my room...

If there is a person to blame, i think it should be you. You should blame yourself for not reading statement carefully. Many people solved it, so you shouldn't blame the pretest.

Not only pretests were weak, but system tests too, which makes it more fair.

Here is O(m*k) accepted solution, which I did not manage to hack within contest.

for each number you have the sqrt of the sum of numbers before it bf, and number next to it nxt. now you need to find an x such that ll(sqrt(a * a + nxt)) == sqrt(a * a + nxt) and a = bf + x . I don't think binary search would work, so I iterated while ((a + 1) * (a + 1) - a * a <= nxt) which means that the difference between the next perfect square is already bigger than nxt and we have no answer if that happened, and nxt <= 1e5 so that will fit in the time limit. Tho I don't have any proof whether the first number that fits will be the only one that does.

I did it with a greedy algorithm. For every odd i find such an a[i], so sum (a[1..i-1]) + a[i] + a[i+1] is a correct square, using the fact, that we can make any correct square from sum (a[1..i]), that is less than sum (a[1..i-1]). So every time i seek for the minimal square. We can stop seeking, when a[i+1] is less than 2 * sqrt (sum (a[1..i])) + 1.

I did it with a greedy algorithm. For every odd i find such an a[i], so sum (a[1..i-1]) + a[i] + a[i+1] is a correct square, using the fact, that we can make any correct square from sum (a[1..i]), that is less than sum (a[1..i-1]). So every time I seek for the minimal one. We can stop seeking, when a[i+1] is less than 2 * sqrt (sum (a[1..i])) + 1.

In general, we can't. For example, see array with size 2. 01 and 10 are indistinguishable.

It is

Basically, anything

please?

For each people we can say the number of hats of his kind — it's n - a[i]. Then we can count the number of people, the number of hat's of whose if n - a[i]. X people for Z hats. If for each number from 1 to n X % Z == 0 — we can answer. Otherwise, it's impossible. We can choose the types from 1 to n in this order:

int ttype = 0;
for (int i = 0; i < n; i++)
{
	cin >> a[i];
	if (numb[n - a[i]] % (n - a[i]) == 0) 
	{
		ttype++;
		type[i] = ttype;
		numbtype[n - a[i]] = ttype;
	}
	else type[i] = numbtype[n - a[i]];
	numb[n - a[i]]++;
}

I think l is similar to 1, but l is not similar to 1.

+1, I spent like 40 minutes trying to figure out when to invert the value of s[i]...

PS: I still think the problem was awesome

I had ifs:

if (k==0)return cout<<m,0;

if (k>m)return cout<<0,0;

I removed them and got ac, formula is: d[i][j]=d[i-1][j-1]*(m-1)+d[i-1][j];

Before processing this formula i put every d[i][0] to m (1<=i<=n)

Here a[i] is the number of persons who wear different hat from him.
Hence, n-a[i] is the number of persons who wear similar hat to him.

Now, group the indices whose n-a[i] is equal. Insert i in the group[n-a[i]].
If for any group[i], size of the group is not divisible by i, then print Impossible
Otherwise, maintain a id starting from 1. For each group[i], iterate through all the indices in
it and for every i indices, set their value of b[] to the counter value and increment the counter by 1. Then print Possible and the array b[].
Update: Here is my code: https://pastebin.com/QWf0gbsB

Sorry for my poor English. Feel free to comment, if you don't understand the solution.

Probably to do the system testing fast.

DP[0][0] = 1;

DP[i][j] = m*DP[0][j] + Sigma(x from 0 -> i-1) (m-1) *DP[x][j-1] (if j > 0)

As a general rule, no one solved H. But I still think the problems are perfect.

I was hacked by khokho with this same idea. Luckily for me, he gave me the opportunity to correct my code.

EDIT: my corrected code didn't pass system tests. Damn it, I spent twice the time for less than worse results.

EDIT: Why the downvotes?

i think it's will be something like 2 1 1 or 4 2 2 2 2 or 7 5 5 5 5 5 5 6

You should try to be bad-at-luck like me, constantly jumping into rooms that nobody makes mistakes even other rooms are full of such people :D
Also, nicely done hacking one D :D

What is FST?

aactually I have seen the code of problem A which tourist hacked . that fellow's code gives output 2 for input 6. here's the code https://codeforces.net/contest/1081/submission/47132351 and hacking that code is too easy for someone like Tourist!

The problems should be able to submit by now. However, they're not at the top of the problemset, so be careful to find them.

coz they havent put the problems for practice!!

If color[i] is the color of the i-th brick, then it's talking about the number of bricks such that

color[i] != color[i-1].

I agree that it could have been worded better.

But thats O(n) solution.

Taken such test for example:

3 2 2
1 2
1 2 3
2 3 4

The answer should be 3, but since many solutions output the maximum weight of the MST of the entire graph (not just the subgraph including all special vertices), they outputted 4 and failed system tests.