Привет, Codeforces!
В Dec/19/2019 17:35 (Moscow time) состоится Educational Codeforces Round 78 (Rated for Div. 2).
Продолжается серия образовательных раундов в рамках инициативы Harbour.Space University! Подробности о сотрудничестве Harbour.Space University и Codeforces можно прочитать в посте.
Этот раунд будет рейтинговым для участников с рейтингом менее 2100. Соревнование будет проводиться по немного расширенным правилам ICPC. Штраф за каждую неверную посылку до посылки, являющейся полным решением, равен 10 минутам. После окончания раунда будет период времени длительностью в 12 часов, в течение которого вы можете попробовать взломать абсолютно любое решение (в том числе свое). Причем исходный код будет предоставлен не только для чтения, но и для копирования.
Вам будет предложено 6 задач на 2 часа. Мы надеемся, что вам они покажутся интересными.
Задачи вместе со мной придумывали и готовили Роман Roms Глазов, Адилбек adedalic Далабаев, Владимир vovuh Петров, Иван BledDest Андросов и Максим Neon Мещеряков. Также большое спасибо Михаилу MikeMirzayanov Мирзаянову за системы Polygon и Codeforces.
Удачи в раунде! Успешных решений!
Так же от наших друзей и партнёров из Harbour.Space есть сообщение для вас:
Привет Codeforces!
Истекают последние дни для подачи заявки на нашу стипендию магистра в Бангкоке!
Не упустите свой шанс и подайте заявку на участие в наших прогрессивных магистерских программах в области Data Science и Cyber Security всего за 3 шага:
1. Отправьте свое резюме, чтобы узнать, являетесь ли вы кандидатом на получение стипендии.
2. Если ваш профиль соответствует требованиям, один из наших сотрудников свяжется с вами.
3. Подайте заявку на программу, заплатите 125€ за заявку, пройдите серию интервью, и, если вы приняты, пакуйте чемоданы в Бангкок!
И, если вы знаете кого-то, кто может быть заинтересован в Digital Marketing, High Tech Entrepreneurship, Interaction Design или FinTech, поделитесь с ними информацией о нашей стипендии!
Кроме того, не забудьте прочитать наши последние блоги!
Поздравляем победителей:
Место | Участник | Задач решено | Штраф |
---|---|---|---|
1 | HIR180 | 6 | 106 |
2 | neal | 6 | 162 |
3 | receed | 6 | 172 |
4 | Geothermal | 6 | 174 |
5 | cerberus97 | 6 | 179 |
Поздравляем лучших взломщиков:
Место | Участник | Число взломов |
---|---|---|
1 | Akulyat | 24 |
2 | hoke_t | 20 |
3 | dhxh | 18:-1 |
4 | vovanstrr | 14 |
5 | WNG | 13:-1 |
И, наконец, поздравляем людей, отправивших первое полное решение по задаче:
Задача | Участник | Штраф |
---|---|---|
A | Dalgerok | 0:01 |
B | neal | 0:04 |
C | HIR180 | 0:08 |
D | Tutis | 0:17 |
E | gxnncrx1993 | 0:20 |
F | jqdai0815 | 0:07 |
UPD: Разбор опубликован
![ ]()
Best of luck to all those participating!!! Can't wait to see what problems there will be!!!
time to go blue.
Why educational rounds has more greedy problems?
Why educational rounds have more greedy problems?
because greed is good.
https://www.youtube.com/watch?v=6bbzwJ0Sx48
I was not expecting a video in the comment! LOL
sorry bro by mistake vote -ve ho gaya
You can still make positive.
Deleted
Clashes with Mirror replay round of ICPC Gwalior regionals on Codechef
If you have to do something else, just don't do the contest here instead of whining about it in the comments. There's no contest time that can satisfy everyone in every time zone.
Would have considered that helpful, if u had replied before the contests started rather than now. Anyways peace out!
anyone please provide any good resource(book,blog,lecture) for understanding lazy-propagation i am unable to understand that.
here
https://csacademy.com/lesson/segment_trees/
Who want to see my screencast(without comments)? Not sure I'm as cool as Um_nik tbh.
Here it is
Ставь минус раунду, если считаешь, что либо нужно ставить нормальный ML, либо не давать такие тесты как 72 задачи D.
Хотя там Е гениально связана с Д, поэтому можно и плюс поставить...
А в чем проблема 72 теста? Да, он находится далеко для первого теста покрывающего базовый случай, но с этим можно смириться.
я сделал перепосылку по задаче Б, но штраф не обновился ? это фишка educational раундов или я что-то не шарю?
Штраф прибавляется только, если первая успешная попытка провалилась на системном тесте, но вторая попытка прошла тесты.
а какое решение потом будут взламывать ? какое будет проходить системные тесты? и что если первое решение сфейлится
На системных тестах проверяются все успешные попытки. Играет роль только та, которая первым прошла системные тесты. Взломывать можно любое, прошедшие тесты решения.
Насколько мне известно, все посылки кроме последней не тестируются на полных тестах
Нет. На образовательных раундах не так. Проверяются все успешные попытки.
Solve D — Rejudge WA 72 — Find that in your solution there can be cycle but it outputs a tree — Write a dfs checker — Forget to call dfs function to get 3 more WAs. LOL... Anyway D and E are easier this time(Assuming they passes or does not get hacked).
Can D solved something like interval handling using set?
I tried and got MLE on test 51 :(
:)
yes, it can.
I thought of similar approach but stopped. Isn't your time complexity in worst case O(N^2) since you are also iterating the set of segments containing the i as starting point?
sort the segments depending on the endpoints.
now for each segment i, all you need to iterate on is the segments j between i + 1 and n that satisfies the condition: start_point[i] <= start_point[j] <= end_point[i]
which is the number of edges in the created graph
when you have more than n-1 edges, just stop.
Okay, I get
if(it.first > a[j].r) break;
this makes it run faster.For problem B, who solved using https://oeis.org/A140358
The link describes it as "Smallest positive integer k such that n = +-1+-2+-...+-k for some choice of +'s and -'s." What's the relation between this and problem B ?
Find the absolute difference of a and b. Then when we add number to the smaller of a and b, we're just reducing the absolute difference by that number. Otherwise we're increasing it. The problem becomes: Find the smallest positive integer k such that the absolute difference = +-1+-2+-...+-k for some choice of +'s and -'s. Effectively the problem is solved using the link above.
WHAT IS TEST CASE 2 OF DIV2B
Try for cases like 2 4 (Ans:3) or 5 14 (Ans:5)
how is the answer for 2,4 equal to 2 ? could you explain it a little more
Sorry my mistake. Corrected.
also for 5,14 case , i am getting 6 not 5 as the answer.
first 5 + 1 = 6 //step 1
6+2 = 8 // 2
8 + 3 = 11 // 3
11 + 4 = 15 // 4
15 + 5 = 20 // 5
14 + 6 = 20 // 6
Is there a better way ?
5 + (1 + 2 + 4 + 5) = 14 + 3
Screencast if anyone's interested: https://youtu.be/g4Gcl0yAgDU
Subscribed :)
42 minutes ?!
Wow! That's really cool. Hoping to get more of them
Can you explain how solve the problem B? I see that you are making some solution based on bits, But I could not get your solution...
The bits were only used to test parity. https://mirror.codeforces.com/blog/entry/72268?#comment-565771 describes my solution well.
How to solve D? P.s. round was great, so interestring problems!
What was pretest 2 of B?
I was first adding maximum possible n*(n + 1) /2 to the smallest number. Than answer = n + (difference between numbers) * 2;
whats wrong in this approach?
input: 1 31 20
output : 5
Yes, getting 6 as output.
Sorry, the output should be 5
test this: 1 5 answer is 3 because: 1) 1 6 2) 3 6 3) 6 6
Thanks for this case!
So what was the approach to solving the problem?
Sorry for my poor english, I cant explain this problem to you. The main idea that (a + b + tmp) mod 2 = 0 and (a + b + tmp) / 2 >= max(a, b), where tmp = 1 + 2 + 3 + .. + n. You can check my submission, I think it will help you. https://mirror.codeforces.com/contest/1278/submission/67230823
Is there any chance of getting the second problem being hacked?
I think no.Educational rounds usually have strong sys tests
Still, many solutions of problem D have been hacked!
But you just did ++tmp it does't mean tmp = 1 + 2 + 3 + ... +n.
i hope you understand.
tmp in my code its just a number that we will add next time, when we will need it. I increase a every time in cycle.
How do you guys solved C? I thought of a greedy approach but it didn't worked :(.
using 2 prefix sum arrays and then using maps
Let us suppose you eat s1 strawberries and b1 blueberries in the left and s2 strawberries and b2 blueberries to the right. If total strawberries is s and b, then we want s — (s1 + s2) = b — (b1 + b2). Or, equivalently, (s — b) — (s1 — b1) = (s2 — b2). So, for given s1 and b1, you need search for minimum steps in the right to make difference equal to the above. You can maintain hashtable to store for every (s2 — b2) the minimum steps to reach it in the right. This will speed up the search...Complexity O(nlogn)
What is wrong in the greedy approach?
Cant I just eat up the jar which is closest to me?
I reversed the problem; find the maximum possible of jars remaining such that the two types are equal in number. It is easy to see that such jars must form a prefix and a suffix of the given array.
I thus separate the array into two halves ($$$A$$$ and $$$B$$$) and reverse the second half. I also treat strawberry as $$$+1$$$ and blueberry as $$$-1$$$. I then iterate through $$$A$$$ collecting prefix sums and storing it in a map (be sure to set $$$M[0] := 0$$$ before), thus for each prefix sum I now know the biggest prefix of $$$A$$$ with that sum.
I then do similarly with $$$B$$$, except this time I treat strawberry as $$$-1$$$ and blueberry as $$$+1$$$, and I look up the prefix sums in the map. If the match exists, I add the two lengths and keep the biggest candidate seen. Finally, I restore the original answer by subtracting the maximum remainder from $$$2n$$$.
Sample: 67283206
Eh, got stuck on E this time, had several approaches that worked on paper but didn't know how to translate them into code. So, how to solve E? :)
Suppose you can build answer for any subtree of the current tree. Answer for subtree is a list of segments. We will say that the last segment in this list is the root.
Then you have a tree, you built answers for every children.
If there are no children, you can return a single segment {0,1}.
Otherwise you do something that is drawn on the picture. Real segments mean a last (root) segment and the area near it means other segments in this subtree.
a
,b
,c
are children ofd
anda'
,b'
,c'
,d'
are other segments in that subtrees. In this picture we build a treed
.You can see that there are no intersections between the children, but all the children root's are intersected with
d
.If you take the biggest (by count of segments in it) child as a base, you can add other children to this child and in total it will take nlogn time.
Seems that O(N) is possible too:
Wow, that's nice. The idea is almost the same as mine one, but works much faster.
Anyone solve C using binary search???
I tried with binary search but i got Wrong answer on test 2
same here, but now I realise that binary search will not work on some cases
Actually I managed to do that, you just need to build prefix differences (num2 — num1) & suffix differences, then sort the suffix ones and find a pair where suffix difference = -prefix difference using binary search.
Could you please explain the process in detail ?
The idea is as follows: 1. For all prefixes of the array containing from 0 to n elements inclusive we compute the difference between #of 1-s and 2-s (doesn't matter in which order). Going from the smaller to bigger ones, this is done in linear time. 2. Do the same thing for all suffixes from size 0 to n inclusive. Store the difference together with the size of the suffix 3. Sort the suffix differences from smaller difference to larger (if the differences match, put the one where the the length is bigger first) 4. For each of the prefixes, do a binary search in the sorted suffix differences array. We search for -prefix_differences[]. From all the suffixes with matching difference, select the largest (remember that due to our comparator being clever this requires almost no modifications). 5. Out of all the pairs select the one where 2 * n — prefix_length — suffix_length is smallest. This is the answer.
How to solve B?
Thank you dude
What is the logic behind that?
My answer for B. A and B
Let the numbers be $$$a$$$ and $$$b$$$. After the operations, we end up with another number that is $$$c$$$ where $$$c\ge \max(a, b)$$$. Now the operations are adding $$$1, 2, 3 ...$$$ so after $$$n$$$ operations we have $$$\frac{n\cdot(n+1)}{2}$$$ as total increment in $$$a$$$ and $$$b$$$, distributed among them in some way.
Now this total increment is also equal to $$$c-a + c-b = 2\cdot c -a-b$$$. Thus we have $$$\frac{n\cdot(n+1)}{2} = 2\cdot c-a-b$$$. Increment can also be written as $$$ |a-b|+2(c - \max(a,b))$$$.
From here we get the two required conditions. We loop over $$$n$$$ to get first $$$n$$$ that satisfies:
$$$\frac{n(n+1)}{2} \ge |a-b|$$$
$$$\frac{n(n+1)}{2} - |a-b|$$$ should be divisible by $$$2$$$
Now since we need increment $$$\frac{n(n+1)}{2} \ge \max(a,b)$$$ so at the max $$$n^2 = 10^9$$$, so the time complexity is $$$\sqrt{\max(a, b)}$$$.
My submission: 67218512
Btw I was watching William Lin's screencast, I have no idea what he has done. People have done it very quickly!
EDIT: Just realised, no need to loop over so many values, since we know $$$\frac{n(n+1)}{2} \ge \max(a, b)$$$. Thanks to @aniervs. That will give constant complexity..
dude thanx from bottom of heart here i made only small change in your logic to keep it simple and it works like 1. total increment = n*(n+1)/2 2.suppose number at which a and b both land will be c
so (c-a)+(c-b)=n*(n+1)/2 here c>=max(a,b) two cases arise (say)x=n*(n+1)/2+a+b
1.x%2==0&&x>=2*max(a,b)
iterate until above reach and print x
below is my solution https://mirror.codeforces.com/contest/1278/submission/67251204
tmwilliamlin168 Care to explain?
I did the same thing, looping over the first n such that a >= b (assuming a < b at first) and that a and b will have the same parity.
let's say $$$n$$$ is the value that $$$a$$$ and $$$b$$$ reach at the end, and there were $$$k$$$ operations. Then, $$$2n=a+b+\frac{k(k+1)}{2}$$$. Multplying by $$$2$$$, we get $$$4n=2a+2b+k(k+1)$$$. Let's say $$$a <= b$$$, then $$$4n>=4b$$$, so $$$2a+2b+k(k+1)>=4b$$$, we get $$$k(k+1)>=2b-2a$$$, then $$$(k+1)^2>=2b-2a$$$, so $$$k >= (2b-2a)^{1/2}-1$$$. But $$$2a+2b+k(k+1)$$$ is a multiple of $$$4$$$, so we can iterate $$$k$$$ by the first four values grater than or equal to $$$(2b-2a)^{1/2}-1$$$
How to solve C?
I took 2's as -1 and maintained prefix sum of array from left to center at each position and the same for the right of center.Then I stored first occurence of distinct prefix sum's to the left and right in different tables.Now just iterate over tables and check if an element in left table has a negative counterpart in the right one, if it does, then the gap is one of the possible answers.
This was the most difficult B I've ever seen.
That moment when you find the bug in the last second I'm so unlucky
That moment when C is easier than B :sad:
Not really? You find the index of first triangle number larger than abs(b — a) that has the same parity as abs(b — a) :) Because you can increment the smaller number one by 1+2+3+...+n EXCEPT for (triangle number — abs(b — a)) / 2 (which is an integer) :)
Only if
how to solve
meant that the question was easy :(I think C can be solved using binary search (searching for the the minimum number of jars ) but why i got WA on test 2 ???? ooooohhhh
Did you cover the case when you eat up no jar from the left side or right side?
I don't think C is possible with bianry search, since (number of jar to use)->(whether the goal is possible) function is not monotonic.
Could you give me a test that explain your idea?
I do not think binary search is possible too because if an interval size satisfies the criteria of the question, bigger interval may violate it...I haven't generated the precise test case but consider the below transition:
Binary search at len = x tells interval Lx,Rx is one of the feasible intervals: So interval is like : ..... 1 (1 2 2 1 1 2 2) 1 .... So just expanding the interval to the right or to the left or towards both sides changes the feasibility of interval to remain as answer.
In which test case my solution is wrong?? https://mirror.codeforces.com/contest/1278/submission/67240467
i solved it using binary search,what i did is make two vectors (vector of pairs {value,index}) for left(1 to n) and right part(n+1 to 2*n) where each element of both arrays stores the contribution they give to the "difference".(if s=no. of strawberrys and b=no. of blackberrys then difference is abs(s-b) ).sort both vectors. Now apply binary search such that left_i + right_j = difference. Also check for left_i=diff and right_j=diff separately. This is my code : https://mirror.codeforces.com/contest/1278/submission/67254126
For $$$C$$$ what is wrong with this approach:- Iterate from $$$2n$$$ to $$$n + 1$$$, If $$$a[i] == 1$$$ then $$$val = val + 1$$$ else $$$val = val - 1$$$, Push these values in an HashTable, $$$HashTable[val].pushback(index)$$$. Now iterate from 1 to n, keep a variable (let say) $$$val = 0$$$. If $$$a[i] == 1$$$ then $$$val = val + 1$$$ else $$$val = val - 1$$$, then find the smallest index corresponding to value $$$-val$$$ in HashTable(if present), and update the answer.
you don't cover the case when you eat no jar from the left or right
You may have missed some corner cases..
How to solve F?
Essentially, the problem is this (My solution requires some knowledge about calculus and probability) Given a binomial distribution $$$B(n, \frac{1}{m})$$$, we want $$$E(X^k)$$$.
Consider moment generating function $$$M(t) = E(e^{tX})$$$. Then, k-th moment, which is $$$E(X^k)$$$, can be achieved as $$$\frac{d^k}{dt^k} M(t)$$$ evaluated at $$$t = 0$$$. (one can prove this by taylor expansion)
Also, a mathematical fact — $$$M(t) = (pe^t + 1 - p)^n$$$ for $$$B(n, p)$$$.
Considering all this, try actually computing some derivatives. You can notice some pattern. By this pattern, we can get some $$$k$$$ degree polynomial about $$$n$$$ and $$$p = \frac{1}{m}$$$. The actual computation was quite messy, but the pattern was clearly noticable. The only task left is to implement this function and evaluate with rational numbers as given.
My approach is similar, but more intuitive IMO, if you have never seen the $$$M(t)=E(e^{tX})$$$ before.
We want:
Notice, it is similar to our familiar binomial expansion:
We want to create the term $i^k$ in the front, and then plug in $$$x=1$$$ to get our answer. How do we create the $$$i^k$$$? We, can do derivative with respect to $$$x$$$ :). Like this:
Now, multiply $x$ and repeat! Do it $$$k$$$ times total to get the term $$$i^k$$$. Calculating the $$$k$$$ derivatives takes $$$O(k^2)$$$ time.
Example: https://mirror.codeforces.com/contest/1278/submission/67249722
Off topic note: does anyone know how to fix the inline latex not rendering correctly? :P
Try to put
\displaystyle
in the beginning of a formula.$$$\displaystyle\sum_{i=0}^n\left[i^k\binom{n}{i}\left(\frac{1}{m}\right)^i\left(\frac{m-1}{m}\right)^{n-i}\right]$$$
I don't get what the "multiply x and repeat" mean. It's easy for me to understand that after k times derivatice, the right of this equation is just what we want. But how to deal with the left part of this equation? I tried to multiply x and derivative the left part but found nothing. Would you like to explain it in details? Thx
The right side of equation starts with term $$$x^i$$$. After derivative it becomes $$$ix^{i-1}$$$. Then we multiply by $$$x$$$ to get $$$ix^i$$$. Then another derivative to get $$$i^2x^{i-1}$$$. Then multiply by $$$x$$$ again, etc. It is straight forward to see how this process can generate term $$$i^k$$$. Now, for left side, we must also do the derivative and multiply by $$$x$$$ repetition. For this, one strategy is to keep an array of size $$$k+1$$$ of coefficients of terms $$$\left(\left(\frac{1}{m}\right)x+\frac{m-1}{m}\right)^{n-i}x^i$$$ for $$$i=0,\ldots,k$$$, perform $$$k$$$ updates on this. This is the approach I used in submission above.
THX!How stupid of me for forgetting this is a "programming" competition lol
Couldn't we just calculate the original expression in the top without using any derivatives as only thing to care about there is the nci terms other than that all terms can be easily calculated.
Ah, sorry, the sum is supposed to be to $$$n$$$, not $$$k$$$ (which is the reason why we can't calculate the sum directly). I have fixed the post now.
Can you tell why can we raise i to the power k?
Yes, it is actually from the definition of expected value. Informally, expected value of $$$f(x)$$$ is equal to:
In this case, $f(x) = x^k$, and the probability terms end up equaling the coefficients in my above comment.
Your solution was much better than the MGF one!
Is there some pattern tbh? I am facing a lot of difficulty as to how to calculate those messy derviatives, how did you write the recursion for the same?
Yes, I can explain derivative implementation details :).
We remove constant $$$\left(\frac{1}{m}\right)^n$$$ and account for it at the end. Now we do derivative and multiply by $$$x$$$.
Now, the second repetition.
We notice all terms are of form $$$C\cdot(x+m-1)^{n-i}\cdot x^i$$$ for some coefficient $$$C$$$ and some power $$$i$$$. We create an array $$$a$$$ of size $$$k+1$$$ with indices $$$i=0,...,k$$$ such that $$$a[i]$$$ stores coefficient of above term. Now we can apply derivatives and multiplication of $$$x$$$ on this array. We can see this operation results in relation $$$a[i]=(n-i)\cdot a[i-1]+i\cdot a[i]$$$.
Let's rewrite $$$x^k$$$ as the number of tuples $$$(x_1, x_2, \dots, x_k)$$$ such that $$$1 \le x_i \le n$$$ and for every $$$i$$$, the $$$x_i$$$-th shuffle of the deck resulted in a joker. Then the expected value of $$$x^k$$$ is the expected number of such tuples.
For each tuple, we need to determine the probability that it belongs to the set of tuples. If the number of distinct elements in a tuple is $$$y$$$, then this probability is $$$\frac{1}{m^y}$$$. Then for each $$$y$$$ calculate the number of tuples of size $$$k$$$ with exactly $$$y$$$ distinct elements; this can be done with dynamic programming — let $$$dp_{i, j}$$$ be the number of tuples of size $$$i$$$ with $$$j$$$ distinct elements; during each transition we either add a new element (there are $$$n - j$$$ ways to do it) or add a previously added element (there are $$$j$$$ ways to do it).
F can be done in $$$O(K \log K)$$$ using FFT.
$$$ \mathbb{E}(X^K)=\mathbb{E}((x_1+x_2+...+x_n)^K)$$$, where $$$x_i $$$ is indicator variable for the $$$i^{th}$$$ try.
$$$ = \mathbb{E}(\sum_{y_1+y_2+..+y_n=K} {K \choose {y_1,y_2,...,y_n}} \cdot x_1^{y_1} \cdot x_2^{y_2}...\cdot x_n^{y_n} ) $$$
$$$ = K! \cdot \mathbb{E}(\sum_{y_1+y_2+..+y_n=K} \frac{x_1^{y_1}}{y_1!} \cdot \frac{x_2^{y_2}}{y_2!} ... \cdot \frac{x_n^{y_n}}{y_n!})$$$
Now, the Inner expected value can be calculated as :
$$$ \sum_{i=1}^{min(N,K)} \binom{N}{i} (\frac{1}{M})^{i} \cdot \sum_{j=0}^{i} \binom{i}{j} \cdot (-1)^{i-j} \cdot \frac{j^K}{K!} $$$
So, cleaning, we get :
$$$ \sum_{i=1}^{min(N,K)} \frac{N!}{(N-i)!} \sum_{j=0}^{i} \frac{-1^{(i-j)}}{(i-j)!} \cdot \frac{j^K}{j!} $$$
The inner sum part for each $$$i$$$ can be calculated over all $$$i$$$ using NTT, and so overall $$$O(K \cdot \log K ) $$$
My Submission
See this problem.
Does anyone have proof that the answer for problem $$$F$$$ is polynomial of degree $$$k + 1$$$?
Yes, as I wrote in the comment right above your comment, I tried computing some derivatives and could get $$$k$$$ degree polynomial. We start with $$$(pe^t + (1-p))^n$$$, and we differentiate it $$$k$$$ times. Also notice that since we are dealing with $$$t = 0$$$, $$$e^t$$$ term left in the solution will be evaluated to 1.
Note that we only need to find the expected value of $$$X^k$$$, where $$$X$$$ is a binomially distributed random variable with parameter $$$1/m$$$. For binomially distributed random variables, we know that the $$$E[D_r(X)] = \frac{n!}{(n-r)!} \cdot p^r$$$, where $$$D_r(x)$$$ is the falling factorial function with degree $$$r$$$. Also, we know that $$$x^k = \sum_{i=0}^{i=k} S(k, i) D_i(x)$$$, where $$$S(k, i)$$$ is the Stirling number of the second kind. Now the answer can be computed using a dp to compute $$$S(k, i)$$$ and then by taking the expected value of the identity above.
I think
n
is too large in D/E. It's essential to solve problems like these using dfs approach, but you probably can't do it because stack size is not that large.I've got StackOverflowError in this submission 67239760 and accepted the same code but with bfs instead of dfs 67244701.
C can be solved with greedy approach in o(n) time. for right and left create a list X that each element is accumulated difference of the two types.
all numbers in X are between -5*10^4 and 5*10^4. then using X create a list ( or hashmap ) that is first occurrence of any number in X.
with this we decide how much of the total difference are we gonna cover from left or right.(greedy part) for example. 4 reds 2 blues so difference is -2.
I just browsed through some of the profiles and many of them says : William Lin fan-club
Anybody can shed some light on it for me?
when's the editorial coming?
After ends the hacking phase , hope so.
I think proof of B had similar idea as this question: https://atcoder.jp/contests/abc147/tasks/abc147_f
The way I solved B was like this :
Let $$$P_n$$$ be a set of distinct natural numbers from $$$1$$$ up to $$$n$$$. And let $$$sum[i] = \frac{i*(i+1)}{2}$$$, which is sum of all natural numbers from $$$1$$$ to $$$i$$$. Choose two disjoint subsets $$$A$$$ and $$$B$$$ of $$$P_n$$$ such that $$$A \cup B = P_n$$$ and the difference between the sum of elements of $$$A$$$ and $$$B$$$ be $$$d$$$. You have to choose $$$A$$$ and $$$B$$$ is such a way that $$$d$$$ is equal to the difference between $$$a$$$, and $$$b$$$, and then add the subset having smaller sum with $$$max(a,b)$$$ and the other one with $$$min(a,b)$$$ to make $$$a$$$ and $$$b$$$ equal. Now the problem is to choose such a $$$P_i$$$ such that $$$i$$$ is minimum and $$$d = abs(a-b)$$$. Notice that if I choose $$$P_i$$$ such that $$$sum[i]$$$ is even, then the set of all possible $$$d$$$ made from $$$P_i$$$ contains all non negative even numbers up to $$$sum[i]$$$. The reason is, if you choose $$$A$$$ such that the sum of elements of $$$A$$$ is $$$x$$$, and then put all the other numbers of $$$P_i$$$ inside $$$B$$$, then sum of elements of $$$B$$$ and $$$A$$$ shall be $$$sum[i] - x$$$, and $$$x$$$ respectively. So, $$$d = sum[i] - x -x = sum[i] - 2x$$$. So, $$$d$$$ is even. And obviously $$$1 \leq x \leq sum[i]$$$, so we get all the non negative even numbers up to $$$sum[i]$$$. Similarly, if $$$sum[i]$$$ is odd, all $$$d$$$s are odd. So, the solution is to find minimum value of $$$i$$$ such that $$$sum[i] \geq abs(a-b)$$$.
whats the hack for D? and also is it a wa hack or a tle one?
4
1 4
2 5
3 8
6 7
The answer should be NO.
who can help me???67258839
problem C
I think your mistake is, you are adding 1 to $$$ans2[i]$$$ and $$$ans1[i]$$$ when you get 1, and adding -1 when you get 2. But, you need to check frequency of 1 and 2 first. If the frequency of 1 is greater, then you increment $$$ans[i]$$$ if 1 is found, and otherwise increment decrease $$$ans[i]$$$ by 1. I did the same mistake first.
Can you give me a counterexample?thank you
I suggest you to use map. You are running the loop from 0 to $$$2*n$$$ and $$$2*n$$$ can be $$$2*10^5$$$ at most, but your array size is less than that. And also your nested loop may cause TLE.
all right, i find my misstake
if(i <= n && k-i <= n)
accpeted ,thank youWhen will system test start?
When system tests?-
someone can tell me why ( ans*(ans+1) — abs(a-b) )%2 == 0 in problem B ?
Imagine two numbers a and b. a=1 and b=5. The difference between both is 4. So we need a summation that is bigger than 4 like 1+2+3 which is equal to 3 steps. lets take the all the summation and add it to B so now the B becomes 11 and the difference is now 10. If you took the 2 from the summation and deleted it from B and added it to A, the difference will become 6 as you subtracted 2 from B and added it to A. do the same for the 3 and now the difference become 0. So overall, it has double the effect. 1+2+3=6 that summation accepts the difference between A and B to be:6,4,2,0. To sum up the idea, the summation result and the difference between A and B should be both either even or odd! I hope this helped!
ООООООООООООООООООООчень плохие претесты по D. Там просто взяли и не засунули в претесты случаи, со вложенными отрезками с n — 1 ребром.
А почему они должны были их туда засовывать?
Чтобы решения не падали, а также чтобы люди понимали, что тупое решение не заходит
Нужно же это самому продумать, а не требовать от жюри. Там не 5 тестов было, чтобы предъявлять, а 72.
Есть один косяк, что именно этот случай под корень режет тупой скан лайн
72-ой тест был именно такой ($$$n - 1$$$ ребро, но не дерево). Но его не хватило, видимо
Там при этом нет ситуации, когда компоненты связанности вложенные, а это все-таки давольно-таки сложный случай
Can somebody help me with the fact that — "What is the best way to approach a mathematical problem?"(Like Problem B in this contest).I usually try to make some test cases and from that cases try to form a general formula.But most of the times,i get WA in test case 4-5. :(
Whenever you solve a problem(or maybe you fail to) always try to understand the mathematical solution behind it. It will add up to your knowledge and may help you next time. This is a never-ending process, you have to learn something new, every time.
I think that each individual develops their own mathematical intuition for different types of problem and I am sorry to say that there is no shortcut to approach such problems, except one, practicing and up-solving lots and lots of math problems.
1 — Solve codeforces under 1000-dif-math problem This is best way to get a better view of math problems(also all A&B problem)[I had the same problem solving math problems] and how to think better. As you done(became master solving this kind of problems easily), Start solving under 1500-dif and so on.
2 — Study number theory.
3 — Every step in thinking on a problem ask yourself what to do now? this gives your mind a really nice view about the problem.
4 — Don't ignore some dumb ideas on a problem (sometimes this dumb ideas are the solution)
5 — Search for the pattern not for a single testcase you wrote, think more open (for example : in problem B, it was better to write down all the differences that adding 1 to n can make. (I also did this & got Acc on B)
Hope it was helpful.
Thanks,That was very helpful ^_^
When the ratings will be updated?
Can anyone share their approach to solve D?
basic idea is sort the range in increasing order of l. now consider a range at index i {l,r} find all the range that start b/w (l,r) and end after r then there will be intersection b/w segment without completely inside of another.
now how can we do that optimally, maintain a segment tree such that v[i]=range[i].r after sorting. we can find the range of index of segment for which segment start b/w (l,r) using lower_bound. now we can update using segment tree, if max of v[i] is less than r for an interval in segment tree then we won't go into that node, otherwise there can be atleast one segment for which it start b/w (l,r) and end after r.
In worst case there could nc2 edges but we don't need to go beyond n-1 edges. once there are n edges in graph it will no longer remain tree. so we can use dsu to maintain whether we got the cycle or not.
to find a node in segment tree such that there will be intersection b/w segments, its complexity will be O(logn) using segment tree. we need to add atmost n-1 edges so combined complexity will be O(nlogn) and we need to maintain dsu for cycle check that can be O(nlogn) so overall complexity will be O(nlogn) Here is my Submission
Shouldn't you have
Min[p] = v[l]
in your build function at line 111?Oh yeah, my mistake I missed that in build function but reason it didn't made any effect on verdict because Min[i] will always be zero and the condition I applied (Min[i]>r) will never be true.
I think my solution is pretty complex. return_me mentioned very simple idea for implementation as well in comment
Get all the edges until it's less that n :) 67240718
when editorial will be published ?
Can C be done in worst case O(n) time without using hashmap? I managed to do it in O(nlog n) using map, but I am curious about linear time!
I think so using prefix and suffix sums and jumping pointers.
Instead of using a map to query the nearest index in the right half with required difference in strawberries and blackberries, we can maintain an array with size $$$2n$$$ initialized to -1. This works since difference ranges between $$$-n$$$ and $$$+n$$$. This will run in $$$O(n)$$$.
Well yes, we can surely do that, but is there some general method to find if there exists a subarray whose sum is a given value, in linear time?
............When the ratings will be updated?
Auto comment: topic has been updated by awoo (previous revision, new revision, compare).
when will the parsing be published? (if anyone has a discard please)
Auto comment: topic has been updated by awoo (previous revision, new revision, compare).
Why does this solution 67308922 fails on case #434 on test 2?
67469642 Could someone please explain to me which part of my code is causing the "heap use after free" error shown in the diagnostics section? (I understand my code is in no way a solution to the problem it was submitted for, I would just like to know what is causing the error before I try to convert what I have into a solution)
Thank you!