Привет, Codeforces!
В 05.06.2019 17:35 (Московское время) состоится Educational Codeforces Round 66 (рейтинговый для Див. 2).
Продолжается серия образовательных раундов в рамках инициативы Harbour.Space University! Подробности о сотрудничестве Harbour.Space University и Codeforces можно прочитать в посте.
Этот раунд будет рейтинговым для участников с рейтингом менее 2100. Соревнование будет проводиться по немного расширенным правилам ICPC. Штраф за каждую неверную посылку до посылки, являющейся полным решением, равен 10 минутам. После окончания раунда будет период времени длительностью в 12 часов, в течение которого вы можете попробовать взломать абсолютно любое решение (в том числе свое). Причем исходный код будет предоставлен не только для чтения, но и для копирования.
Вам будет предложено 7 задач на 2 часа. Мы надеемся, что вам они покажутся интересными.
Задачи вместе со мной придумывали и готовили Роман Roms Глазов, Адилбек adedalic Далабаев, Владимир vovuh Петров, Иван BledDest Андросов и Максим Neon Мещеряков. Также большое спасибо Михаилу MikeMirzayanov Мирзаянову за системы Polygon и Codeforces.
Удачи в раунде! Успешных решений!
UPD:
Так же от наших друзей и партнёров из Harbour.Space есть сообщение для вас:
Codeforces! Каков следующий шаг на пути вашего самосовершенствования?
Мы понимаем что такое заниматься своим развитием самим — в конце концов, мы стартап-университет, и наш студенческий коллектив является исключительным отчасти потому, что он состоит из людей, которые не ждали, пока кто-нибудь покажет им путь.
Если вы такие же, ваше место в Harbour.Space. Цель нашего университета — создать глобальное сообщество людей такого типа, независимо от возраста и национальности, потому что когда вы работаете самостоятельно, вы можете измениться к лучшему, но когда вы работаете вместе с другими, вы можете изменить Мир.
Если вы считаете, что в вас есть это, то вы нужны нам!
Учебный план является частью того, что делает модули такими особенными. А другая часть? Наши выдающиеся учителя, которые являются лидерами в своих отраслях.
Мы верим в ваши достоинства и потенциал! Станьте частью нашей команды!
Поздравляем победителей:
| Место | Участник | Задач решено | Штраф |
|---|---|---|---|
| 1 | mango_lassi | 6 | 145 |
| 2 | E869120 | 6 | 148 |
| 3 | kiyotaka | 6 | 154 |
| 4 | 244mhq | 6 | 154 |
| 5 | mzen | 6 | 157 |
Поздравляем лучших взломщиков:
| Место | Участник | Число взломов |
|---|---|---|
| 1 | Radewoosh | 97:-19 |
| 2 | test_hack | 56:-37 |
| 3 | alvinvaja | 30:-10 |
| 4 | AryaKnight | 48:-48 |
| 5 | nikolapesic2802 | 30:-14 |
И, наконец, поздравляем людей, отправивших первое полное решение по задаче:
| Задача | Участник | Штраф |
|---|---|---|
| A | okwedook | 0:01 |
| B | mango_lassi | 0:05 |
| C | nuip | 0:07 |
| D | Yushen | 0:04 |
| E | Sehnsucht | 0:20 |
| F | ---------- | 0:05 |
| G | LgndryGrandmasturbator | 0:47 |
UPD: Разбор опубликован
[deleted]
Thanks for the consecutive contests! Wish that the problem statements will be neat and clean and short as the previous one. Eid Mubarak everyone!
Eid Mubarak ! Happy Eid-ul-Fitr !!
This picture reminds me of this song.
You want to be white rank?
No, I want you to be white rank! I want something just like this
true, but make your special girl unrated, not cm
stef just reach 2400 instead of 2300 next time and i guarantee you will be more successful
The guy she told you not to worry about is Tourist.
Comment "Is it Rated?" if you want to gain contribution points! (In the negative direction)
Let me do this job for you.
Is is Rated (for Div1)?
Ans seems Yes.
MikeMirzayanov awoo Please fix it.
Everyone is registered as "Contestants".
Mark me and others as "out of competition".
No, it is not rated for you. It is rated only for those who are below the master
It is not a bug. In Educational Rounds no one is out of contest everyone can compete officially but it is only rated for Div2. And after contest in the Final Standings there are options (div1,div2) to see standings
thank u, pik misha!!!!!!!!!!!!!!!!! i love you
we all love pik misha :D
I never really understood the concept of Educational Rounds. Don't we learn something new from every contest? Why exactly term it Educational?
LoOOoOOooOooLoOOOoooOOOoOOLoOoOooOoooooOOL. ROFL. LMAO.
Problems at usual contests: "use a segment tree with some trciky operations and tricky queries"
Problems at educationals: "use a trivial segment tree, (yes) and queries are in the form of $$$[p_i,i]$$$
didn't you feel that difference?"
Finally found the person who uses the id LanceTheDragonTrainer.
no, he uses id riela
LoOOoOOooOooLoOOOoooOOOoOOLoOoOooOoooooOOL. ROFL. LMAO.
marymarine is no longer my alt, we disbanded because he doesnt like twice.
Yup, that makes sense. Thanks!
And for us mortals, Educational rounds are ironically harder than the normal rounds, and the editorial comes the same way for both educational and normal rounds, so not even sure what's the point of calling it "educational".
it is your fault if you fail to solve problems
once more:
edu rounds -> hard problems with classical ideas
usual rounds -> hard tricky problems
Yes, I'm just saying how ironic it is for a round that calls itself "educational" is as educational as any other round and it manages to make itself harder than an average round.
I just don't get it, I literally don't get why it's called "educational", it has no special property what so ever that would make it educational.
I'm talking about ABC tasks, I'm not qualified enough to talk about the difficulty of DEF...
Yes, DEF are actually educational
If educationals DEF are so much easier than normal round DEF then why does DEF get solved the same/less than in a normal round ? This EDU alone has only like 20 people who solved DEF, maybe 50 that solved DE, and the rest are D
i didn't say they are easier, i meant they are with classic ideas
The purpose of contests is for people to solve problems and learn from them I think.
It doesn't matter if its name was "Educational" or something. If you are good you can solve problem. If you are not you need to learn more, tutorials is a good point.
I'm fine with the rounds, the more the merrier, just saying that EDU rounds are worse than normal rounds imo.
I enjoyed all of the problems. I mean we aren't allow to choose our life condition so we need to prepare for the worst.
I enjoyed the problems of this EDU as well, I'm talking about the previous EDU.
Yes, I'm talking about every problem :)
awoo is a boy or a girl?
I'm a wolf! awoo~
awoo and uwu?
why must you do this to me
UWU
just awoo then?
That moment when you realize that a wolf can code better than you.
trueBest Girl is also Best boy
yes
Konstantin Mertsalov is a nice man , we discussed some math problems with him through skype
Eid Mubarak to all Programmer.
Baraa_Armoush ur logic hhhhhhh
First question has wrong limits on K!! Because of this I lost valuable time
I wonder why im getting downvotes...am I wrong?
what is wrong with the limits?
k = 1 in one test case but question says k>=2
Can you see the test case? How do you know that?
I added the check for k == 1 and it passed
Is that the only difference in your solutions?
If you want to be sure add assert(k >= 2) right after your read input and submit again! If you are right you should get a RuntimeError verdict.
You changed types from int to long long
I don't think it's true. My accepted submission would loop forever on $$$K = 1$$$.
Yes.
because you wrote very trashy comment.
you are just a pupil after 4 years and you said codeforces contest has a problem ??
how did you decide to write this comment ?
Thanks for the round.
The worst B problem I have ever solved
There is always "A worse" in CF...
why?In my opinion this problem is cool.
IDK, maybe im stupid, but i couldn`t find whats wrong with my code
But tricky. Swapping C and B would be better.
The same opinion
How did you solve it? I got WA in test 5.
Think of following test case 10^5/2-1 nested for loops with add.
https://mirror.codeforces.com/contest/1175/submission/55150517 what's wrong with this? please help me in debugging.
Like this?
Yes. People who are storing value to add will result in overflow for long long.
I didn't do that but still I'm getting wrong answer on test case 8. Please help.
same here, can't figure out why am I getting WA on TC 8
even got WA on tc8. I wasn't checking th condition when the answer was exactly 2^32.
pa.n.ik Can you please take a look at this ?? 55171711 I have checked for 2^32
amstan your code is too complicated to understand, here refer my solution
It's even easier to understand with recursion. Here: recursive_solution_to_B
Can you tell why this code gives WA on test case 9?
55158372
I guess you are using the accumulated sum and multiplying it for each loop. Check for input : 6 for 3 add end for 3 add end // output : 12 // should be : 6
I really liked D there's a relation between each possibility but I don't know how this is going to help :/ how did you solve it
Expand the summation using prefix sums everywhere
Is this correct k*ps[n] — (sum of small k-1 smallest prefix sum)
Yeah
Too bad I cannot implement it. Though this problem looks like some DP optimization which I am not familiar with and started searching articles for it.
don't forget to exclude ps[n] though, while finding k-1 smallest prefix sums.
it is easier to implement using suffix array
Задача F баян — была на отборе на БГУИР в марте
Problem B!! :'( made it the worst contest I gave on codeforces :/ and why cant we use python3 signal in codes :'/
Problem B is just a simple stack based problem of evaluating parenthesized expressions.
And as for signal, check the documentation. signal.alarm is unix only
Can you tell why this code gives WA on test case 9? 55158372
I'm so sorry of that. I just wanted to laugh and maybe some upvotes. I didn't think reminding some old joke would be that annoying. Maybe this cause more downvote, but I want to talk some more words. I'm just a kid, please just don't make me cry. :( Last day I started commenting and I got contribution +3. But now it is going down to -4. I'm so depressed by now. I promise I won't write something idiot more. I'm sorry again. Can you help me get my contribution up to 0 again?
Just a reminder. :D
Which site you use to upload photos there's alot of memes in my mind to post XD
I just got this from another comment on CF
But I found a site to upload.
After that I disabled my antivirus and then something special happened to my desktop.(the backgroung and resolution changed suddenly)
Be Carefull. Btw do you know how to get upvotes?
Don't post all the jokes you think about because some of them aren't that funny
the more unique and unexpected the joke is the more upvotes it will get also the right timing plays a role
. Btw I did not understand what does the antivirus has to do with uploading a photo.
After uploading I wanted to send it here. I copied the URL and posted it. Then the antivirus blocked it. Because I wasn't sure that it is sent correctly. I turned off the antivirus. And after a few moments that happened. It was my mistake to turn off the antivirus.
D was quite solvable
Maybe not for me.
C is extremely hard to me. lol In my opinion D is easier than C. :)
Agree. 38 minutes spent on C, mostly staring at piece of paper. 30 minutes for D, no idea why it took so long.
How to solve E?
Create sparse table such that nxt[i][j] is the maximum index sucht that [i, nxt[i][j] ] can be covered using atmost $$$2^j$$$ segments.
Can be solved using binary lifting (this is the same, but actually easier to code).
Don't we call binary lifting on arrays as sparse table?
how do u prove this?
During the contest time I was thinking if I can create a sqrt decomposition solution.
Couldn't find one. Can you think of one? ( I am pretty sure that the time limit can be tight)
I have one in mind. For all precompute the ans for all [i, j] such that $$$j - i \lt \sqrt{n}$$$. Then the queries for $$$y - x \lt \sqrt{n}$$$ can be answered in O(1) and for others in $$$O(\sqrt(n))$$$
Yes, I had similar in mind.
But I realized, it can be troublesome when an interval ( say [li, ri]) lies inside 2 blocks (say, [√n+1, 2*√n] call it block1 and [2*√n+1, 3*√n] call it block2).
Because, that time when we loop through block1 and block2, I am not sure how to combine their answers. Are you able to feel the difficulty? Or do you have a better approach to it?
Would you like to elaborate more on how do you use the sparse table to find the minimum number of segments?
I learnt about sparse table and successfully solved this problem.
Thanks to you <3
E:
https://informatics.mccme.ru/mod/statements/view3.php?id=18805&chapterid=113099
How to solve D?
Let 1, x2, x3,...,n be index where new subarray starts. Then answer is f(1)×1 + (f(x2)-f(1))×2+....+(f(n)-f(x_k-2))×k. Open it. f(i) is prefix sum till i'th element.
but how do you know which are the indexes where a new subarray starts?
The idea is that once you expand you just get the sum of the suffixes that start with the left endings of the segments. Therefore the answer is the sum of the k-1 largest suffixes (without allowing the total complete string) plus the total sum.
Thank you Jefe :D
Do anyone know what test case 6 might be?
test case 6 broke my solution and with a brute force I found this test case:
5 3
-1 -5 5 -3 6
Expected 16 but I answered 13.
I can't be sure if your mistake is the same as mine though
Thanks alot. Same mistake.
If you need a lengthier explanation go here https://medium.com/@harryjobz/educational-round-66-a673621a3959
You can extend this proof to general k segments
can't we solve C using the ternary search?
No you can't 55147246
Why go for ternary when you can do with binary?
Ref: 55155030
I used binary search on answer over f(x). Now if f(x) exists, it means that x must be equal array[i]+f(x) or arr[i]-f(x). Iterate over the array to find such possible 'i' where you get at least k-1 elements in the array which are less than or equal to f(x) (using upper bound). If you find any such 'i' then modify r, else modify l.
f(x) = (l+r)/2 i.e. mid
Hope it helps! :)
No. because the f(x) might be something like sin(x) (just for imagination!). suppose there are k + 1 points close to each other, then a huge gap then again k + 1 points close to each other, then a huge gap and so on...
Ok. to clarify my idea let's see this test case
k = 0 so $$$f_k(x)$$$ means the distance of the closest point to x for each integer x. the graph of $$$f_k(x)$$$ will be like this :
How to solve problem C?
Average of points which have k-1 given integers between them.
Could you please explain the correctness of this approach?
If the solution you get from that is not correct, that means you could move left or right. If you move left, you will be further away from the point on the right, which means you are no longer at the minimum. If you move right, you will be further away from the point on the left, which means you are no longer at the minimum.
So, you just want to find the 2 given points that have k-1 given points between them, and the average of those 2 points will be your answer.
My solution lets find minimal distance using binary search. Suppose the answer is X.
Then, our answer point should be in the distance X for at least k points.
Second part is just easy to check if there is a point where k segment intersect [a_i — X, a_i + X].
Complexity O(n * log^2)
But can be easily implemented in O(n * log)
why are you using binary search? if you already knows the greedy approach to check the answer, you can just do it without guessing the answers ... just get the mininum distance that a X point have the elements. The X with this minimum distance is the answer.
The problem that I don't know the minimum distance, I use binary search to find it.
What is the proof of correctness of C?
Have you solved it? Well, supose X is outside the range we are right now. Then its better to put it inside the range, to decrease the distances of the k consecutives elements. The ans is the min middle point of all ranges with lenght K. (the best point is the middle one because it gives us the least k minimum differences).
Thank You.
^.^
when will tutorial soln for educational contest will come
After the Hacking Phase
how to solve D?
How to solve D?
https://mirror.codeforces.com/blog/entry/67411?#comment-516189
How to solve G?
Let's invent dp0[i][j] and dp1[i][j].
dp0[i][j] is answer for prefix of length i if we divide into j subsegments
dp1[i][j] is answer for prefix of length i if we divide into j subsegments such as maximum on the last segment (ending at j) is a[i].
First, let's learn how to calculate dp1[i][j].
We find such minimal l that maximum on segment [l; i] is a[i]. Then dp1[i][j] = max(dp1[k-1][j-1] + a[i] * (i — k + 1)) for k in [l; i]. We can notice that we are able to recalc it in O(log n) time using sparse table and Li-Chao tree.
How to recalc dp0[i][j]. Let's notice that if we recalc it as max(dp1[k-1][j] + a[k] * (i — k + 1)) for k in [j; i] we will get right answer (we can't make it better than it is, because the if we fix left bound, bigger right bound means not lower maximum value). Notice that it can be recalced using Li-Chao tree in O(log n). Total complexity is O(nk log n)
There is something suspicious in your solution:
the problem asks you to minimize, not maximize answer;
it seems like dp1[i][j] = max(dp0[k-1][j-1] + a[i] * (i — k + 1));
and dp0[i][j] = max(dp1[k][j] + a[k] * (i — k)). And it doesn't work if we change max to min, because here it's can be profittable to cut some a[x] > a[k] where k < x <= i.
P.S.: You wrote your comment "in Russian", so it doesn't show up on the English version of the page.
How to solve G?
D̶&̶C̶ ̶D̶P̶ ̶o̶p̶t̶i̶m̶i̶z̶a̶t̶i̶o̶n̶ I'm actually not sure(there is no editorial for task, so I wrote what i remembered it was), thx for pointing it out
By the way, the problem is not original, statement is only in romanian though
Are you sure that it is D&C DP optimization?
I thought for a while, but it doesn't look like D&C working there. And much more people would solve it in this case.
It looks like Convex hull Trick https://mirror.codeforces.com/contest/1175/submission/55157777
Thanks for pointing out :)
I tried to solve it using D&C DP and got wrong answer on test 4. Any idea why D&C DP doesn't work on this problem?
I have an $$$O(NKlog)$$$ solution for G but still havent been able to implement it until now which ruins my rating as always :)
So we lets denote $$$MAX(L, R)$$$ be the maximum value in the subarray $$$[L, R]$$$, and $$$F(i, j)$$$ as the minimum weight of splitting first $$$i$$$ elements to $$$k$$$ subsegments.
By that, we have $$$F(i, j) = min(F(x, j - 1) + MAX(x, i) * (x - i + 1)))$$$ for every $$$x ≤ i$$$.
Lets have an observation:
We can separate $$$(i - x + 1) * MAX(x, i)$$$ to $$$(i - 1) * MAX(x, i) - x * MAX(x, i)$$$. As always, we will have some data structre like Convex Hull or Lichao Tree to query for the minimum $$$w* MAX(x, i) - x * MAX(x, i) + F(x, j - 1)$$$ for $$$w = i - 1$$$.
Now, normally, one will always think of idea of iterating elements from left to right, maintaining the stack of maximum elements and trying to do something about deleting and pushing elements to that stack. As every time $$$MAX(x, i)$$$ changes, we will need to reset our Convex Hull or Lichao Tree over again.
Lets fix $$$i$$$. Now our stack will represent the changes of the $$$MAX(x, i)$$$ if we iterates $$$x$$$ from $$$i$$$ to the left. And for every fixed $$$k$$$, the elements that satisfy $$$MAX(x, i) = k$$$ lies on a continuous subarray. So my main idea is for each $$$k$$$, i will first find the $$$x$$$ that minimizes $$$-x * k + F(x, j - 1)$$$ before we actually inserting it to our Lichao/Convex Hull.
To do this, you can think of an segment tree which each of its node has a Convex Hull or Lichao tree to take this query. And we will use Convex Hull in this case. If we notice that every time we try to change the $$$MAX$$$ of some subarray by deleting some elements from our stack, their $$$MAX$$$ only gets bigger and bigger. So if we use Convex Hull, we can actually handle queries in $$$O(1)$$$ by using the pointer trick instead of binary searching.
Now once we get the best $$$x$$$ for our $$$k$$$, we will insert a line $$$(k, -x * k + F(x, j - 1))$$$ to our Lichao Tree and take queries later.
But another thing to notice is that if some elements are poped out from our stack, the Lichao tree should also be changed. But luckily, only the top elements are deleted from our stack so its prefix is still the same. Here, we can use a persistent Lichao Tree to handle this case.
So my time complexity is actually $$$O(NKlogC)$$$ for building the segment tree of ConvexHull and $$$O(Nlog)$$$ memory for having a persistent Lichao Tree.
Since this solution is pretty much disgusting, I hope its not author's solution. But i dont want his solution to be $$$O(Nkloglog)$$$ either cause I didn't expect it to pass and spent all my contest thinking of a better (not the one above lol) one.
"...I hope it's not the author's solution..." - Your hope is futile.
On the other hand, I was sure, that there would be much better solutions.
Here's a similar solution but maybe easier to implement.
Denote $$$D_{i, j}$$$ as the minimum cost to split prefix $$$i$$$ to $$$j$$$ subarrays. we fix $$$j$$$ and solve the layer in $$$\mathcal{O}(n \log n)$$$.
We compute the answer for all $$$i$$$ in a D&C fashion; to compute the answer for all $$$l \le i \le r$$$, first recursively solve for $$$[i, m], [m + 1, r]$$$ where $$$m = \frac{l + r}{2}$$$, and then we consider transitions between the two halves.
define $$$A_i = \max(a[m+1...i]), B_i = \max(a[i...m])$$$, the transition is
$$$D_{i, j} = \min_{k \le m} (D_{k, j-1} + (i - k) * \max(B_k, A_i))$$$
Notice that due to monotonicity of $$$A, B$$$, for fixed $$$i$$$ there is a suffix of the first half where $$$A_i$$$ is larger, and a prefix where $$$B_j$$$ is larger. We can solve both cases independently;
$$$D_{i, j} = \min_{k \le m} (D_{k, j-1} + (i - k) * A_i) = \min_{k \le m} (D_{k, j-1} - k * A_i) + i * A_i$$$
We have a linear function inside (for constant $$$k$$$), so we can maintain those in a cht. When we increase $$$i$$$, the suffix in which $$$A_i$$$ dominates increases, and we repeatedly add functions with smaller slopes, so we can do this in $$$\mathcal{O}(n)$$$.
The case when $$$B_k$$$ dominates is almost identical, same analysis.
Here's another boring solution.
As many said, DP formula should be like $$$dp(i, R) = \min(dp(i - 1, L - 1) + (R - L + 1) \cdot \max(a_{L}, a_{L + 1}, \ldots, a_{R}))$$$ $$$(L \leq R)$$$.
Now let's rewrite this formula using $$$a_{M}$$$ $$$(L \leq M \leq R)$$$ as any maximum element in that subarray, and then we can boost the transmitting process of $$$L \to M$$$ and $$$M \to R$$$ separately.
Denote $$$[left(M), right(M)]$$$ as the maximal subarray that contains $$$a_{M}$$$ as its maximum element. For each $$$M$$$, we first calculate $$$f(M) = \min(-(L - 1) \cdot \color{red}{a_M} + dp(i - 1, L - 1))$$$ $$$(left(M) \leq L \leq M)$$$, and then we update $$$dp(i, R)$$$ $$$(M \leq R \leq right(M))$$$ by $$$(a_M \cdot \color{red}{R} + f(M))$$$.
In both parts, we only need to answer the minimum inner product for a query 2D vector (e.g. $$$(a_M, 1)$$$ or $$$(R, 1)$$$) with one vector (e.g. $$$(-L + 1, dp(i - 1, L - 1))$$$ or $$$(a_M, f(M))$$$) selected from a certain set.
To implement easily, we can maintain two segment trees of convex hulls offline. Since we don't need to support insertion and query for segments simultaneously, and we can sort the points in increasing order of the first coordinate, we can solve the problem in $$$\mathcal{O}(n k \log n)$$$.
I don't know how to work without supporting insertion and query for segment simultaneously. For answering $$$f(M)$$$ , we need to know the minimum inner product, it can be solved by working binary search on segment tree with $$$O(log^2n)$$$. And for updating $$$dp(i,R)$$$ , we need to maintain a set by stack and use Li Chao tree with the same complexity. I can't understand how to solve this problem by sorting the point:(
Let's maintain two SegmentTrees, in which each node stores the convex hull of a set of points. By doing insertions and queries offline, we can insert points in increasing order of the first coordinate (which means you only need to append points at the end of each hull) and then resolve query points in increasing order of the first coordinate, which means you only need to calculate the inner product between each query point and the point at the end of each hull (and drop useless points when it's necessary). Note that we avoid any binary search by doing things offline.
The outline is like this:
Here is my submission: 55180395
Oh! I get it! Thank you so much!
It can be solved with ordinary segment tree. With time complexity O(NKlogN). Our dp will dp[k][n], where k is number of groups, and n is representing last added to some group. Now let's focus on solving only one dp layer in terms of group. Update segment tree by setting cost of each index to value of dp[prevgroup][that_index]. Now iterate from left to right, suppose that we are at index i now. Each index will have some cost in segment tree. Now our reccurence will be dp[i] = min dp[j] + cost(j,i). This can be easily found if we can calculate efficiently cost(j,i). Instead of calculating it each time, we will somehow update it efficiently. We can do so by grouping elements by maximum element from them to our i. Now one can see that when moving right, we can find where this element represents maximum. And set it as maximum for new group, while deleting previous groups that those elements belong to. Only thing that is left is that maximum is multiplied by length. We can handle this again by segment tree arithmetic progression update (it can be found easily on net, i am lazy to write about it now). I hope i helped.
It seems like there will be a problem to combine operations "add arithmetic progression to a segment" and "find minimal value on a segment".
why ternary search is not correct for problem C? i am getting WA on test case 2.
Ternary search (to find crest) holds good for a function whose value keeps on decreasing till some point, then keeps on increasing.
Why my this solution for B is failing on test 8 . Solution
your answer bigger than 2^32 so you should puts OVERFLOW!!!
As you can see I am putting it when x > mx .
seems that u need to judge if no>0 when adding to ans
But when no > 0 sum will be ~1e15 so I think there is no need to do it .
By the way I'll see . Thanks for your time .
you missed a few cases while handling your 'no' variable, just made required changes 55178901
Thanks Bro .
What is the hacking penalty and profit for Educational round?
There is no direct addition in score on hacking a problem in Educational Round but it seems quite a good debugging practice
Задача G была на Республиканском олимпиаде Казахстана (ROI) 2018 года), Задача F
А E была на региональном этапе Всероссийской олимпиады школьников:
https://informatics.mccme.ru/mod/statements/view3.php?id=18805&chapterid=113099
Интересно, а почему меня и nkamzabek минусуют, а ILoveDaneliyaTuleshova'a, находящегося прямо снизу, — нет, несмотря на то, что он сказал то же самое...
G была на Республиканской олимпиаде Казахстана problem F
Solution by Tima
Can anyone help what's wrong in this submission for Problem B. 55174319 Thank you!
I think your solve WR, in test:
10 add for 1 add for 4 end for 1 add end add end
The answer is 4 but in your sol is 7
you can refer my solve https://mirror.codeforces.com/contest/1175/submission/55139309
Not good screencast with commentary
What is hacking test case for B)?
Why there are so many hacks in B? Weak Test Cases?
code which loop through vector/stack every time they add the number can cause TLE.
the test case looks like this.
mine got hacked too :)
I saw some of the solutions for F rely on the fact that the answer will not be too large. Does anyone want to give a proof/intuition on that?
Let a valid subarray be $$$a_{l}, a_{l + 1}, \ldots, a_{r}$$$.
Observation 1: Pick up all the elements of value $$$1$$$. For every two adjacent elements $$$1$$$, denoted by $$$a_{x}$$$ and $$$a_{y}$$$, if $$$l \leq x$$$, then it must be held that $$$x \leq r \lt y$$$.
More generally, for every three adjacent elements $$$1$$$, denoted by $$$a_{x}$$$, $$$a_{y}$$$ and $$$a_{z}$$$, $$$x \lt l \leq y$$$ must lead to $$$y \leq r \lt z$$$.
Observation 2: Let's fix the position of value $$$1$$$ as $$$a_{k}$$$ ($$$l \leq k \leq r$$$). Without loss of generality, we assume the position of value $$$(r - l + 1)$$$ is on the right of $$$a_{k}$$$, and then we can conclude the only one possible $$$l$$$ by enumerating $$$r$$$, as we know $$$l = r + 1 - \max(a_{k}, a_{k + 1}, \ldots, a_{r})$$$.
Consequently, there are at most $$$2 n$$$ possible subarrays that we need to check if the elements in each subarray are distinct.
I get it. Thank you so much!
Why this solution of D is wrong? Take the cut $$$[ k, n ]$$$ and find maximum suffix of it, $$$[ l, n ]$$$. Increase answer by the sum on $$$[ l, n ] * k$$$. Then find the maximum suffix of $$$[ k-1, l-1 ]$$$ and so on. In the end, if there some elements in the beggining of the array, which weren't counted in any suffix, also add them to answer. We can do all this with the segment tree in $$$O ( ( n + k ) \log n )$$$.
6 3
-1 -2 -10 4 5 6
I probably did the same mistake as yours.
_____I MADE A DUMB MISTAKE SORRY______
Correct ans is 28.
[-1,-2,-10][4][5,6]
Oh, yeah that makes sense. Thank you!
Can you tell me why it gives WA in test 9? https://mirror.codeforces.com/contest/1175/submission/55166598
Was I the only person who felt B was trouble-some and spent more time on it compared to C and D?
Could someone tell me why I will get WA in T5? Thansk. 55187500
The problem is in this part:
if(tmp*x>=LIMIT){ cnt++; }
what if there is no add inside the loops, but you still increase cnt and print overflow.
But I solve this case like: else if(str=="end"){ if(cnt>0) cnt--;
I think I am so stupid that I will ignore the x of input,if cnt>0 :(
At first, there was a legend related to the name of the problem, but now it's just a formal statement.
Does someone know about that legend?
editorial?
In problem B it was specified "x is an integer variable and can be assigned values from 0 to 2^32−1" so doesn't it means the range of x is [0,2^32-1] and the number 2^32-1 should be included or my English is just bad?
Yes, both 0 and 2^32-1 are included.
My Submission got accepted during the contest 55132811 but after the contest ended the status changed to Compilation error. I checked the same code on custom invocation and it compiled without any errors. What the heck is going on!! Can somebody explain?
Even submitted the same code 55191358 and it got accepted. :/
It will be fixed today.
It hasn't yet. :(
Not till today. :^)
Ok, feels lucky for being expert again :^)
Hello everyone! Answer me please. Why is my solution for C getting TL? What's wrong? https://mirror.codeforces.com/contest/1175/submission/55161342 Please, help)
Help!! Could someone please explain how to solve C what does ar[i+k]-ar[i] even mean;
In my opinion, it's because the first k value will be generated in a[i] ~ a[i + k] intervals.
To answer on task's question you should find the smallest interval which include exactly k points.
My submission: 55152560
Господа, хотелось бы увидеть разбор, хотя бы краткий, по решениям не всё очевидно. Заранее спасибо.
могу объяснить первые 4, про пятую сам бы послушал
Спасибо! Давайте подождём ещё денёк, чтобы лишний раз вас не напрягать. Только что обновили пост победителями, так и до разбора недалеко.
Auto comment: topic has been updated by awoo (previous revision, new revision, compare).
Any hint for F?
(l,r) is a subpermutation iff r = max(l,r) + (l-1) and all values in(l,r) are unique. so we try to find out how many valid l are there for a fixed r, and this can be done by a segment tree with lazy propagation
Can it be solved via BFS? Start bfs at each 1 with state (i,i+1), from (l,r) next state is (l-1,r) if a[l-1] == r-l+1 and (l,r+1) if a[r+1] == r-l+1. Increase answer by 1 for each state reached. Bound is number of permutations, which should be much less than N^2.
I don't think, it can be solved by BFS .
You're right, I missed the statement by a mile.
Can you explain how to find number of valid l for a fixed r using segment tree with lazy propagation
If all values are unique in range (l,r) then r <= (l-1) + max(l,r). Its equal only when (l,r) is a subpermutation. So for a fixed index r, in each l such that l<=r we need to have (l-1)+ max(l,r), and in each node of segment tree we need to store the minimum in that and a count denoting in how many indices that minimum occurs. As you go right and your r changes, the max (l,r) for some l is changing. You can maintain the maximum with the stack technique. And in segment tree you need to handle that with lazy propagation. You can have a look at my code for a better understanding. 55194670
Can someone help me find the problem with my code for problem B ?
Submission: https://mirror.codeforces.com/contest/1175/submission/55197218
The value val should be (1<<32) — 1 instead of just (1<<32) . Read problem statement to sure
Thanks for reply. But, I used '>=' to check for overflow considering that.
Can anyone explain why it is giving wrong answer on test case 8 in problem B? My submission-55198130
Read a bit above . Mb it will help you
I have applied the overflow condition whenever I am adding but still I cannot understand why I am getting wrong answer on test case 8
sarthakoherwal, your code will fail for this test : 4 for 2^32-1 add end add
You have to apply additional overflow check in the else if loop after the line 'x+=checker'
are you checking for
if( x > (int) pow(2,32) - 1 )then cout<<"OVERFLOW" ?where is editorial ??
Why isn't the editorial out yet?
Auto comment: topic has been updated by awoo (previous revision, new revision, compare).
When will tutorials come ?
Actually, I have the same quation(
it has came finally :)