Hey everyone!
I'd like to invite you to participate in the ECPC 2019 Kickoff contest on gym on Wednesday, 08:30 UTC. The contest was originally held in Cairo in 2019, and we woke up today and decided to publish it.
The problems were created by me, TripleM5da, KhaledKEE, Mohammad_Yasser, Dark, and Jester. The contest will include 14 problems, and you'll have 5 hours to solve them.
We hope you enjoy it :D
PS: Osama_Alkhodairy was a tester.
Thanks for uploading contest in gym! But i have 2 questions:
1) Is it team contest?
2) Is it suitable for master(s)?
1) Yes
2)During the official contest the top 3 teams consisted of masters and one of them had a grandmaster however none of them solved all the problems (not going to say how far they were thou) so yes even grandmasters will have fun participating.
Thanks again!
Where can I find the official scoreboard and the editorial of this contest?
Note: thanks for uploading the contest, my team enjoy to solve the problemset
Congrats for the win!
So there's no detailed scoreboard, but the top 3 teams all solved 11 problems, and they were mostly masters and 1 GM. We didn't prepare an official editorial, but I'm guessing people will discuss the solutions in the comments. I see no teams solved I, so I'll start the discussion with its solution.
Let's see what we can do with trees of diameter 2... aka star trees. I claim you can only form complete bipartite graphs. The reason is, you start with an empty graph, which is a complete bipartite graph, and every time you xor a complete bipartite graph with a star tree rooted at $$$r$$$, you simply change which side of the bipartition $$$r$$$ is in, and the graph remains complete bipartite.
So if your graph is complete bipartite, bicolor it and use star trees. Otherwise, you need trees of diameter 3.
I'll describe a way to form 2 edges that share an endpoint using the xor of 2 trees with diameter 3. Start with a star tree rooted at $$$r$$$. Cut the edge $$$(r,a)$$$ and add $$$(a,b)$$$ instead. That's the first tree. Now, swap the labels $$$a$$$ and $$$b$$$ to get the second tree. The xor of these trees is just the edges $$$(r,a)$$$ and $$$(r,b)$$$.
Next, I'll describe a way to decompose a connected graph containing an even number of edges into pairs of edges that share an endpoint. Let's do a dfs. Say we're currently in node $$$u$$$. We first solve for $$$u$$$'s children. Then, if $$$u$$$ is incident to en even number of edges, we pair these edges together with $$$u$$$ as the common endpoint. If they're odd, we pair them together except the edge between $$$u$$$ and its parent. Its parent will take care of that.
Finally, the case where the graph has an odd number of edges. If $$$n$$$ is odd, $$$n-1$$$ is even, and we can only make graph with an even number of edges, so it's impossible. Otherwise, just xor your graph with a star tree to make the number of edges even. Be careful though; that shouldn't disconnect the graph. The best way to guarantee this is to choose a node which isn't an articulation point to be the star tree's root (e.g. a leaf in the dfs tree.)
Code
How to solve problem K, please?
1) for each plant i you need to find "good" segment — segment of time [l, r] where height[i] <= height[i + 1]
it can be done easily, just check all situations like (h[i] <= h[i + 1] and g[i] <= g[i + 1]), (h[i] > h[i + 1] and g[i] < g[i + 1]), etc...
2) now we need to check whether we have a time moment t, such that it belongs to all these good segments, i.e. we need to intersect all segments
3) intersection is done as usual — for each segment make point (l, +1) and (r + 1, -1), then sort these points, go from left to right and keep the balance
Thank you
Let's look at three possible situations:
1) there are letters $$$a$$$ and $$$c$$$, but there is no $$$b$$$ — answer is $$$-1$$$, as we can't rearrange letters so they would satisfy condition
2) there are letters $$$a$$$ (maybe with $$$b$$$), or letters $$$c$$$ (maybe with $$$b$$$) — answer is $$$0$$$, condition is true from the start
3) there are $$$a$$$, $$$b$$$ and $$$c$$$ — we need to make the string look like $$$aa...abc...cc$$$ or $$$cc...cba...aa$$$, calculate the difference between initial string and both of these strings and choose the best
4) how to calculate difference between two strings $$$s_1$$$ and $$$s_2$$$:
basically it's just going $$$i$$$ from left to right, increasing the answer whenever $$$s_1[i] \ne s_2[i]$$$, then we divide result by $$$2$$$, as we counted twice situations where for example
$$$s_1[j_1] = a\ and\ s_1[j_2] = c$$$
$$$s_2[j_1] = c\ and\ s_2[j_2] = a$$$
they would result in just one swap of indices $$$j_1$$$ and $$$j_2$$$
the only thing you need to keep in mind, when you see situation like this
$$$s_1[j_1] = a\ and\ s_1[j_2] = b$$$
$$$s_2[j_1] = b\ and\ s_2[j_2] = c$$$
you see that in this situation you need one more swap
First look at the operations $$$OR$$$ and $$$XOR$$$:
1) $$$a_i | (a_i - 1)$$$ sets all $$$0$$$ (in binary presentation) to $$$1$$$ at the end (before the first $$$1$$$) of the number $$$a_i$$$
$$$11001000 \rightarrow 11001111$$$
2) $$$a_i \oplus (a_i - 1)$$$ does the same as $$$OR$$$ (sets all $$$0$$$ at the end to $$$1$$$) and erases all bits to the left of the first $$$1$$$
$$$11001000 \rightarrow 00001111$$$
You can see that applying $$$OR$$$ operation to the same number second time doesn't change it.
Applying $$$XOR$$$ operation to the same number second time, or applying it to the number that was $$$OR$$$-ed sets it to $$$1$$$
Once a number reaches $$$1$$$ it can't change anymore.
So we see that each number can change its value at most 2 times: one $$$OR$$$ one $$$XOR$$$, or two $$$XOR$$$.
Make a segment tree on sum, store flags like $$$done_{or}, done_{xor},\ \textit{numbers_are_ones}$$$ in vertices of this tree, so you won't do changes that you've already done.
Asymptotics $$$O((n + q)log n)$$$
Emulate given function.
Imagine we have an array of 30 pointers: $$$p[i]$$$ — index of the first number, that has $$$i$$$-th bit on, and $$$vis[p[i]] = false$$$ — this number hasn't been visited
We can keep such pointers pretty easily, you don't need to update them immediately, just whenever you need them do
You can make another 2 pointers: for the first unvisited number, that's equal to $$$0$$$, and just for the first unvisited number, with the same lazy-update
Now look what happens in the function:
1) in the first for-loop we run through the indices from $$$0$$$ to $$$n - 1$$$, look if we have at least one bit in common.
We can run through all active bits in current number $$$a[u]$$$ and take the minimum index $$$p[i]$$$, corresponding to these bits $$$min({p[i] : i\ bit \in a[u]})$$$. Pick this minimum and call function from it, then calculate this minimum again and again, until there is not numbers left
2) in the second for-loop we do the same, but go through the bits that are not set in the current number $$$min({p[i] : i\ bit\ not \in a[u]})$$$, (don't forget about zeros, they don't have any bits, so we've made a special pointer for them)
(actually we can do this part easier and just go through all the unvisited vertices, no matter what bits they have, if a number has $$$1$$$ in our bit it's already been visited in the first for-loop, otherwise it's our candidate)
if $$$a[u] = 0$$$ first for-loop does nothing, second for-loop just iterates over all numbers that are not visited
Asymtotics $$$O(n log(max_a))$$$
Binary search maximum possible distance from the first city that exploded $$$c[1]$$$. Precalculate distances between each pair of cities, this can be done by doing bfs $$$n$$$ times.
Imagine we are at the distance $$$r$$$ from the city $$$c[1]$$$. We can iterate over all cities that were bombed, and keep the minimal time needed to reach current city. If this time is greater than $$$d[i]$$$ — we can't start at the distance $$$\ge r$$$ from the first city.
So let $$$R$$$ be the maximum possible distance from the first city. The answer is the amount of vertices in graph such that $$$dist(v, c[1]) \le R$$$
Asymptotics $$$O(n \cdot(n + m) + qlogn)$$$
Denote start node as $$$v_{start}$$$
1) Look at $$$s_{min} = min({s})$$$ — it should be the weight of the smallest edge outcoming from the $$$v_{start}$$$, so mark as candidates both ends $$$(u, v)$$$ for each edge with weight equal to $$$s_{min}$$$ such that $$$(s[u] = s_{min})\ xor\ (s[v] = s_{min})$$$ — one vertex $$$u$$$ or $$$v$$$ has it's distance equal to $$$s_{min}$$$
2) Distance of the $$$v_{start}$$$ should be $$$2 \cdot s_{min}$$$ — as the most optimal way is to use the smallest edge from $$$v_{start}$$$ two times, so we also mark all such vertices as candidates.
Then we iterate from $$$1$$$ to $$$n$$$, look if this vertex was marked as candidate in both cases and call Djkstra from this node to check if it gives us a correct array. In Djkstra return as soon as you found that $$$dist[v] < s[v]$$$ or $$$dist[v] > s[v]$$$ and cannot become smaller.
I don't know how many candidates we'll have, but it seems like not a lot. Something like if we have lots of candidates $$$\rightarrow$$$ graph is dense $$$\rightarrow$$$ $$$\sqrt{E}$$$ vertices. Or if the graph is sparse $$$\rightarrow$$$ we'll make small amount of operations before telling that calculated distance for some vertex is bad. But I'm not sure about that. This solution works in 607ms.
Asymtotics $$$O(candidates \cdot ElogV)$$$
What is the expected solution to H?
I'll use $$$(a,b,c)$$$ to denote an edge from $$$a$$$ to $$$b$$$ with cost $$$c$$$.
If there's an edge $$$(a,b,c)$$$ such that $$$s_a+c<s_b$$$, that's a clear contradiction and there's no answer.
Let's call a node $$$u$$$ critical if it's adjacent to the hidden node, and the ONLY shortest path from the hidden node to $$$u$$$ is the direct edge between them. If a node $$$u$$$ is not critical, the path from the hidden node to $$$u$$$ must pass through another node $$$v$$$, so there must be an edge $$$(v,u,c)$$$ such that $$$s_v+c=s_u$$$. On the other hand, if node such edge exists, $$$u$$$ must be critical.
So now, after scanning the edges, we can pin down which nodes are critical. What constraints do we have now on the hidden node?
We can see that these constraints are also sufficient! If we make it work for the critical nodes, all the other nodes will follow. We can pin down which nodes pass the first $$$2$$$ constraints in $$$O(n+m)$$$ by iterating through the critical nodes and then their neighbors, and then we can check the third constraint in $$$O(n+m)$$$ by iterating through the candidates and then their neighbors.
Code
How to solve problem B?
It is obvious that we should increase the length of a shortest side of the triangle. You can calculate the optimal increase using ternary search.
Code
wow, I was doing 3 ternary searches to check which side I should increase.
For some reason something went wrong.
thank you!
UPD: I changed this line in ternary search:
(f1 < f2) ? l = m1 : r = m2;
to this:
(f1 > f2) ? r = m2 : l = m1;
and I got accepted
It also can be solved without ternary search: for two fixed triangle sides $$$a$$$ and $$$b$$$, the area is maximized when the third side is equal to $$$\sqrt{a^2 + b^2}$$$, that is, the angle $$$\alpha$$$ between $$$a$$$ and $$$b$$$ is $$$\frac \pi 2$$$. This is because the area is equal to $$$\frac 1 2 a b \cdot \sin{\alpha}$$$. Using this, we can just get as close to this value as possible.
can anyone please explain how to solve L?
Notice that the xor is just for Ehab-effect. xoring an $$$n$$$-bit number with a random $$$n$$$-bit number is simply equivalent to replacing it with a random number. The probability this new number is $$$0$$$ is always $$$\frac{1}{2^n}$$$. let's call this $$$a$$$.
Let's denote $$$P(event)$$$ as the probability that event would happen. Let's first try to find $$$E(m)$$$, the expected number of moves. This is equal to:
Now, how do we modify this sum to get $$$E(m^2)$$$? Notice that the $$$i^{th}$$$ perfect square is just the sum of the first $$$i$$$ odd numbers. So we can multiply $$$P(m>i)$$$ by $$$(2i+1)$$$ to get the desired formula:
Notice that $$$P(m>i)$$$ means neither of the first $$$i$$$ rounds made $$$x$$$ equal to $$$0$$$, so $$$P(m>i)$$$ is just $$$(1-a)^i$$$. So we want:
This is an arithmetic-geometric progression. You can get its sum with a closed formula in $$$O(1)$$$.
There's an alternative calculus-based solution! Let's start over. The most direct formula for $$$E(m^2)$$$ is:
Now, $$$P(m=i)$$$ means neither of the first $$$i-1$$$ rounds made $$$x$$$ equal to $$$0$$$, but the $$$i^{th}$$$ round did. So it's equal to $$$(1-a)^{i-1}*a$$$. Our desired sum is:
Let's start with the geometric-progression formula:
$
Let's look at $$$(1-a)^i$$$. If you differentiate with respect to $$$a$$$, multiply with $$$1-a$$$, and then differentiate again, you'll get $$$(1-a)^{i-1}*i^2$$$. Looks familiar? Do the same to the RHS to get an $$$O(1)$$$ formula for the answer.
Bonus: try to modify both methods to get $$$E(m^k)$$$ in $$$O(k^2)$$$.
I solved problem L using relation $$$E((x+1)^2)=E(x^2)+1+2*E(x)$$$, if we generalize this relation for $$$K$$$ , we can use binomial expansion to calculate $$$E(x^k)$$$ from $$$ E(x),E(x^2)....E(x^{k-1})$$$.
`
How to solve problem F? I couldn't get any further after simplifying the sum to $$$ (m1) \times(\sum_{x=l}^{r}((m2 \times x )+ x)-\sum_{x=l}^{r}((m2 \times x) AND x))$$$ where m1 is the minimum slope and m2 is the difference between the two slopes.
The expression boils down to sum( (x<<s1) ^ (x<<s2)). Lets count for every power of two how many times it appears in the expression, fix the power of two K, and now we need to count how many binary strings less or equal than X exists such that exactly one bit from {K-s1,K-s2} is on, its classic dp on digits.
Thank you , I get it now
I try to submit this code several times but i get wrong answer in pypy2 but it run in my pc can someone help me to get this code accepted in pypy2?
in problem M i take input with this way inp=open('lis.in','r') but it gives me RTE what is wrong and sorry for my bad English
i just add .strip() to second line and it get accepted Your code because when you add strip to readline() it remove '\n' this character from the string .
hope it well__
WA on test 12 — Problem J
7
bacacca
output: 2
Can we solve Problem F, if $$$s1$$$ and $$$s2$$$ are not powers of $$$2$$$?
Hi! can anyone share problem A solution. I am getting runtime error. Also why the third sample input has 39 as answer. It should be 36 I guess?
Did you found out the solution? I am also stuck rn. I know how to find the string using 2 pointer but i am not able to shrink it like we usually do cause order matters here. Can you share your approach. Thanks!
Nvm could be easily done in O(n^2)
can you show me your solution ?