Привет, Codeforces!
В Nov/12/2018 17:35 (Moscow time) состоится Educational Codeforces Round 54 (Rated for Div. 2).
Продолжается серия образовательных раундов в рамках инициативы Harbour.Space University! Подробности о сотрудничестве Harbour.Space University и Codeforces можно прочитать в посте.
Этот раунд будет рейтинговым для участников с рейтингом менее 2100. Соревнование будет проводиться по немного расширенным правилам ACM ICPC. Штраф за каждую неверную посылку до посылки, являющейся полным решением, равен 10 минутам. После окончания раунда будет период времени длительностью в 12 часов, в течение которого вы можете попробовать взломать абсолютно любое решение (в том числе свое). Причем исходный код будет предоставлен не только для чтения, но и для копирования.
Вам будет предложено 7 задач на 2 часа. Мы надеемся, что вам они покажутся интересными.
Задачи вместе со мной придумывали и готовили Роман Roms Глазов, Адилбек adedalic Далабаев, Владимир vovuh Петров и Иван BledDest Андросов.
Удачи в раунде! Успешных решений!
Поздравляем победителей:
| Место | Участник | Задач решено | Штраф |
|---|---|---|---|
| 1 | Anadi | 7 | 266 |
| 2 | HIR180 | 6 | 129 |
| 3 | mrscherry | 6 | 152 |
| 4 | Vergara | 6 | 158 |
| 5 | Jeel_Vaishnav | 6 | 185 |
Поздравляем лучших взломщиков:
| Место | Участник | Число взломов |
|---|---|---|
| 1 | teapotd | 100:-4 |
| 2 | vlad.raw | 52:-5 |
| 3 | MarcosK | 32 |
| 4 | tataky | 28:-5 |
| 5 | knotValid | 23 |
И, наконец, поздравляем людей, отправивших первое полное решение по задаче:
| Задача | Участник | Штраф |
|---|---|---|
| A | Dalgerok | 0:01 |
| B | Nazikk | 0:03 |
| C | neal | 0:03 |
| D | tamref | 0:14 |
| E | shadowatyy | 0:13 |
| F | killer_god | 0:34 |
| G | lxrvelory | 1:03 |
UPD: В задаче D обнаружена серьёзная ошибка, из-за которой некоторые некорректные решения могут приниматься как корректные. Мы исследуем количество пользователей, чьи решения были оценены неправильно, и работаем над исправлением чекера. Приносим извинения за эту ошибку. Решение о рейтинговости раунда будет опубликовано позже.
UPD2: После обсуждения проблемы мы пришли к следующему решению:
Те, кто сначала получил AC, а потом WA, не подвергнутся изменению рейтинга. Для всех остальных (те, кто получили правильный вердикт) контест будет рейтинговым.
UPD3: Разбор опубликован
2 hours for 7 problems seem to be too less. Any chance extending the time to 2.30 hours? Specially for Educational Round, which should focus on having participants with low-mid ratings attempt more problems. C'mon beloved Codeforces! Give a thought.. :)
"Specially for Educational Round, which should focus on having participants with low-mid ratings attempt more problems".
Not really that's what Div. 3 rounds are for.
Div3 rounds (both frequency and problem difficulty level) are inconsistent, Edu Rounds are still the best way to get introduced with ideas that can be used in broader extent.
Most of the div2 people solve at most 5 of them anyway. Having 2h for 7 problems is good enough, since it gives a challenge for the better contestants too
I'm saying just for education rounds though, the idea is to Educate, so why not give an extra half an hour?! That will surely benefit lots of programmers like me who are not yet to the level but trying to attempt and solve more problems than they usually do. There're lots of other div2 rounds where better contestants can be challenged by 2 hours time limit.
Pretty sure the meaning of "Educational" rounds was lost a long time ago.
Back when they started, educational rounds had classic problems which highlighted ideas and techniques that contestans should learn.
Nowadays they are just normal contests with different rules ¯\_(ツ)_/¯
Maybe they ran out of ideas and techniques that new contestants should learn...
that's a good idea but maybe 2 hours make us want to try faster .. for me at my best I would solve 3 problems in less than 2 hours so it won't make that difference but it could for others so I agree with you
Hoping to get some plus ratings in this round :p
well... not anymore :/
Раунды awoo и команды — единственное, что может скрасить серый понедельник, спасибо
upd. топ-10 пранков, вышедших из под контроля
Но не этот(
Lower, or lower and equal to 2100?
educational round == div2 round sponsored by harbour space
True
If your rating is equal to 2100 then your rating will not change no matter what.
Hi, guys, is it rated for me too?
I am participating after a long time and I have heard that some changes have been done in the divisions — div1,2 and 3. What are the rating ranges in these divisions and will my rating be affected if I participate in this contest? Thank you.
You rating will change
okay. Thanks
An Educational round after several bad contests, time to get new high rating.
69 ( ͡° ͜ʖ ͡°)
what is test 5 on E???????????????????
Why can't we see the test cases?
wait are we allowed to discuss
Why in E d can be>n?
it doesn't matter. you can just take d=min(d,n).
There was an error in problem D which caused some incorrect solutions to get accepted. We will investigate the number of users who were affected by this issue and decide whether the round is rated.
I am really sorry :( Both bugs (in D and G) were mine.
<3
Why not consider it as a part of the hacking since Accepted here is not a final verdict because there is testing after hacking phase is finished
Just imagine the number of people who attempted to other problems after submiting a wrong solution to problem D and its affection to the rankings...
The tests aren't exhaustive, and Accepted doesn't necessarily mean your solution is correct.
<3
Isn't that the whole point of having hacking-phase or system tests?
You are poset
Please don't unrated. Please. :(
Please turn on hacking phase to hack solutions with cout << 0 (to investigate the number of users who REALLY affected by this issue) and then run system tests.
Such a noob
Please don't be unrated
TOM TOM TOM
i submit code for problem D with just cout << 0 << endl; and get AC but good vertices in my code ans simple test 1 are different why??
NO!!! Plz be rated!!!! It's my first time to be MASTER!!! :(
I was gonna be an expert too:(
Poor you, bro. I hope this contest could be rated.
How was your result today?
After seeing that "cout << 0" passed all tests in D, it is really unnecessary to consider it should be rated or not:(
The system is judging at the moment. :)
I hope it's rated too.
I agree
The same thing man, I can be expert for the first time in my whole life after 2 years of work, if this round will be rated, please let it be so.
Please don't unrate this contest.
Could we rejudge problem D or some accepted incorrect solutions?
I don't think so...
I myself didn't solve D, but there might be some guys with little bugs, who would have solved this problem after getting WA.
How does correct checker guarantee that you will get WA for the little bug? The little bug is the most common reason for hacking
It mustn't be that little you're thinking...
Not everyone solve problem D in on try. But getting AC in pretest means don't working on it anymore.
And the pretests was really weak, the guy posted above (alireza_kaviani) got AC with outputing only 0.
Spoiler Alert:
In D, is it true to:
1- Find MST.
2- If n - 1 < = k then we have reached the answer, otherwise, erase edges starting from leaves until the number of remaining edges equals k.
I think it needs to be tree that grants minimum distances from the node 1 (like, dijkstra-tree)
You're right. Dijkstra tree with the root at 1. Not MST.
Thank you! I had forgot what MST represents, but have just remembered.
Shouldn't it be shortest path tree rather than MST?
Apply Dijkstra from source 1. Get tree with n-1 edges. Start removing leaves edges from that tree. Too bad I had a small bug in Dijkstra and could not submit on time.
@MatPhySC what if # of edges in optimal paths is greather than K, dijkstra tree should answer less edges than the solution
If I understood your question correctly than if K >= N-1 then answer will be Dijkstra tree because all vertices are good
Sorry, poor english, but what i mean is that even when all vertices in Dijkstra tree are good, there could be another ones that belong to some other Dijkstra tree and they are also good edges
consider this case: 3 3 3 1 2 2 1 3 1 2 3 1
if i understood your solution, it should give 2 1 2
however, 3rd edge is also good, at least the way i get the problem
UD: i got it now, it's good vertices, not good edges
There are two Dijkstra tree. You can consider any of them.
Wrong solution:
Consider the following case - 3 3 2 1 2 2 2 3 2 1 3 3
Answer is — 2 1 3
Answer from MST - 2 1 2
Minimum distance from 1 to 3 is 3 units. MST gives 4 units distance from 1 to 3, so 3 is no more a good vertex.
This will fail. Consider this tree. 1 2 1 1 3 1 1 4 1 2 4 1 There are multiple MST. But taking any MST other then 1,2,3rd edges. Will give WA.
MST does not guarantee that all edges are at the minimum distance from vertex 1.
Thank you all!.
Beautiful problem BTW :D
I don't think MST works. I got AC on this problem with SPT(shortest path tree). and maximum number of good vertices is min(n-1, k).
What is test 3 in D?
First time I wrote a buggy segment tree. :(
It means you get an Accepted for Problem E, don't you?
Could I see your solution?
Yep. It was accepted after the contest was over. In the last minute, I realized my mistake.
My Soln.
Thanks, bro. Hope you high rating :)
when I wondering how this guy passed D in 31 ms
lol, lmao
I bet a lot of contestant will fail on D :|
It seems like the checker was wrong, because the code is clearly wrong for even the sample cases.
This solution doesn't even take the input.
It's not necessary to take the input. See this blog.
Thanks got it :)
It's not necessary to take input in any of the problems.
I am sorry to be saying this but in my opinion it would be extremely unfair to declare this round as unrated because there would be many people who might not have done 'D' and have performed well in today's contest. If some incorrect solutions were accepted then it may as well be considered as a case of weak test cases. I urge you to consider the plight of many like me who believed they did well in today's contest and would be stranded disappointed if it is made unrated. PS Edit1: To all those who down voted this I am sorry to have hurt your feelings. I do respect your opinion and I totally accept that either of the scenarios I suggested would have been unfair. But the final decision taken by the contest makers is fair in everyone's eyes and no one loses out so I believe it is for the best.
feel about those coders who cannot improve his D solution to get actual AC solution. because of he/she already get AC.
I can understand that but that's also the case in many contests when your pretests get passed and your main tests fail. I understand that either decision would be unfair to some but it comes down to which one is more on the fairer side. It comes down to 1 question vs 1 contest and I believe that making it unrated would be more unfair.
My solution on D is actually failing on pretest 2 but during contest it passed Now consider if the checker was correct i would have checked my code again and solved it after getting a WA.
Yes, I understand it wasn't fair to you. I sincerely apologise for ranting out.
To all those who down voted this I am sorry to have hurt your feelings. I do respect your opinion and I totally accept that either of the scenarios I suggested would have been unfair. But the final decision taken by the contest makers is fair in everyone's eyes and no one loses out so I believe it is for the best.
make it unrated omfg !!
thats what you wont say when you did a heck good job today (or at least you think so). and the guys who got a crappy AC for that problem will get their ratings back to what they should have in the next contest or two ei?
yeah i forgot most of the ,s and .s but yeah nice day too :D
you didn't submit any solution for D lol
When will we know if our submission for D is correct or not?
Why can't simple dfs + 2 multiset pass problem E?
I passed with a simple DFS and a vector of maps.
Perhaps you got some bugs? Personally I wasted 30 minutes for not realizing I overwrote queries instead of accumulating those lol.
You were right, I made insanely stupid bug. GG
Mine passaed 45632893 (After the contest and the code is probably bad)
rated plz!
Just fix the problem(s) of specialjudge.
And those best hackers will get everything done. ;)
In system test, the code that pretest is passed can be wrong, naturally. I think there is no reason that this round will be unrated. Moreover, this round is educational round and hacking can't be attempted in the contest. So this round wasn't influenced by something wrong.
If our solution failed on pretests we will have time to make that solution correct. But now we can't do anything. So if round gets rated it will be unfair for all participants whose solution failed on D because of bug in checker. So round should be unrated.
if your solution is this:
then you obviously know your solution is wrong.
and if its something different, how is it different then having very easy pretests if it passes sample correctly?
My solution is not even close to this. And we can't assume all 36/37 pretests are like samples (in running contest).
Same would be the case when pretests are weak. but we don't make it unrated in that case.
36 weak pretests in D! We are not that unlucky
If it is little amount of people of whom they were affected, I think the round should be rated, because nothing bad as participating and then get, 0 rating changes :D
Let's hit the unrated button.
PikMike said this in Discord server...
damn that feels good..
It seems that the special judge of problem D is incorrect. So I'm thinking about something like ummmmm.. unrated? In fact, I just wanna complain about the awful quality. Please check your contest more carefully.
Let's make it unrated
Ппц лажанклись :)
Я считаю контест должен быть рейтинговым , так как человек осознанно отправлял свое решение . Я не думаю что человек , который отправил
cout << 0 ;и затем не написал адекватное решение , решил бы эту задачу .Но кто — то просто набагал в реализации, а престесты это не выявили
I feel that the contest should not be rated. Any opinions?
please make it unrated
It say people, who get WA1 on D.
I'm wondering why my bruteforce solution on problem E could get Accepted... Can anyone explain why?
Don't worry fam, it's no longer accepted now :)
The answer to "why" it was accepted before is because pretests are never perfect.
Принципе те кто норм решали д так ее и решили так что можно делать рейт
Please keep it rated !!
please rated
So many people wanting the contest to be unrated are people who just did bad, not people who were affected by D.
I did bad and was also affected by D
OK ,The contest must be UNRATED!! ;)
I solved problems A, B, C, D and F. I was really happy with my results and now my D got wrong answer on test 1 (after the contest). I have A, B, C, F problems accepted, which worth less than A, B, C, D because solving A, B, C, D is faster than solving A, B, C, F. A similar problem was at round 485 (the queue froze during the contest): http://codeforces.me/contest/987 I lost 166 rating points there, I can't believe this is happening again. Instead of gaining points, I will lose :( Please make it unrated.
If you got wa on even sample who is to blame really?
I never check the 1st example, I don't get penalty if I get WA on test 1. And why would I check after it got AC?
please rated
I messed up, got stock on C god please make this unrated
Am feeling kinda stupid.... Anyways how to solve E ?
Whenever you enter or exit any node, update BIT. I got that idea but implemented it with set instead of BIT during contest.
solution: http://codeforces.me/contest/1076/submission/45630591
Thnx
You can do a simple DFS throughout the entire tree, starting at node 1 (i.e. root).
Before starting, let's denote
accumulatedas an integer storing the sum of all added values for the current node. We'll get on with the way it worked below.When we start traversing from node
zwith depthdepth, we'll do all these things:zas subtree root, and add the x values of all those queries intoaccumulated.z(only those with distance not larger than d). Therefore, we'll use a global arraydeactivated[](more info in next steps). For each query with maximum depth allowed of d, add x intodeactivated[depth+d+1]. Of course, since d ≤ 109, ifdepth+d+1surpasses the maximum depth of the entire tree, ignore it.deactivated[depth]fromaccumulated.Then,
accumulatedwill be the answer for vertexz. Store it and start running DFS like usual. When done traversing, remember to undo all the above steps before leaving the function.My submission, for further clarity: 45624305
Thnx. Got it. Simple!! My bad.
Nice solution!
Wait, another Kuroyukihime around here? <3
lotus is my wife!
We discussed the issue and came up with the following decision:
Those who got accepted earlier and get WA now won't be affected by rating changes. For everyone else (for those who got correct verdict) the contest will be rated.
very well
Please make it rated for those who use
cout << 0It is clear that someone might get lucky enough to try it and get AC
But it does not makes sense that many people were able to do it.
It is clear that they clearly discussed the hack among themselves.
Can you explain what was the issue clearly? Incase if the WA was on hidden pretest then maybe next time make it unrated for everyone having WA after final system tests too in all rounds?
For some solutions in problem D that should be rejected the checking program answered that they are accepted.
How many such users are there? I still fail to understand if a solution gives correct answer on sample tests and gives WA on some hidden tests whats the problem... How is it different from having weak pretests..
Because the checker gives AC even if the solution gives incorrect answer on samples.
2 categories:
gets AC on samples previously, WA on samples now
gets AC on samples previously, WA on hidden pretest now (eg: http://codeforces.me/contest/1076/submission/45623636)
i think number 2 should be rated
I think number 2 should be rated
The checker wasn't correct,
It outputs ac if you just printed less than or equal to K distinct numbers from what i understand(even if you print 0).
What about the people who are getting +ve rating change even after being affected by WA in D? It doesn't make sense to make it unrated for them.
Just unrated all, let this round be a practice round
Like traditional educational rounds
Make it like those who got accepted earlier and get WA now won't be affected by rating changes if their delta is negative. P.S. My delta shows positive by predictor
How about being unrated for negative deltas?? Seems cool!!
But just a question, the unrated people will be considered out of contest(unofficial) or not??
Similar thing happened in this contest
Why “Those who got accepted earlier and get WA now won't be affected by rating changes” ? Why don’t we consider those are Accepted at the time it’s correct and ignore all submissons after that? This contest’s rule is ACM/ICPC, right? In ACM, it’s also rejudge as the way I mentioned. There is no ACM/ICPC contest skip a Accepted submission to judge final submisson in this case!
Sorry, I miss your mean.
Why different decisions for similar problem that happened in educational round 51?
BledDest any comments?
When there were only 10 contestants affected, it was easy to check them manually.
When there are 500 of them, it is much harder since we can't automatically do it.
You should take the "unrated" users out of the rating pool entirely (i.e. make them unofficial). Rating deltas are comparative: if somebody gains rating, someone else is supposed to lose it. If you just make the users not affected by rating changes, you'll have some users who influence the ratings of others but don't get their ratings influenced themselves.
I hope what I'm saying makes sense, I don't really know how to express my idea.
D-Forces
It's my first chance to become master, I'd like to see it rated, but if the wrong make the contest unfair seriously, it should be unrated.
If you deserve it then you will get it
Actually I don't even it's rated, lol.
Can someone explain to me what I messed up?
http://codeforces.me/contest/1076/submission/45631931
It's just a dfs + 2 multisets. I must have looked over this more than 20 times. (I also put the updates to active/spent before and after the recursion, but that didn't do anything.)
Thanks in advance.
nvm solved, made stupid bug
Can someone explain me why this solution for problem A will fail ? http://codeforces.me/contest/1076/submission/45621631
3 baz
Your answer is ba when my answer is az.
Deleting biggest one is not the solution check it 5 abcad
Consider this case:
3 bac
Your code output "ba", while the correct answer is "ac".
So, what you have to do is not removing the largest char in the string, instead you have to remove the first char s[i] such that s[i]>s[i+1], as this will result in smaller string.
Can someone explain me why I'm wrong? I made a submission to count number of good vertexes and with 50000 edges, one can't have more than 50001 good vertexes.
45607996 // the original one, from the contest 45632353 // the modified one
The edges you give aren't necessarily connected. So you could have tree fragments everywhere. You have to do a dfs to get the edges and make sure they can actually reach the 1 node. (I might be wrong.)
I'm using Dijkstra starting from vertex 1, so the graph is connected for sure
I submitted problem D 3 times.
In the second time, I get AC but the system said WA.
When rejudge, My second submission is changed (it exactly the same solution of prolem A). I think this is a bug of Codeforecs. Could you consider my case?
Submission number: 45627317
Before rejudge, WA on test case 3.
After rejudge, WA on test case 1, and the code is totally changed :( why ?
Hi Mr.MikeMirzayanov,
My submission 45627317 was changed after system rejudge. I sent a message to problem setter but he did not respond. Please check again I will support any thing.
It maybe I submitte wrong file code. :’( Sorry
is your standing in the leaderboard affected by how many accomplished hacks do you have?
Please don't unrated, I probably become specialist after this round TAT.
Don't worry, I think u can become specialist soon ~~~ fight!
weird behavior, according to my code it never can be N for 69 but here in cf it is showing N.
Looked at your code — if you use the cin/cout speedup for C++, never mix them with printf/scanf — the streams are desynchronized so the output may not come out in the same order as you expect it to. That's what is happening here.
Thanks!! i got it.
You should look up what things do before you use them :)
That
#define timesave ios_base::sync_with_stdio(false); cin.tie(0);, isn't some magic fairy dust that you just sprinkle over your program to make it faster. It has some effects.To be more specific,
ios_base::sync_with_stdio(false)means (as the name suggests) that you are disabling syncing between io with streams (the kind you do with cin and cout) and standard io (the kind you do with scanf, printf etc). You disable the sync, yet in your code you use both methods of io (you use cout for the "No" case and printf for other cases) and then expect them to be synced up.Why “Those who got accepted earlier and get WA now won't be affected by rating changes” ? Why don’t we consider those are Accepted at the time it’s correct and ignore all submissons after that? This contest’s rule is ACM/ICPC, right? In ACM, it’s also rejudge as the way I mentioned. There is no ACM/ICPC contest skip a Accepted submission to judge final submisson in this case!
The thing is that people could check their source once more if they knew that's wrong, but everyone usually stops at the AC verdict
He meant, "those who got accepted due to the bug, and the same submissions got WA after rejudging".
And for that, it's certain enough to say why it should be unrated (at least) for them.
Thanks, bro. I know his mean now.
Isn't is unfair to those who are getting positive delta but it will be unrated for them.
Can you please proof the problem C ?
It's a pure mathematical problem.
According to the given formula, we can figure out
, thus 
.
You can draw the graph of the equation
, and figure out a few things:
For the last case (d ≥ 4) no need for binary search, instead, solve the equation
which is actually a2 - d * a + d = 0. After that, b = d - a.
Simple.
I feel freaking odd to deny solving this simple quadratic equation and binary searching the answer during contest time :D
Well, whatever that works :D
Те, кто сначала получил AC, а потом WA, не подвергнутся изменению рейтинга. Для всех остальных (те, кто получили правильный вердикт) контест будет рейтинговым. Здравствуйте, но по моему мнению делать раунд не рейтинговым для тех у кого + рейтинг как то неправильно, я бы пересмотрел решение с вашей стороны.
Hello, but in my opinion, to make the round not rated for those who have + rating as something wrong, I would reconsider the decision on your part.
if i did't got accepted, my rank will up. and now my rank won't up. sad :'(
if i did't got accepted, my rank will up. and now my rank won't up. sad :'(
And persons that haven't try the quest D? Is unrated or rated?
Yo yo dudes, come on, the ones who got affected should have their rating increased if it shows +, and nothing if it shows -.
Preview twice, post comment once.
just another [partial unrated educational round rated for div 2]
I got AC earlier and got WA now. But despite that, can I still get rated since CF-Predictor seems to indicate I will still get a positive rating increase.
If I got D accepted with a wrong solution, but still managed to gain some rating after my D got WA, I do not see the point of why my rating should't increase.
How to solve C?
x + y = d xy = d Math system
binary search
I spent a lot of time for D problem. And i have a nice score . Why my contest won't be rated. I don't do
printf(0);
I do bfs but my solution get wrong answer after rejudge. Please help me!!!.
It is not fair.
You are so right. Why do you ban from contest. Don't accept question but it should be rated for all.
Can anybody proof me B problem, pleace
If n is even, then the smallest prime divisor is 2. After subtracting 2 from it, n is still even, so the smallest prime divisor will keep being 2. Therefore, the answer is how many times you can subtract 2 from n, which is n / 2.
If n isn't even, find the smallest prime divisor d. You do one subtraction and get to n — d. Now, d is most certainly odd, therefore n — d is even, so the answer for n — d (as described above) is (n — d) / 2. Counting the subtraction of d from the start, the total answer is (n — d) / 2 + 1.
"Those who got accepted earlier and get WA now won't be affected by rating changes. For everyone else (for those who got correct verdict) the contest will be rated."
Please make this only for those who are getting negative rating changes.
Making this unrated for those who are getting positive rating changes even with WA on D is unfair.
"Those who got accepted earlier and get WA now won't be affected by rating changes. For everyone else (for those who got correct verdict) the contest will be rated."
This is unfair for the users with positive rating changes even with WA on D. Please see if there is an alternate solution for this issue.
I totaly agree. Please make it rated for the ones who will increase their rating.
BledDest why not doing this ?
Atleast make it rated for those getting +ve rating change, no matter if they were affected by D or not.
this contest should be rated for all those who got correct the 4th one but failed later..but still are getting their ratings better than before and unrated for the ones whose ratings would be decreased due to the 4th question.
Can anyone tell me how to solve problem D ?
run dijkstra from vertex 1 to all other ones
that gives you a tree of shortest paths
all you need to do is remove leaf by leaf untill you have k+1 vertices (and k edges)
it clearly maximizes the number of 'good vertices' and is always valid as well
Can anyone gives me a hint on problem E?
My friend tell me its depth segment tree ， but i still no idea yet update： I pass the problem just now，here is my code http://codeforces.me/contest/1076/submission/45654052，I think u can get my idea easily。orz，the solution not very difficult，But I've been thinking about it for so long. It seems more practice is needed……
Can anybody please proof the problem C mathmatically. It would be greatly appriciated. Thanks :)
Consider a * b = a + b = d
we can get 2 equations for a , a = (a+b) / b = d / b and a = (a * b) — b = d-b
d / b = (d — b) -> b^2 — bd + d = 0
so , we can use quadratic equation to get b , then a = d/b But if there is no valid answer from quadratic equation then answer is N
We know:
1) (a + b) ^ 2 = (a ^ 2) + (b ^ 2) + 2 * a * b
2) (a — b) ^ 2 = (a ^ 2) + (b ^ 2) — 2 * a * b
So we can calculate (a — b) ^ 2 as follows:
1) (a — b) ^ 2 = (a + b) ^ 2 — 4 * a * b
We know also that a + b = d & a * b = d.
let A = d ^ 2 — 4 * a * d
So we have (a — b) ^ 2 = A
Now, in order for the problem to have answer, A must be positive. In case where A is negative simply output 'N'. In case it is positive, find it's square root and name it c.
now we have to equations:
1) a + b = d
2) a — b = c
So a = (d + c) / 2 & b = d — a
After calculating the values for a & b check them. The problem wants a & b to be non-negative real numbers. So if either of them is negative then output 'N' and else output the numbers.
By Vieta's formulas, we know that the sum of roots of the second degree polynomial ax2 + bx + c is equal to
while their product is equal to 
. So if such numbers exist they will be roots of the polynomial x2 - dx + d.
why exactly did people try to submit solutions with cout << 0 anyway?
that feels just odd to me
Can someone please explain me why my answer is wrong for problem A in the shown test case? Input 1000 rkqggsabguejnkvqhflwqtndjqakicbgcirayhvustungfyjrvgvxdcpwaoyqmqrorxfjlmvqazvgqwbwkiwypcxclzhskvrjdxrgbanlngwymdlmgurflfvnersfqkwnsmsh...............
Participant's output rkqggsabguejnkvqhflwqtndjqakicbgcirayhvustungfyjrvgvxdcpwaoyqmqrorxfjlmvqavgqwbwkiwypcxclzhskvrjdxrgbanlngwymdlmgu................
Jury's answer kqggsabguejnkvqhflwqtndjqakicbgcirayhvustungfyjrvgvxdcpwaoyqmqrorxfjlmvqazvgqwbwkiwypcxclzhskvrjdxrgbanlngw..................
(why is 'r' being cut instead of 'z'?)
Consider the simpler case:
Output:
acYour code's output:
baYou should delete the first character s[i] such as s[i] > s[i+1], not the largest character
Can anyone make me understand solution of D. Had a terrible round.
My solution is based on dijkstra's algorithm from vertex 1. So while we're running dijkstra , i just pick the first K node(that is not 1) that we visit by dijkstra , if we were about to exceed K just break the loop. (FYI my dijkstra is implemented in a while loop with a priority_queue as the main data structure , you can see the submission from my profile.)
Actually Dijkstra process built a shortest-path tree with N vertices from the graph. So we will build that tree, and repeat this N — k — 1 times: Find a vertex that is a leaf and delete it. This process make sure all the current vertex of the tree has as same shortest distance from vertex 1 as it was before the deletion, and the number of these vertices is largest. This can be done with dfs
You can make the deletion simpler, by dfs the shortest-path tree and build a subtree of k edges. Here is my submission 45633192.
How to solve problem G ?
Was the contest unrated for all..as my rating has not been increased.
So we have just eliminated everyone affected by D... what?? This is just so stupid. Someone who has done E or F and whose rating might be +100 would be unfair for them!! Make it rated for those with +ve rating change please.
" Those who got accepted earlier and get WA now won't be affected by rating changes. For everyone else (for those who got correct verdict) the contest will be rated. " — What if the those contestants will get a higher rating if we skip D submissions of those users?
Эм, у меня упала D из-за Вашего бага. Но я хочу, чтобы у меня изменился рейтинг... Эм...
My rating still hasn't changed, is everything fine? I haven't touched D at all.
UPD. It did now, sorry.
deleted
For those who got TLE on test 64 on D: When implementing Dijkstra, do not check edges from a vertex if it is already visited (in other words, if the distance from the PQ is greater than the one written in the distance array). A vertex can be pushed into the PQ O(V) times and it also can have O(V) outgoing edges, so it can be O(V^2) in the worst case. Furthermore, this can be repeated for multiple vertices and possibly reach O(V^3) in a complete graph.
The generator is:
This is unfair to me. Predictor was showing I will get +50 rating. But now this became unrated for me. This is unfair...ummmmmmmmm
Is there a way to look up what test was used to hack my solution, in case I want to debug?
View test under the hack verdict: https://codeforces.me/contest/1076/submission/45608998
Is there editorial?
Будет ли опубликован разбор?
For E is it possible to build some type of tour so that we can use segtree for range update and then push all the changes?
I have the same question. Can someone answer this?
i was wondering how setters managed to change the rating based on a particular problem's verdict... is it a database sort or ??
Why TLE on Test Case 64? problem D
maybe this
Thanks. Accepted.
Auto comment: topic has been updated by awoo (previous revision, new revision, compare).
Auto comment: topic has been updated by awoo (previous revision, new revision, compare).
Спасибо за контест.
I think in "Meme Problem(C)" float and double will give different answers. Both the answers shall be considered valid since logic is same. If programmer is able to give any one of them it implies his/her logic is sound.