Привет, Codeforces!
В 29.10.2021 17:35 (Московское время) состоится Educational Codeforces Round 116 (рейтинговый для Div. 2).
Продолжается серия образовательных раундов в рамках инициативы Harbour.Space University! Подробности о сотрудничестве Harbour.Space University и Codeforces можно прочитать в посте.
Этот раунд будет рейтинговым для участников с рейтингом менее 2100. Соревнование будет проводиться по немного расширенным правилам ICPC. Штраф за каждую неверную посылку до посылки, являющейся полным решением, равен 10 минутам. После окончания раунда будет период времени длительностью в 12 часов, в течение которого вы можете попробовать взломать абсолютно любое решение (в том числе свое). Причем исходный код будет предоставлен не только для чтения, но и для копирования.
Вам будет предложено 6 или 7 задач на 2 часа. Мы надеемся, что вам они покажутся интересными.
Задачи вместе со мной придумывали и готовили Адилбек adedalic Далабаев, Владимир vovuh Петров, Иван BledDest Андросов, Максим Neon Мещеряков и Роман Roms Глазов. Также большое спасибо Михаилу MikeMirzayanov Мирзаянову за системы Polygon и Codeforces.
Удачи в раунде! Успешных решений!
UPD: Разбор опубликован.
Waiting For Another learning Contest.
Have you paid copyright to naman1601 for using that tag?
Hey, I understand that you want to make a point, but don't you think tagging is unnecessary? I believe noone likes to be tagged just to see their meme style being stolen by random people.
What harm did you get from this tag?
wasn't he joking ? I believe he was just memeing.
I wish if div 3's were more frequent...
when i started, i thought that i can't participate in Div2 because my rating is < 1600))) So i waited for Div3s)
I have never participated in contests but it was my first time and I could not do well. when is Div 3 ?
https://www.timeanddate.com/worldclock/fixedtime.html?day=2&month=11&year=2021&hour=17&min=35&sec=0&p1=166
How did you improve so much?
solved problems and watched videos on Pavel Mavrins YouTube channel
Good luck to everyone on this educational :D
my problem b just failed for longlong in this way...
I hope I can add 50 points
sure you can! if there are any problems, just use calculator!
Glad to see no unusual time.
Hey, I have few queries to ask about educational Rounds:
1) I heard that all problems have equal points, Is it so?
2) If every problem does have equal point, then, Is there any deduction of points after every minutes during contest? If yes, then does it vary for each problem?
Thanks in advance.
It is ICPC style contest. There are no points. Only number of solved problems matters. And there is a penalty which breaks a tie between people with the same number of solved problems.
Penalty is calculated like this. If you solve any problem, then the minute on which you solved it will be added to the penalty. For example if you solve problem after 1 hour and 23 minutes after the start, then 83(60+23) will be added to the penalty. Also if you had unsuccessful attempts on this problem previously, then each attempt will add 10 penalty points.
there are queue in codeforces it will be solved before the contest ??
How to solve E ??
for dp[n][x], iterate over i = 0 ~ n but i != n — 1, which means i people died in the first round
The condition to have no winner is to have at least two same max numbers and then the rest of the numbers can be anything less than that. Am I correct?
Countercase: [1, 1, 2]
There is only one maximum, but all heroes receive 2 damage in the first round and die, so there's no winner.
Thank you for replying! Is this like an edge case? If no, then what was the intended solution?
It's not an edge case, there's no way to eliminate these cases easily.
We will post an official editorial in 24 hours after the contest.
Shortly, the main idea is dynamic programming of the form $$$dp_{i,j}$$$ — suppose, after some round, all heroes received $$$i$$$ damage, and exactly $$$j$$$ of them died, what is the number of ways to make it happen?
sorry but why wait 24 hours for editorial, when hacking ends in 12 hours? its almost as if educational rounds are notorious for slow editorials
So maybe just handle such cases alone?
My approach was adding all possible combinations with max value <= $$$min(n-1, k)$$$.
Then for all $$$i$$$ bigger then or equal $$$k$$$, do what faraz said, at least two same max numbers and then the rest of the numbers can be anything less than that.
I didn't implement in time though and unsure if even close to correct.
This solution doesn’t cover all cases, and there is no easy way for that. And that’s why you have to do dp
Does problem D have an actual clean solution other than sorting the rows and prefix/suffix max/min on four sides?
I did the same thing. 3961ms AC...
Me too, but only 810 ms. record
Would really like to see the editorial for D
:D In C Problem, complier 64bit wrong :D and 32bit AC :D -
Most likely the pow function here is the culprit. Even if both of its arguments are integers, it still works with non-integer types, so it sometimes causes precision issues.
tks, I think I need to use my pow function for the next contest.
Took me 40 minutes to figure that out :')
But i used the binary exponential as power still the error is there
Can u please explain how u solved C problem?
you can use n = 10^(a[i + 1] — a[i]) — 1 notes for each note. For the largest one, no maximum. Iterate each note from small to large. if k is more than or equal to n then use all the notes, minus n from k and move to next note. if you have k less than n, then use (k + 1) notes and done.
:| How to solve Problem D? :( I can't think of solutions for it.
... Find the prefix max, prefix min, suffix max, suffix min along each row.
If you sort the rows by the first element in increasing order, it turns out that blue rows is a prefix of the matrix.
I read D wrongly as
Me too, initially. But after looking at the figure, I corrected my understanding.
I want to ask all of you, honestly, pls tell me which problem was good for you and why? For me, it was so nonalgorithmic problems :(
All are quite good problems. If you talk about algorithmic, D — F of course are.
Hi Folks, need help, how can we approach problem A? I tried few ways but my approach is wrong.
first and last symbols must be the same of the string to achieve AB's = BA's
Yes. I spent 19 minutes to realize this simple result...
Me too got confused and after 5-6 WA i realized the simple solution :(.
Why Math.ceil() in java is giving wa on testcase 6 Wa But calculating ceil manually gives ac AC
coz I think Math.ceil() will give some precision error while manual ceil gives correct answer. See below: ~~~~~ Input: 1000000000000000000 2 Checker Log wrong answer 2nd numbers differ - expected: '500000000000000000', found: '500000000000000002' ~~~~~
. Using Math.ceil(), we will get above error . !!
Well that was embarrassing
How to solve E?
Think about how to kill a fighter. His health should be lower than n. So, no winner means all fighters have health less than number of fighters at some time. Pick k players and assign them any health lower than n. C(n, k) * POW(n — 1, k) choices. For the other n — k fighters, health of each of them is decreased by n — 1. So, here is a sub problem: the number of choices when we have n — k fighters with maximum x — n + 1 health point.
dp(n, x) = sigma(k = 0 to n, k!=n-1, C(n, k) * POW(n — 1, k) * dp(n — k, x — n + 1))
Thanks
how to solve c ?
You must use the largest number of smaller denomination bills before you can use the larger denomination bills. All you need to do is count how many bills of each denomination you can use, and remember that you can use no more than 10^(a[i+1]-a[i]) — 1 bill of denomination a[i] (where a[i] is the denomination of the bill being counted, and a[i+1] is the denomination of the smallest bill, the one larger than a[i]) I hope I described the solution at least a little clearly :)
where is the editorial?
Damn , I solve problem after contest ended by menuties
Today I got a lot of WA on third as I was using gnu c++ 64 bit
4th numbers differ — expected: '999999920999999999', found: '999999921000000000'
but after contest friend suggested me to use gnu c++ 17
ok 4 number(s): "59 778 148999 999999920999999999
anyone know why this happen?
No idea how but I just ACed F using $$$O(n^{\frac{5}{3}})$$$, actually its $$$O(nk^2+\frac{n^2}{k})$$$ with $$$k=150$$$. Posting this here hoping someone can hack it somehow. 133531014
I don't know whether or not it's hackable, but you can very easily improve the $$$O(nk^2)$$$ DP part of your solution to $$$O(nk)$$$ by simply not visiting useless DP states. Specifically, notice that you can't remove more nodes than you've currently processed, so if you've processed the first $$$m$$$ children of some node, and you're about to process ($$$m+1$$$)-th, then you have $$$\min(\sum_{i=1}^m sz_{ch_i},k)$$$ useful DP states. Proof for how this then becomes $$$O(nk)$$$ is here.
With this, setting $$$k=\sqrt{n}$$$, the complexity becomes $$$O(n\sqrt{n})$$$, which comfortably passes in 1s, my code: 133546415
So many hacks on problem B. Can anyone give me the edge case?
can someone tell me whats wrong in my code? https://codeforces.net/contest/1606/submission/133515590
Because 10000 iterations isn’t enough. Answer can be very large and you can’t loop.
thanks but i thought it grow fast like fibancci sequence so i thought 54 is enough can you explain why this conclousion wrong
After copied computers reaches k, each round could only add k more computers.
For example n=10^18 and k=1. You can copy to 1 computer at a time
ok now i understand so the answer for this case shoulde be n — 1 i will try it thanks alot
Yes
How to solve F? I assume quadratic DP is trivial? Can it be improved or something?
It is really an educational contest thanks for writers
can someone help me with my code https://codeforces.net/contest/1606/submission/133548731. It is giving wrong answer and I don't know why.
Overflow. Change dp[i+go][k]+=dp[i][j]*(power(go,j-k,mod)*ncr(j,k,mod))%mod; to: dp[i+go][k]+=(dp[i][j]*((power(go,j-k,mod)*ncr(j,k,mod))%mod))%mod.
This will solve the WA, but you will get TLE.
thanks a lot. i think the tle can be fixed by precomputing some stuff.
How to solve problem E? I'm stuck.
How to solve problem E? I'm stuck.
See my comments above.
It's been more than 8 contests and haven't improved yet, feeling very low and disappointed not able to solve even a single question in this round. Also doing upsolving but not improving any suggestions please
Create a mashup of 4 A(1000 level) problems + 4 B problems(1200 level) and solve them in the virtual contest.
Can someone please explain their approach for Problem D?
let mnl[i][j] be min(a[i][k] for 1<=k<=j), mxl[i][j] be max(a[i][k] for 1<=k<=j), mnr be min(a[i][j] for j<=k<=m) and mxr be max(a[i][j] for j<=k<=m). Iterate from column number 1 to column number m-1. Let the current column number be j, let array t contains all the row indices i in ascending order of mxl[i][j]. Now, if we can cut the column into two pieces at column j (j being in the left part), there must be some prefix of t such that max(mxl[k][j] for k belongs to prefix of t)<min(mnl[k][j] for k belongs to suffix of t) and min(mnr[k][j+1] for k belongs to prefix of t)>max(mxr[k][j+1] for k belongs to suffix of t). Here, all the indices in prefix are coloured blue and the rest are coloured red.
Here is my code. (Ignore the segment tree templates. I initially thought of implementing using segment trees but, later used multisets).
Can anyone tell me what's wrong with my solution? 133471460 For example on this test case : 576460752303423488 288230376151711743
Jury's answer is 60 but according to me it should be 59. As, first 59 powers of 2 will give the sum of n-1 and 2 ^ 58 < k here.
Even I got it wrong. The issue is with log2. Instead divide by 2 repeatedly.
Oh, thanks! Never using log2 again :(
How to solve F using segment tree or treap?
Hi , i was checking my final standing and i saw i just got wrong answer after the contest and even hack session was over while before that i have got accepted in problem B. So i don't know if they changed the test cases or what but i think it's not fair to change the test cases when the contest is over and changing the test cases should just be allowed while the contest is running.(and i didn't get hacked , i just suddenly got wrong answer on test 30 in problem B).
This a rule in contest which have hacking phase in them. They collect all hack cases and insert them as new tests.
oh i didn't know that thanks for responding.
When will the editorials and the ratings get updated?
This is my hack case which kills more than 100 submissions.
The issue is numerical error of log or pow in 1e18.
see also the editorial of this problem : ABC215-B
Hi, awoo, and other round coordinatrs. Please check this issue that my solution for problem C is skipped, reason stated that it was coincided with others solution. The solution to the problem is quite intuitive, may be, that's the reason. Please check it. Not this time again.
can you tell us the number of submission that coindieded with yours??
if you can't, you are just another cheater from India -the country of cheaters-.
The solution to the problem is quite intuitive, maybe, that's the reason, Yes it is so intuitive that you changed your template and coding style on C.
I got a message from the system that my solution is the same as some user in C and all my solutions for the first 3 problems are skipped !! I hope you can rejudge and give me my points back :(
Can someone help me explaining why this solution for E problem is not correct?
In my solution winner must have >= n health to win(others n — 1 heroes can have < winner health)
Then I subtract from all possibilities win possibilities
https://codeforces.net/contest/1606/submission/133586943
I did the same thing but it wasn't working for the fourth sample case. If someone can point out the error in the approach, it would be really helpful.
MikeMirzayanov In the Educational round that was conducted yesterday, I have been wrongly flagged for plagiarism. The solution for question C was fairly straightforward in terms of logic and coincidence should have been expected by the problem setters. I assure you I have not indulged in unfair practices. I participated after a fairly long time and was really happy that I performed well. Please return my rating delta. Thanks in advance.
Was waiting for an educational round for a long time.... Finally had a great contest today and was ranked 858(my first ever under 1000 rank :-) and got a rating boost of +105 :-)
Auto comment: topic has been updated by awoo (previous revision, new revision, compare).
I haven't been seeing them publishing top 5 winners and top 5 hackers and 1st one to solve the each problem for a while..