Is there any AI Cup this year?

Memes and more memes . . .

NOIP2018(National Olympiad in Informatics in Provinces) is being held in China now.So we will miss a great contest.What a pity!

Cleshes with Asia champions league-final

Very few users registered for this round :\

why would my second hacking attempt gets counted if its the same input to the same person ?

I just pressed backward in the browser and accedintally it got sent again :(

How to solve C,D,E?

Cool problems btw

any idea what pretest 5 of C might be?

If I had 10 more seconds I think I would have solved D! ouch

Also, how do you solve C?

In D pretest 8 is something like

2
abab
ba
aaab
ba

Unfortunately, I've came up with this too late.

I swear to god, that motherfucking test 8 in Prob D...

Any idea what that test might be? :/

Will the following solution for F work?

Let A be an array of size n. A_i = xor of path from root to i^th node. Now answer is just the k^th smallest pairwise xor in A.

To do this do a binary search for value of xor. Say x is your current value. Find number of pairwise xors less than equal to x (this should be easy to do with trie). And so on...

Test 13 in problem D???

How to solve C?

How to solve problem c? Is there any kind of geometry involved?

Test 7 in C?

I have passed pretests on C with this :)

long long ans = 0;
for (int step = 0; step < 1e8; step++)
{
	ans = max(ans, segments_intersection_size(l[0], r[0], l[1], r[1]));

	if (l[0] < l[1])
	{
		l[0] += t[0];
		r[0] += t[0];
	}
	else if (l[1] < l[0])
	{
		l[1] += t[1];
		r[1] += t[1];
	}
	else
		break;
}

What are the edge cases for problem D. I was getting WA on pretest 8.

hey, this is cruel to set such tight constraints in F! Why couldn't you at least allow memory pass? :(

Who can explain why low number of votes?

how to solve problem B

Used a char array to store the lcp calculated by Z-algorithm on D.
How come I can't find this bug using more than 1 hour during the contest, but spot this instantly after contest......

was my comment invisible or what :P

I don't understand the logic of counting the same hacking attempt when someone send it accedintally .. why it's not like when someone send the same WA solution twice they don't count the second one

Thanks for the contest! I liked the problem ideas but thought limits on problems D and F were unnecessarily strict.

D is a very nice conceptual problem, but limits require linear-time string matching (and fast-enough input to read 18 million chars in 1 second). IMO, linear-time matching does not add any depth -- a limit of N ≤ 300, w_i ≤ 300 would have all the same conceptual value without requiring book code.

F is similar. Requiring linear-time bucket sort or trie traversal makes the problem much harder but not much more interesting. N <  = 10⁵ would allow map / sort / unordered_map solutions to pass without changing the core of the problem. Also, the complexities are hard to distinguish: I've heard of some log-time solutions that snuck under TL as well as some constant-time solutions that went over.

What's the solution for problem C ?

debugforces

Earning a macbook air with 30 seconds. Glorious !

Apparently pretests in C were very weak. My code even fails to something really simple like

1 2 4
0 0 6

because I shifted by t_a instead of the gcd after taking mod gcd :/

Why isn't the contest open for practice? EDIT: it is now.

How to solve F? Kind of seems impossible to a noob like me

I dont give a sh*t if people down vote this but ive seen 2 round of this contest and both of them sucked.

Interesting, for E problem S³ * log(N) is passing easily — 45540761 :)

Here is a more intuitive and simple explanation for solution to Problem C which i found after struggling for a day,

Pre-requisite : Understand what we have to do

First of all, if one can make an Alice's interval and a Bob's interval coincide (in the sense that both begin in the same number) then the answer is just min(r_b - l_b + 1, r_a - l_a + 1) (the length of the shortest interval).

However, this may not be possible. Sometimes it isn't possible for them to perfectly overlap ever(think about it, if you don't get it, continue reading anyway).

We intend to choose lucky intervals(one of alice, one of bob) so as to minimise the difference of the start points of the intervals of alice and bob. Now convince yourself that this will give maximum intersection.

Now the easier part, the solution :)

Consider the start points of two general intervals (one of alice, one of bob).

For alice, start point of general lucky interval is : l_a + k₁ * t_a

For bob, it is : l_b + k₂ * t_b

Difference of start points, diff = l_b- l_a +  (k₂ * t_b) -  (k₁ * t_a)

Now, I want you to focus on last two terms of the above expression, they are : (k₂ * t_b) -  (k₁ * t_a) where k₁, k₂ are general integers. That's a linear combination of t₁ and t₂ which always happens to be a multiple of gcd(t_a, t_b). In fact any multiple of gcd(t₁, t₂) can always be written as a linear combination of t₁, t₂(see Bezout's lemma for both these facts).

So we can say that the difference is of the form :

diff = l_b- l_a + k * gcd(t_a, t_b), where k is yet another integer.

We intend to minimise the absolute value of diff; so we solve the equation, diff = 0(minimise diff) for k. (Note that it may be not be possible for integer value of k, i'm coming on it)

We get after rearranging,

k = -(l_b- l_a) / gcd(t_a, t_b) (Don't do integer division here).

Of course, since diff = 0 isn't always possible because the start points of alice and bob may never overlap. So this k we have here must be calculated as a float value (use long double), its floor and ceiling are two integer candidates one of which will make the diff value minimum.

So with ceil(k) and floor(k), we obtain two different diff values. For both of these diff values, we calculate the intersection length of intervals [l_a;r_a] and [l_a + diff; l_a + diff + (r_b — l_b)] and print the maximum intersection length for two diff values. (If you don't get this last part, think about it, it's easy, you can ask if you don't get it)

You can refer to my solution here. 45568612