### mohammedehab2002's blog

By mohammedehab2002, history, 22 months ago,

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, DeadlyPillow, 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

Announcement of ECPC 2019 Kickoff

• +64

 » 22 months ago, # |   +27 PS: Osama_Alkhodairy was a tester.
 » 22 months ago, # |   +14 Thanks for uploading contest in gym! But i have 2 questions:1) Is it team contest?2) Is it suitable for master(s)?
•  » » 22 months ago, # ^ | ← Rev. 2 →   +9 1) Yes2)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.
•  » » » 22 months ago, # ^ |   0 Thanks again!
•  » » » 22 months ago, # ^ | ← Rev. 2 →   +8 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
•  » » » » 22 months ago, # ^ | ← Rev. 2 →   +23 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. I's solutionLet'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
 » 22 months ago, # |   0 How to solve problem K, please?
•  » » 22 months ago, # ^ | ← Rev. 2 →   +18 Solution for problem K1) 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 segments3) 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
•  » » » 22 months ago, # ^ |   0 Thank you
 » 22 months ago, # | ← Rev. 8 →   +15 Solution for problem JLet'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 condition2) there are letters $a$ (maybe with $b$), or letters $c$ (maybe with $b$) — answer is $0$, condition is true from the start3) 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 best4) 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] = athey would result in just one swap of indices j_1 and j_2the only thing you need to keep in mind, when you see situation like thiss_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 Solution for problem EFirst 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 110011112) 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)$ Solution for problem CEmulate 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 visitedWe can keep such pointers pretty easily, you don't need to update them immediately, just whenever you need them do while (p[i] < n && (vis[p[i]] || !(a[p[i]] & (1 << i)) )) p[i]++ 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-updateNow 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 left2) 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 visitedAsymtotics $O(n log(max_a))$ Solution for problem DBinary 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)$ Solution for problem HDenote 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)$
 » 22 months ago, # |   0 What is the expected solution to H?
•  » » 22 months ago, # ^ | ← Rev. 2 →   +19 H's solutionI'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  » 22 months ago, # | +6 How to solve problem B? •  » » 22 months ago, # ^ | ← Rev. 7 → +2 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 •  » » » 22 months ago, # ^ | ← Rev. 2 → 0 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 •  » » 22 months ago, # ^ | +22 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.  » 22 months ago, # | 0 can anyone please explain how to solve L? •  » » 22 months ago, # ^ | ← Rev. 2 → +14 L's solutionNotice 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:$\sum\limits_{i=0}^{\infty} P(m>i)$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:$\sum\limits_{i=0}^{\infty} P(m>i)*(2i+1)$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:$\sum\limits_{i=0}^{\infty} (1-a)^i*(2i+1)$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:$\sum\limits_{i=1}^{\infty} i^2*P(m=i)$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:$a*\sum\limits_{i=1}^{\infty} (1-a)^{i-1}*i^2$Let's start with the geometric-progression formula:$\sum\limits_{i=1}^{\infty} (1-a)^i=\frac{1}{a}-1$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)$. •  » » » 22 months ago, # ^ | +5 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})$.`  » 22 months ago, # | 0 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. •  » » 22 months ago, # ^ | 0 The expression boils down to sum( (x< •  » » » 22 months ago, # ^ | 0 Thank you , I get it now  » 21 month(s) ago, # | 0 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?  » 20 months ago, # | 0 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 •  » » 20 months ago, # ^ | ← Rev. 2 → 0 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__ •  » » » 20 months ago, # ^ | ← Rev. 2 → 0 Thanks i got accepted its a good notice  » 18 months ago, # | 0 WA on test 12 — Problem J Try this test case7bacaccaoutput: 2  » 17 months ago, # | 0 Can we solve Problem F, if$s1$and$s2$are not powers of$2\$?
 » 13 months ago, # |   0 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?
•  » » 13 months ago, # ^ |   0 Are you getting input from file? in alphabetical order.
•  » » 12 months ago, # ^ |   0 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!
•  » » » 12 months ago, # ^ |   0 Nvm could be easily done in O(n^2)
•  » » » » 7 weeks ago, # ^ |   -10 can you show me your solution ?