Привет, Codeforces!
В 14.09.2020 17:35 (Московское время) состоится Educational Codeforces Round 95 (рейтинговый для Див. 2).
Продолжается серия образовательных раундов в рамках инициативы Harbour.Space University! Подробности о сотрудничестве Harbour.Space University и Codeforces можно прочитать в посте.
Этот раунд будет рейтинговым для участников с рейтингом менее 2100. Соревнование будет проводиться по немного расширенным правилам ICPC. Штраф за каждую неверную посылку до посылки, являющейся полным решением, равен 10 минутам. После окончания раунда будет период времени длительностью в 12 часов, в течение которого вы можете попробовать взломать абсолютно любое решение (в том числе свое). Причем исходный код будет предоставлен не только для чтения, но и для копирования.
Вам будет предложено 6 или 7 задач на 2 часа. Мы надеемся, что вам они покажутся интересными.
Задачи вместе со мной придумывали и готовили Роман Roms Глазов, Адилбек adedalic Далабаев, Владимир vovuh Петров, Иван BledDest Андросов и Максим Neon Мещеряков. Также большое спасибо Михаилу MikeMirzayanov Мирзаянову за системы Polygon и Codeforces.
Удачи в раунде! Успешных решений!
Поздравляем победителей:
| Место | Участник | Задач решено | Штраф |
|---|---|---|---|
| 1 | dzh_loves_mjy | 7 | 204 |
| 2 | neal | 7 | 231 |
| 3 | WZYYN | 7 | 250 |
| 4 | noimi | 7 | 357 |
| 5 | Um_nik | 7 | 384 |
И, наконец, поздравляем людей, отправивших первое полное решение по задаче:
| Задача | Участник | Штраф |
|---|---|---|
| A | Kirill22 | 0:01 |
| B | dzh_loves_mjy | 0:04 |
| C | SSerxhs | 0:05 |
| D | gleb.astashkin | 0:17 |
| E | Pigbrain | 0:19 |
| F | WZYYN | 0:54 |
| G | OnlyG | 0:16 |
UPD: Из-за проблем с задачами А и B раунд нерейтинговый.
UPD: Разбор опубликован
.
lol the rounds unrated. hope you get it next time tho!
.
even I had 1377 was hoping to go back to specialist ,had even solved two questions real quick but never mind
Ohh, so you managed to solve A?
yeah xD knew my logic was right and when they corrected it I confirmed with given output and submitted
can you explain the logic please?
look at how many sticks there must be, from that you can convert some to coals to have at least $$$k$$$ sticks and $$$k$$$ coals.
$$$\lceil{\frac{k+yk-1}{(x-1)}}\rceil+k$$$ is the answer
t = int(input())for i in range(t):x,y,k = [int(x) for x in input().split()]ans = (k*y) + kcount=0count = m.ceil((ans-1)/(x-1))count += kprint(count)this is the ans i submitted, but i got wa
I had the same issue. I think the ceil function does not work properly for long long numbers.
include<bits/stdc++.h>
using namespace std; int main(){ long long int t; cin>>t; while(t--){ long long int x,y,k,c,d; cin>>x>>y>>k;
} whats the prob wid this code?
When x>(k+y*k), we need to print k+1 as you will exchange one stick for x sticks and k sticks for k coals.
thank you so much. It got accepted
NoobM, shaded I had the same issue. And you are right python's inbuilt ceil function and as a matter of fact square root function does not work properly in case of long long numbers.
So, to solve this issue I found out a solution on stackoverflow. To find the ceil value of division of a by b you can simply do -(a//(-b)) in python and -(a/(-b)) in C++, i did this and got AC.
look you have 0 coals so you will need k steps for k coals.Now as for the sticks you need k sticks to match the coals for conversion into torch.You also need k*y sticks extra so they can be converted into coals later.So, total you need to add (k*y+k-1) sticks extra(since you already have one stick). Now in every trade for sticks you gain x-1 sticks,so, number of steps required is :- (val/(x-1))+min((int)1,(val%(x-1))) where val is (k*y+k-1). So,total no. of steps is (k+(val/(x-1))+min((int)1,(val%(x-1))))
Just curious to know, How they have such a large collections of problems?
they are soon going to make century of educational rounds
.
before: educational so unbearable will again be one math
Now: wow they are doing really interesting rounds of course I will write it
Hope I will get some increase today...
hope i will get billion dollars today
That's so real!
strong pretest, short statement (×)
short pretest, strong statement (√)
reference : https://codeforces.me/blog/entry/80333
A
There has been bad incidents in the past( Long queues, round being unrated, pretests weak/wrong) whenever some author didn't thank Mike. So nobody wants to take the risk you see XD
Truth !
Mike unlinke Mark doesn't sell your data, maintains ad free site, we get quality problems completely free of cost, and without watching any ads like SPOJ. People thank Mike out of gratitude for him.
Wish me luck, please!
Let's go!
Just curious to know, we don't have any problem tester in educational rounds? Or is the same set of people involved in testing the problems?
If only they were less greedy and given free contribution to testers, this round would have been rated
I hope it has strong pretest and interesting problems!
I would like to know which debuging tool are you using? Oh, I suddenly realized that we don't need in cf :D But I still want to hear suggestions
Visual Studio Code is my first choice.
Print Everything
Purple Rain
Hey, this is my first time participating in the educational round and I have a simple question. I quite can't grasp the idea of the time penalty. (I searched up the rules but I still don't get it.)
To the best of my understandings, is it one of the followings? 1) the final score is directly related to time consumed 2) total time of 2 hrs gets shorter by 10 minutes for each wrong submission
Let's say you submitted 2 source code.
Submission 1: got the WA at 00:03
Submission 2: got the AC. at 00:07
Then you get just the same score who got the AC at 00:17.
Thanks :) Have a wonderful day!!
All the best Guys, noob here hope i will make some score today..
I think you are a famous noob as you are getting upvoted by people :)...otherwise lower rating participants always get downvoted here
dont worry i upvoted you ;)
Can I join a contest in codeforces after it has started ??
if u register before 5 min to start — yes
This contest is a nightmare.
so sad that this round will be unrated after all the effort to solve the first few problems
Thank God! It got Unrated.
Problem A made me feel so worthless today.
Back to UnratedForces...
problem A was so irritating before:( now it is good:)
Please let this round rated back :((. Just a small issue from the problem A right ?
Not a small issue for those whose schedule and timing of the contest is completely ruined.
It was obvious that round will be unrated when I saw those wandering trader deals.
Also, 1stick+1coal -> 1torch wtf?
It's minecraft
It's unfortunate that the negativity started in the comment section, in particular this comment has eventually cursed the round and a good problemset. :'(
But i was doing so well :(((((
Out of curiosity how did whatever mistake happened slip through on A? It seems to have been a major error considering that all the samples itself were wrong.
Anyone got it right when the data was not changed?
I made the same mistake and passed all tests when the sample was not changed. Maybe the testers said "Hey, how could there be bugs in A?" and simply let it slip thru.
I submitted within a minute of the change, there were 800 submissions by that point. There were 400-500ish before that.
really wonder how this obvious error can be passed in Polygon...
Yeah, I would expect that there should have been at least a "should TLE" brute force. Moreover how did it pass testing? Did all the testers make the same mistake? Frankly this makes me think that educational rounds don't actually have a testing phase.
literally likely. A previous error make that Problem B can be accepted by almost any way, but nobody noticed that and as a result I got unrated.
Wow, and it gets worse, B's checker today is also wrong.
wish generator is right
I thought for a long time why the test case came out like this.
me too :(
They should explain the sample test case of first question.
New way to make problem A hard to implement.
Damn these unrated rounds. Ruined my first contest.
I feel really sorry for setters. They have make good problemset using a lot of efforts. Contest has been ruined only by A problem.
awoo Were there testers in this round??
and how to become a tester of the round I'm just curious to know.
and thank you for the answer
Does anyone check the correctness of the problems????
Unrated round because of a simple maths problem. Sad for setters and competitors, there should be a tester in edu rounds
This is pretty sad. Even if educational rounds don't have testers (which they should), can't you at least have more than 1 person write model/correct solutions? I know how polygon works and it's not very hard to simply ask someone else to upload another solution and find any mistakes, especially in problem A.
I agree with MagentaCobra
WHY UNRATED? IT WAS THE EDUCATIONAL ROUND IN WHICH I COULD HAVE IMPROVED MY RATINGS. WHY THIS ALWAYS HAPPENS WITH ME.GOD! AM I THAT BAD?
username checked.
Does anyone check the correctness of the problem A??? Bad experience!
Im sad because problems B and C were cool, usually I dislike them, but in this contest they were pretty nice :(
Sorry, looks like its only my problem
DELETED
this is the problem D screenshot from my screen, just notice to word "piles"
also i asked some of my friends and they had same problem
BTW, if you don't have this problem, sorry for unrelated comment
Leaving aside A, other problems are very interesting, do give it a try guys :D
But it is no point for me to stay overnight now... I've refrained from staying up for three days in preparation of this contest
wow, that sounds so inspiring, but don't worry your hard work will pay off in the next contest for sure :D
Damn that was the first time I've solved 2 problems in 20 minutes. But... it's unrated. So sad.
hello everybody. I'm curious to know how to become a tester of the round. if there is a link or description about becoming a tester of the round please leave it under this comment. thank you.
Please don't keep sample tests unexplained even if its problem A.
I think the author could have realized his mistake had he written the explanation of the sample tests once.
Can we please have a div3 at least until saturday?
Can you please explain the test case 3 for problem A,
(
)
Tbh, problem A is pretty easy just like normal A's a simple one line formula for AC, only difference is, they messed up the sample test cases which made it a lot confusing, adding on to that they didn't provide any explanations.
Every other educational round:
me: if I can't solve B I definitely can't solve C.
them: we shall make sure you don't solve B.
me: end up solving just A.
Today:
me: solves A & B in under 20 minutes.
them: unfortunately this round will be unrated.
P.S: I know the frustration is higher for the writers when a round becomes unrated, so feeling sorry for them too.
This also happened to me..
I wrote 2 codes for problem B they gives same output to sample but one of them passes the sample one of them don't but they gives same output for output but when i submit it says wrong on this sample input why?
Before the samples of problem A were fixed, there were already about 1K submissions. I wonder what solution they submitted?
Can I tell it now? I made the same mistake.
None of them did add the other operation and it was more likely that no one added.
Maybe they did so without seeing the sample testcase and worked it on their own... I have seen many coders do that maybe out of competition or confidence
If the jury's mistake was: the statement says you should count both type of operations or at least is ambiguous so it can be interpreted this way, but model solution counts only one of them, then IMO it's a little weird decision to change the tests rather than just make an announcement like: "you should count only operations of type 1, we have updated the statement to make it clear".
It was worse than that as far as I understand
The jury's solution also had a rounding error. So they couldn't just correct the statement the way you suggest
This was the accepted solution at the time of the round
I adjusted my solution to the samples without much thinking when I saw that it does not match the result. Added incorrect rounding and omited the second operation.
I thought "I don't have time to think about it, will figure out why it has to be this way after the contest"
And then I had to return everything back...
Wonder whether author of second model solution did the same
Did a rejudge on B just happen? Some people's Bs got converted from pretests passed to WA on pretest 1.
yeah
What was the mistake though? Mine remained AC so i didn't get what they changed.
A friend of mine (ViciousCoder) misread the question and wrote a solution in which the earliest negative point was minimized, not the latest, so I guess almost anything worked.
Ohh shit. that was bad.
I wonder who that friend is :p
Happy now?
Lmao I was just messing around.
I really should have put a ":P" at the end of the last comment, I wrote that jokingly as well.
problem A likes a nightmare
I am just curious, How is it happen. Is both setter and tester got the same idea for the solution.
Probably I actually got the wrong solution on my first try which matched their test case.
That's crazy level of coincidence
Well the mistake was not counting the 2nd kind of trades so basiclly we output ans-k instead of ans.
Problem A like a nightmare:(
this is what happens when you push code to production without writing unit tests
This contest is really cursed.
When I found the problems easy and solve them fast, the round became unrated. Bad luck for all :(
What a stupid contest !
there should have been testers for the round , as 2 problems had issues in them.
Didn't anyone test this pre-test?
is the round unrated?
yes:(
The contest problems were good enough but only problem was with the checker.Enjoyed problem solving
Waiting for announcement regarding Problem C
Every time I perform little better the contest gets unrated. ;__;
now as the contest is unrated , will there be a hacking phase or we will go strait up to system testing?
Who cares? XD
Every time I perform little better the contest gets unrated. ;__;
BledDest for preparing A & B ? Still remember he writes his checker by casting INT to BOOL.
No, this time I prepared G
Great thanks to you for preparing EDU rounds and wish a better experience next time !
i once solved and got hacked
I think there is a wrong output in Problem B 4th Case:
Your ouput: -4 0 1 6 3
p=[−4,−4,−3,3,6]
k=3 But i have better Solution:
1 0 -4 6 3
p= 1 1 -3 3 6
k=1.
I think we just don't understand what the problem really want , I have the same case as you in my solution
But I got AC on Problem B just ignored their output
Let k be the maximum j (1≤j≤n).. k is not negative value count that is index.. but your solution is also correct max index is also 3 as in the test case !!Ok..Thanks
I didn't read comments . Now I got to know the round is unrated.. __
you even did not get the notification ?? :/
Couldn't even solve one complete question. Need a lot of practice for me. Any good resources and motivation to learn more about competitive coding.
It is OK, go to the problem set sort the problems by difficulty and start practicing with the easier ones, you will be able to solve A problems in a short time
Problems were outstanding. But, A's sample test ruined it :(
not only the sample test , the whole tests.
Very sad to know that the round is unrated after I tried so hard to solve D&E..
Rating is just a number. The problems were interesting and instructive. Thank you all problem setters!
Waiting for the editorial.
Thanks to GOD that the contest was unrated....... The problems are hard and hard to understand.......
For the first time, I solved 4 problems without any WA. sedlyf
What a pity for u that the contest was unrated...
yes bro!
I'm really sorry about the issue with the problem A. This was completely my fault. I re-checked the formula yesterday and discussed it with others and nobody found any mistakes.
1) I didn't round up the result of the division.
2) I forgot about $$$k$$$ trades you need to get coals.
So, my solution was completely incorrect. I will not blame anyone else because this was my problem and I failed its preparation. I didn't want this round to be unrated and this issue right at the start of the contest just completely ruined me. Sorry guys.
its ok, human are not perfect
Or are they?
aw man
Mistakes happen. You are a great problem setter. I've always liked your problems <3
It is OK man, it is kind of encouraging for us beginners to see that even strong coders sometimes make mistakes in problem A ;-)
wouldn't it be nice idea to extend the time of round by 10 more minutes instead of making it as unrated, because the problems are extremely good , feeling sad for this round becoming unrated
Sadly, if the first problem is wrong, it affects almost anyone. And also this was not the only issue because the checker of the problem B was incorrect. Cursed round. Really cursed.
Well mistakes do happen, but the problem itself was good.Just curious how did it slip away from testers?
This is a pretty bad mistake, but you handled it pretty well during the competition and now by admitting to it. I'm surprised that nobody noticed the issue, did anyone actually solve the problem (in code) other than you?
One person solved it before the contest. Sadly, he just tried to find the formula which passes the example. This is fun and sad at the same time.
Well don't you think it's a good idea to have multiple testers on every problem regardless of its difficulty? If testing status were always like this, this situation were bound to happen.
There are reasons Educational Rounds are pretty rarely tested and these reasons almost don't belong to me. Moreover, I'm pretty rare guest in Educational Rounds now because I'm mostly busy with Div.3.
That's kinda sad to hear. One might expect sponsored rounds to be more prepared than the regular ones but it sounds like it's not the case.
But i am surprised to see about 700 people solve the problem before correction. Looking at this i thought i might got something wrong.
No rated contest should have problems that are not stress-tested with a naive slow solution.
But yeah, shit happens.
Problem D — For input [1,3], we move 1 to 2 and 3 to 2. This makes both of them together.
Kindly correct me, if I got it wrong !!
Can anyone explain the test case [1,2,4,8,9,100].
How are we moving the piles to make them together?
for
[1,3]you just keep each one in its place. The problem says to put all of them in at most 2 piles, not necessarily 1.For input [1,3] the answer is 0, you can leave them at their original positions because you need at most two piles
For case [1,2,4,8,9,100], you move all the piles except the one at 100 to position 4, which takes 8 moves
It seems C was like 1400 and D 2000
Still, sad that it is unrated
D was simple with set and multiset. It is
O(q*log(n))I wonder if my solution is overcomplicated or I just suck in c++. I couldn't come up with a solution with datastructures available in python and had to implement it in c++
use
Please
In the end my estimate was nearly perfect and off by 100
Though it maybe affected by the fact that the round ended up unrated
The problems were really interesting, so unfortunate it became unrated, just curious, how the problem A thing happen? all samples were wrong.
Will this round be unrated?
I admit it is fair to unrate the contest because of the issue of problem A but I still feel unhappy because I get a pretty good result.
Anyway, thanks to the problem setters. Bad things happen all the time. Do not worry about it too much.
Man, Can't catch a break.
I do feel bad for Problem Setters though. The problems were definitely good.
Your Graph does not justify this, but Ya, lol
I bet 10 bucks and say if the contest was rated and had no problems, this 46 would be more than 4600.
I'm not denying this. Not at all. Just wanted to post this. It is not meant to be taken seriously.
Best channel for video editorials of this round and all other rounds :- https://www.youtube.com/watch?v=Q76hY9VMHdI
Also , codeforces shouldnt do this to programmers . They should check their programs before the round .
awoo I know this doesn't come under rules but is it possible for you guys to discard the hacking phase as the round is unrated it won't affect much and we don't have to wait for the editorials.
They could post the editorials if they want to, it does not depend on the hacking phase.
Honestly, did not liked the problems much. A, B, C where long and fairly unclear statements. D was long, too, but at least clear.
E, F, G might be to hard, I assume less than 20 rated participants would have solved any of them.
Just noticed that I missunderstood D, it is not that we can move at all positions x, we can move all objects at one position x. So this is is shitty misunderstandable statement, too.
Did D have some elegant implementation? There was too much case work in my solution.
92816134 This is most probably what u wish I guess
where did we receive notification regarding making round non rated?
Can anyone explain how to solve G because the question was pretty straightforward ??
How to solve F and G?
F: Fix $$$d = gcd(x_1, x_2)$$$ where $$$x_2$$$ is yet to be determined, also the condition $$$l \le x_1y_1 \le r$$$ gives some bounds $$$L \le y_1 \le R$$$.
If $$$x_1 = dk$$$, $$$x_2 = ds$$$ then we need $$$s \mid y_1$$$ and $$$k < s \le \frac{n}{d}$$$. We have two cases:
If $$$x_1 \le \frac{n}{2}$$$, then consider $$$x_2 = 2x_1$$$. If $$$y_1$$$ has at least two possible values then at least one is even and we win. (Choose $$$x_1, y, 2x_1, y/2$$$). Otherwise, there's only one possible $$$y_1$$$, and it's easy to check if it works.
If $$$x_1 > \frac{n}{2}$$$, then $$$R \le 2m$$$. Keep a BIT over $$$a[i] = \text{ number of multiples of } i \text{ in } [L, R]$$$, you can keep this updated by doing a total of $$$O(m \log m)$$$ updates, and you can find possible choices for $$$s$$$ by querying the interval $$$[k + 1, n / d]$$$. There's a total of $$$O(n \log n)$$$ choices for $$$d$$$ (counting over all possible values of $$$x_1$$$), so there's also this many queries. This gives a $$$\log^2$$$ solution.
My solution to problem G, AC after 8 minutes of the contest :(
Let's iterate over all R from left to right, and count how many L such that the subarray [L..R] is good for each fixed R.
When we are now on a fixed R, we need to know for each number X, what is the range of valid Ls such that the frequency of X in range [L .. R] is 3.
We can easily do that by storing the indices of number X in a vector V, let's say that the vector size is K, so the valid range of Ls for this X is [V[K-4]+1, v[k-3]], we will use a lazy segment tree to increase / decrease this range each time we see X.
Let's form an array called can[i], can[i] equals how many distinct numbers in range [i .. R] having frequency equals 3.
Now our task becomes, for each R, count how many Ls, such that can[L] equals to the number of distinct integers in range [L .. R]. Let's say that distinct[i] = number of distinct integers in range [i..R]. We can easily update distinct[i] while we are iterating over R, when we find a number X we just need to increase distinct[j] by one, such that lastPostition[X] + 1 <= j <= i. We can do that using the same lazy segment tree.
So we need to count how many (can[i] — distinct[i] == 0). Since (can[i] <= distinct[i]), then (can[i] — distinct[i] <= 0), so we just need to know what is the max number in the lazy segment tree, and if it was 0, we will add the frequency of the max to the answer. So we just need to support querying the max number and its frequency in the segment tree.
My code: 92841078
Can anyone explain the solution of C?
There is two cases.
1) The first character is 1, then friend have to use the skip(obviously).
2) There is substring "111". For any other case we can avoid using the skip
I first tried to implement greedy, but was not able to make it work :/
Look at my submission: 92819400
I used a dp.
dp[i][pl][isSecond] is min number of skip points to kill ith boss by player pl with isSecondsth move.
92828592
I used greedy: For every turn, if its the friend's turn, kill the current boss and see if the next boss is easy, then kill it as well. If its your turn, then kill the current boss and see if the next boss is difficult, then kill it as well.
My solution
sh_maestro I did the same but got WA on test 2.
... my code
funny, same error as mine ;)
"wrong answer 55th numbers differ — expected: '0', found: '1'"
If you figure out that test case , please tell . I am also getting wrong on same test case.
Most probably 55th Test of 2nd test case is-
5
0 0 0 1 1
Thanks!
hey, I also found a similar test case during contest when my similar greedy solution failed on tc-2, but I want to ask that how can we prove the greedy solution wrong by using some mathematical argument or Is finding a counter-example is the only way? as sometime it may be hard to find a counter-example and also takes a lot of time.
Greedy solution does work, though it uses a little bit of coming back a step
greedy solution with insights
Check the link solution
umm thanks I got it know it's kinda some new insight.
In the code by sh_maestro, he is skipping the case when it is your turn and a[i]==0 then he is skipping the boss.
I don't understand why does it lead to correct answer?
Reference to other comment
I guess the only difference is that I don't kill a boss every turn (I leave the easy bosses for the friend) — since either of us has to kill 1 or 2 bosses every turn. But if there's a hard boss, I always kill him (and the subsequent one — should that be a hard boss as well).
I tried to implement exactly that, but got WA. Can you see where I did wrong? 92817183 thanks
The problem statement is a bit vague and there is room for error — after reading your solution, I re-read it and can see why someone would go with that approach.
The key difference is that it is not essential for both you and your friend to kill a boss in your turns. So my solution was something like this:
Sorry, I still do not see the difference.
The friend uses his second hit if current boss is 0, I use my second hit if the current boss is 1. Where differs your solution from this?
I did understand that this logic fails for
0 0 0 1 1"During one session, either you or your friend can kill one or two bosses" — sounds like either my friend or I (or both) have to kill 1 or 2 bosses each round. Though the lines that follow imply that both of us have to alternate and have to kill 1 or 2 bosses in our turn.
If the statement implies that its mandatory to kill a boss in each turn (as opposed to kill 1-2 bosses in either my friend or my turn), then my solution is wrong (and yours and the other solutions shared here who got WA are correct). The problem writer would need to clarify what the intent was.
I think I just got why your solution works.
The key realization is when you are skipping, you can actually imagine that as transferring the previous job to me(basically take it away from friend). Then it, doesn't matter whether it was a 1 or 0. It will not affect the answer. The special case is when there is a 0 at the second position. This time you cannot take the previous job, so we imagine that our friend finished the first two bosses. If in the third position, we have a one, "I" will take care and if it is a zero, then we again imagine a redistribution of work in which first job was done by our friend, second one by me and third one by friend again. This way, the solution always yield the optimal answer.
That's an interesting insight! One thing to think about is what happens when this renegotiation ripples to the beginning (i.e. after the negotiation, the first boss needs to be killed by me, however the solution requires the first boss to be always killed by the friend).
We will not have the ripple back effect because we are always alternating turns and each player can at max handle 2 jobs. When you get a 0 in second place, the friend will take care of it, if we get one more 0, we redistribute as follows:-
First(it may be 0 or 1) one is done by friend, second by me and third one by friend again.
If you have any counterexamples in mind, please share them?
Not a counterexample, but how would we explain this for 1 0 0 1 1? I.e. what does the friend take first, then us, etc.
Okay, so the working will be as follows:-
First our friend finishes the first two bosses "1 0".
When we see a "0", we exchange the last boss finished, i.e. "1" one done by friend, the next "0" is done by me and the third "0" is done by friend.
This way, in the next turn we get to finish the next two hard bosses "1 1" and we are done.
I wrote a code for this idea with comments:-link to submission.
Did I explain your question?
Amazing realization, thank you for that, it really did help understand the greedy approach:)
As far as I understood the problem, it's mandatory to kill at least one boss in any session (friend's turn or my turn). How can you skip "my" turn?
In the code you have provided in the link, if its my turn and the a[i]==0 then, you have skipped the testcase. I can't understand that part.
I think that's because you would like to (greedily) give the 0 values to your friend , to reduce the count. If you yourself use that value 0 ,then next values may be like 1,1 and friend will need 1 more skip in that case.
What about this line: During one session, either you or your friend can kill one or two bosses (neither you nor your friend can skip the session, so the minimum number of bosses killed during one session is at least one). After your friend session, your session begins....?
I am not sure about his code , but i surely didn't skip anyone's chance. my submission
I think your solution is correct but explanation is slightly wrong bro, Consider the given case : 1 0 0 1 1
optimal moves -> Friend, Me, Friend, Me, Me
but according to your explanation your friend will see that second boss is easy and therefore he will kill it and that will result in not being an optimal choice, isn't it?
The way it works right now would be something like ("F" = Friend, "M" = Me) :
In the above example, on the third boss, I see an easy boss and would skip it (so the friend can kill it)
Some more examples:
In the last example, I can only kill 2 bosses at most, so my friend is forced to use a skip point at boss number 6.
You have to find islands of 1 starting from index 1 and 2 ,then divide it by 3 my soln
I couldn't solve a single problem. I hope editorial will help me.
ok, what I've found out from the round.
I should not have divided doubles
I should have read the tasks very carefully (super carefully, extremely carefully).
Looks like there were no testers for this round.
Oh my god, 2 questions with minecraft references, who made those questions dude???
Can someone please help me out to find flaw in my logic for question D?
-> At the end for each query we are just interested in dividing the array(sorted array) into two subarrays.
-> Answer would be diff (max element and min element of first subarray) + diff(max element and min element of second subarray).
-> Also dividing subarray would be optimal when we divide around mid value(max element + mid element)/2
Attached my solution(not sure why its failing on test case 3)92839897
It would be great if someone can please provide a counter example so that I can figure out why my algo is incorrect.
Thanks In Advance.
1
4
1 1 100 1000000
Sorry man, I am not able to understand your test case. What I understood from question, all the pi will be different and in above test case there are two ones.
Try 1,3,4,5,6; optimal division point is at 2
What is the expected correct answer? I can see my solution gives answer as 3. Is that incorrect?
The answer is end value — starting value — (maximum distance between any two consecutive elements after sorting ofcourse)
I see, thanks.
I made the same mistake :) That is optimal for the 2 sides separately but not combined. Eg: 1, 20, 40, 60, 100. Optimal for 60 to go left.
It was kind of easy to think, but my bad I was just trying to correct my above solution by thinking counter example. I would have thought for a different approach.
Can anyone hint me on E?
$$$O(n*m)$$$ is trivial if you know about linearity of expectation. To optimize it observe that for a fixed shield all $$$d_i$$$ smaller than $$$b_j$$$ have same contribution(number of ways such that we can $$$d_i$$$ damage to $$$j'th$$$ shield) and all $$$d_i$$$ greater than or equal to $$$b_j$$$ have same contribution. Do some counting and prefix sum and binary search and that's it.
I can form the expression. Evaluating it takes O(n) for each sample can't see of a way to optimise it further. Would be great if you could check this out —
If (count of no of d(j) >= b(i)) <= a[i](Let this be a for the moment) then the answer is zero. Else from linearity of expectation the total damage can be expressed as D = D[1] + D[2].... + D[n]. Clearly E[D[k]] = 0 for k <= a. For any other k > a it remains to evaluate E[D[k]], which can be obtained by using the definition of Expectation and the associated probabilities can be obtained using combinatorical arguments.(Does there exist a smarter way of doing this, without explicit counting?)
can greedy approach work for C ?
No. Dp solution works
I am not able to see any case where my greedy solution will fail. It is wrong on some 55th case in tc 2.
Yes, just prevent consecutive 3 ones. Check separately for first element.
can you elaborate a bit on how you come up with the greedy solution and also some arguments why your greedy solution work.
after some starting series on one's both players can play optimally to chose their places accordingly that if k consecutive 1s are there then at max only k/3 ones will be handled by friend player due to the fact that since they have the choice to play optimally they can always chose who is going to start this segment of 1s either first player or his friend player. now lets say we start with player who have no bias for 0 ,1 then he will try covering as much as possible he covered 2 ones from k. after this the friend player covers another one. then remaining sequence contains k-3 ones. this happens continuously until k is emptied!. Just handle starting and ending points separately for each segment as they decide optimal choice for next move!.
Prove that after firs position they can decide any position that they want to pick. lets say in order to come at position i x1 moves included only 1 movement to right and again lets say x2 moves included 2 step movements. then as __gcd(1,2)=1. thus x1*1+x2*2 can take any possible value thus it is always available with us to chose positions in the most optimal manner and minimise the skip points hence we can solve it greedily!
Have a look at my simple solution!
92891977
Yes We can!
Can someone explain the solution of E?
By linearity of expectation the answer for a fixed shield is the sum of probabilities that monster deals damage times the monster's damage.
1) Monster deals damage if more than $$$a_i$$$ monsters with damage bigger than or equal to $$$b_i$$$ come before it.
2) Fix set of all monsters with $$$d_j \ge b_i$$$ and add the current monster to it if it's not already present. Let the size of this set be $$$N$$$.
3) Then the probability we search is just the probability that in the fixed -- during the step $$$2$$$ -- set the current monster comes at least ($$$a_i + 1$$$)-th. We don't care about other monsters, that is, we look only at relative positions of a fixed set
4) Probability that monster comes at any position is 1/N, so the probability $$$P(pos \gt a_i) = \frac{N - a_{i}}{N}$$$.
5) $$$O(nm)$$$ solution is as follows: calculate $$$d_j P(pos \gt a_i)$$$ for each monster $$$j$$$ and each shield $$$i$$$.
6) it can be optimized using binary search and prefix sums.
Hints for G, please?
hashing
What's the logic behind problem D ?
u need to find
max(a[i]) - min(a[i]) - max(a[i]-a[i-1])in each query.Can someone explain the statement of Problem B, What does it mean that find the minimum k where k is the maximum j where p[j]<0 ??
last value of index j in the array such that p[j]<0, which is denoted as k , should me minimum. Like: supoose we have n=4 a[]={2,-3,4,-1} l[]={0,0,1,0} so the corresponding sum prefix array will be sum[]={2,-1,3,2}, here max j such that p[j]<0 is j=1 , so k=1. new array such that the condtions are satisfied will be a[]={2,-1,4,-3} Here , sum[]={2,1,5,2} , here max j such that p[j]<0 , is that it does not exist .Accoridng to question , in such cases k=0.So, here answer is k=0 , not k=1 and requires array after rearrangment is a[]={2,-1,4,-3}. I hope this helps and clarifes ur doubt.
Auto comment: topic has been updated by awoo (previous revision, new revision, compare).
Quick observations for D:
The problem is equivalent to solving the following problem
with updates to A. Unfortunately this is somewhat hard since the optimal assignment of points to segments can change a lot after every update. Fortunately the following problem is much simpler
since updates to A changes the set of gaps by a small amount. The answer to the original problem is
max(A) - min(A) - (largest gap between two adjacent elements of A)I am not getting the intuition. Can you elaborate why it works?
I guess he missed that we need to sort the coordiantes first!
First sort the coordinates. If we could keep only 1 coordinate(containing all the piles) in the end, the answer will be
p[n]-p[1]. But here we can keep 2. So basically we need to select a prefix arrayp[1..l],which denotes our first group andp[l+1..n]the second group, such thatp[l]-p[1] + p[n]-p[l+1]is least. Herep[n] & p[1]are always same, the remainingp[l]-p[l+1]is difference between adjacent elements.editorial by tourist.
thanks but this is editorial for problem D :D
take a look at his submissions for other problems.
Sorry to ask but I couldn't find tourist on the leaderboard
thank you so much! too bad I can only give one upvote
Дно пробито, можно закрывать эдьюкейшнлы
Can someone please help me figure out why this solution for D is resulting in a TLE. Thanks a lot in advance.
Found it: Thanks a lot for the help.
Kindly someone explain me the greedy solution to C
The quality and accuracy of problems should be taken more seriously than how funny the legends are.
Moral of this contest- always think a dp, before you do a greedy, and see if it works with the constraints. Greed is not good.
It is the opposite. Always consider the simpler solution first.
Would you suggest to go for a greedy solution first although it's not sure to work? Problem C for example. Would you do greedy or dp?
Dp is sure to give the correct answer whereas greedy might fail.
1) Well, of course you shouldn't code greedy if it doesn't work, but it makes sense to consider it first
2) I solved C with greedy...
Actually, many have a "confusion" about dp and greedy problems. Some find it difficult to distinguish between dp and greedy problems or judge the way solution would work.
Is there something that could help us predict that a problem is to be solved using dp or geedy? Although many times, we can FEEL it, but we can't express it in words why it's a dp or greedy.
I think one should go for dp. DP solution is simpler than the greedy one because its difficult to prove the greed.
Proof for greedy Ya proof was difficult!
Don't trust this guy
I have solved C using DP, can someone provide me the logic for the greedy solution.
Let the friend kill the first boss(and second if it's easy), number of skips will be updated accordingly. Now it's your turn to kill. For every island of 1's (groups of consecutive 1's) the number of skips the friend will need are SizeOfIsland/3 as for every 3 consecutive 1's the friend has to skip at least 1 of them. Let's take an example, input = 10111011111, your friend kills bosses at index (0,1,4,5,8).Two of these were easy so total number of skips = 3 (He will never kill two hard bosses in one turn, it's always better to kill one and end his turn). Take other cases and see that it works. Have a look at my submission. 92823703
Why Unrated！！！We can just extend the length of the contest
Hey,bros,why down vote . I just express mine and many guys'
Please give a test-case where this greedy approach fails for Problem-C. Sol. Link — https://codeforces.me/contest/1418/submission/92829566
Third problem was really a must do for someone struggling with dp.
Sol. Link for Problem-C — https://codeforces.me/contest/1418/submission/92829566 In this Solution's test details , it is written that it fails on 55th I/P but 55th I/P is not showing. Please provide a test-case where this greedy solution fails.
I also wrote a DP Solution - https://codeforces.me/contest/1418/submission/92873324 It got acceepted but greedy one is giving WA. Please provide test case where that greedy one fails.
Is it working with
0 0 0 1 1?
Answer should be 0
Ya Got it Thanks :)
Third problem was really a must do for someone struggling with dp.
if that's the case I'm surely doing that ;)
Nice set of questions . No worries, we are eagerly waiting for the upcoming educational rounds . Cheers to your hard work ...
[Deleted]
If you look at the top it says "recent actions". This includes new comments/blog revisions as well.
It's public outcry, I think
[deleted]
It is very sad that after great effort these problems were invented and prepared by inventors, the result is:
I hope in the future there will be testers for Educational Codeforces Round!
As a compensation can you give me the contact number of the trader which gives me 10^9 stick in exchange of 1 stick.
A contest announcement with most downvote ?Hi awoo , is there any possibility that you post the editorial? I actually liked the problems and I'd love to learn more from the problems.
Thanks
You can find an unofficial editorial here.
Thank you!
Every contest should be rated. As situation is same to every contestant.
Auto comment: topic has been updated by awoo (previous revision, new revision, compare).
Автокомментарий: текст был обновлен пользователем awoo (предыдущая версия, новая версия, сравнить).
Anyway, your problems are very good, cheers!
Why too much down vote ? Actually, This is not good at all. Take the issue as simple. you should be thankful for testers and setters.
Why too much down vote ? Take the issue as simple. You should be thankful for the testers and setters.
It was always interesting for me, why people downvote announcements of unrated contests? People gave you some tasks, contest was unrated but why they should have negative contribution because you are angry?
Everyone wants to have contest often, but you should accept the risk of unrated contest and react normally, not just pressing downvote button.
imagine getting free interesting practice problems and get mad about it because they don't give you some internet point.
It's not like there is shortage of practice problems on the internet and on codeforces in particular.
People who registered for the contest obviously wanted, you know, a contest. And this part was ruined. Moreover it was not ruined because of something unpredictable like a sudden outage of servers, but because of terrible organization. If this contest doesn't deserve downvotes, then I don't know which one does.
imagine thinking a contest is a ruin because it doesn't give you some internet point
But surely the one who made the questions doesn't deserve downvotes does he
Well, it may be not their fault, but people evaluate the contest as a whole, not the tasks.
btw, whose alt account is top 1?
Mistakes happen.No need to feel sorry, the problems were really interesting. :)
Sorry, I'm new. When the round is unrated it means that the contest doesn't count in your personal rating?
Yes
Solution to Problem C Mortal Combat Tower in youtube video.
Trash problem is really trash.
Can anyone explain how 5 is coming as the output of this 1 2 6 8 10?
they will choose the points 2 and 6
10, 8 and 6 will go to 6 and this will cost 4 moves, 1 and 2 will go to 2 and this will cost 1 move
the total moves = 5
btw this's one of the best problems I ever seen and it's very helpful
We have to find min. number of moves.
So i'll move 6 to 8, cost=1.(moving x to x+1 will result in 1 move) moving 10 to 8, cost=1.(moving x to x-1) moving 1 to 2, cost=1.(moving x to x+1)
overall cost should be 3. WHY 5?
Please tell me that you're joking, did you even know that 1+1 = 2 ?
Moving 6 to 8 needs 2 moves, 10 to 8 also 2 moves, finally 1 to 2 needs 1 move.
The total moves = 5 !!!