Привет, Codeforces!
В 06.04.2023 17:35 (Московское время) состоится Educational Codeforces Round 146 (Rated for Div. 2).
Продолжается серия образовательных раундов в рамках инициативы Harbour.Space University! Подробности о сотрудничестве Harbour.Space University и Codeforces можно прочитать в посте.
Этот раунд будет рейтинговым для участников с рейтингом менее 2100. Соревнование будет проводиться по немного расширенным правилам ICPC. Штраф за каждую неверную посылку до посылки, являющейся полным решением, равен 10 минутам. После окончания раунда будет период времени длительностью в 12 часов, в течение которого вы можете попробовать взломать абсолютно любое решение (в том числе свое). Причем исходный код будет предоставлен не только для чтения, но и для копирования.
Вам будет предложено 6 или 7 задач на 2 часа. Мы надеемся, что вам они покажутся интересными.
Задачи вместе со мной придумывали и готовили Адилбек adedalic Далабаев, Иван BledDest Андросов и Максим Neon Мещеряков. Также большое спасибо Михаилу MikeMirzayanov Мирзаянову за системы Polygon и Codeforces.
Удачи в раунде! Успешных решений!
Также от наших друзей и партнёров из Harbour.Space есть сообщение для вас:
Привет, Codeforces!
Пришло время для еще одной захватывающей возможности — стипендии от Harbour.Space!
Мы ищем талантливых людей, которые хотят начать свою карьеру в области кибербезопасности со стипендией 50% для обучения в Барселоне.
Если вы любите технологии и стремитесь к отличной карьере, то кибербезопасность может быть для вас!
Это не просто слова — как член сообщества Codeforces, вы знаете ценность непрерывного обучения и развития. Программа подготовки магистров по вопросам кибербезопасности в Harbour.Space отвечает увеличивающимся потребностям рынка, обусловленным ростом угроз глобальной кибервойны, для специалистов в области кибербезопасности, имеющих продвинутую подготовку в области защитных и наступательных кибер-действий. Программа предназначена для предоставления знаний, навыков и умений, необходимых для успешного выполнения важнейших задач в области кибербезопасности.
Требования:
- Степень бакалавра
- Свободное владение английским языком
- Резюме на английском языке
Что вы узнаете:
- Прикладной анализ угроз
- Поиск угроз
- Обратная разработка и Анализ вредоносного ПО
- Цифровая криминалистика и реагирование на инциденты
- Пентестинг и этичный взлом
- Аппаратная концепция модулей обработки для IoT
- Сети и протоколы
- Антикризисное управление и коммуникации
- Блокчейн и IAM
- Гибкие навыки: формирование команды, навыки презентации и организация встреч
- И многое другое
Не забудьте подать заявку до 30 апреля 2023 года, чтобы иметь шанс получить стипендию и снизить плату за подачу заявления.
Следите за новостями в LinkedIn, чтобы не упустить новые возможности. А так же загляните в наш Instagram, где мы делимся событиями студенческой жизни и историями успеха наших учеников.
Мы всегда рады видеть участников сообщества Codeforces в качестве наших студентов здесь, в Harbour.Space.
Подайте заявку сейчас, чтобы учиться у лучших в этой области и вывести свою карьеру на новый уровень!
Желаем удачи и до встречи в следующий раз!
Harbour.Space University
UPD: Контест нерейтинговый. Приносим свои извинения.
UPD: Разбор опубликован
Good luck to all! Happy decisions! Hope everyone enjoys this round! Thanks: adedalic, BledDest, Neon for the assignments and MikeMirzayanov for system Codeforces!
Worst round testing I have ever seen!..
The second worst contest of the year. The first was still the one in which the problem setter used an older cf problem still, It was rated.
awoo ORZ!
Good luck everyone!
This is where I first became interested in hacking a solution. And why do we need such hacks? Won't this spoil the evening for someone whose solution was hacked?
Ratings indeed matter. But improvements matter more.
Hi Nathan my friend haha
^O^
how can rating drop when you are levelling up?
He's talking about hacking, which means that ur original correct submission becomes WA.
hope to be specialist again.
I am hoping to not become pupil back :(.
Hope to be pupil again
expert or pupil :)
pupil
Hope to get a positive delta
Hoping for the round to go well
Can I have more points if I hacked other people's solutions?
Sorry I was not fully aware.Apologize for wrong comment.
In Educational and Div3 rounds, NO
Spartans!!! it's time to conquer CYAN.
How did people see their expected delta changes? I can only see the status of the problems in the standings.
Most people downloaded a Chrome extension called "Carrot", which shows you the expected delta changes.
I seem to getting logged out and am getting timed out errors while trying to access codeforces , is it just me?
I too facing problems, site not working
I smell unrated round.
Me too
I hope no, because I wrote A too fast, lol)
same vro,;-;
Site is not working properly please look into the matter.
Slowforces
Server problem again?
Thanks for making the contest unrated
Contests has been crashing for past several rounds. Please fix this and make this contest unrated.
site couldn't be reached for around 15minutes :')
The contests have been crashing for several rounds. please fix this and make last contest unrated.
cnm
Having crashed for 30 minutes, it should be unrated!
Extension? This has to be unrated right.
should be unrated
WORST CONTEST I HAVE EVER SEEN!
nice joke
"Problem D is under investigation." What's that mean?
why these days the rounds are too much unbalanced? MikeMirzayanov
Bro just dropped worst contest in CF history and thought we wouldn't notice :skull:
Server problem and investigation? Should be unrated.
unratedforces :(
robotforces
My first time getting expert and it's unrated :(
Question B was a joke for some and some were joke for question b
Fr
Educational round should be tested!!!!!!!!!
Ladies and gentleman, I present to you, the REAL april fools contest :D
Very poor unexpected!!!!
First time I cannot solve problem B in an Educational Codeforces round. Too hard!
Me having a good contest :)
CF- Let's make it unrated
Me having my worst contest :(
CF — Let's make him happy :)
Same here :)
Same here :(
Bruh, new contests are in the review queue for around 5-6 months, and yet you fail to find if there's an error in a question. I can't comprehend how bad the "testing" process must be!
Because there is no such process as "testing". Authors are Too cool, why would they even need to test it ?
What is happening!!!
I was going to be specialist today...
I hate robots.
When an educational round starts, then the server is down
Nothing can beat Div4.
Very correct.
Never been so sad to know the round is unrated when I solve A, B and C in just 30 minutes
I'm sure that I'll see blue after this contest and it just...
I know just bad luck...
Look at the fact that only 1.6k Accepted solutions of problem B. I have never seen this in an Educational round
I thought I could get to Expert but this one is NON-rated now.
Those of you downvoting announcement/making snarky remarks in the comments, please stop. I can't believe I have to say this, but don't you think the authors already feel bad enough about the mistake? It's not like issues with the round (besides technical issues) happen often.
Just because you have a right to complain doesn't mean you should.
Yeah Support! Imagine if you were the author...be supportive!
.
Feeling very dishonoured by not able to solve D
Auto comment: topic has been updated by awoo (previous revision, new revision, compare).
Looks like its a even odd pattern going on solve counts.
Untested EduForces!!
This is the first time I haven't worked out question B(For 2023).
I'm a little nervous.
But I like this feeling!
did you get any idea ? B was hard for me . I didn't get any idea
The contest hasn't ended yet, but it's a cool trick!
Is the game back to life?
Unrated. But it's still running though
So let's just keep thinking.
I hope it could be an April Fool's joke hh
Is it the competition or my comment?
competition
>.<
Bon Appetit 2.0
This competition had one official technical issue and one technical issue from the organizer... It ruined the first three very interesting questions. I feel very angry.
is this round unrated?
Yes
Me too
Yeah, I could see +90 on predictor and the round got unrated.
me too
I think MikeMirzayanov should make some Duckworth–Lewis–Stern method on codeforces for such round.
Like in Cricket
Imagine getting DDOS attack but making round unrated for investigation of a problem.
Your rating graph is pretty amazing
have you ever tested this round...?
Bro. Li is right
I thought I could become an Expert until I found that this round will be unrated
B is so hard for me!
I hate B -_-
I hate unrating-_-
i hate too
Problems like B make me wonder how I spent 12 years studying algebra in school and still can't do basic math -_-
it is a really bad experience.the difficulty order of the questions is unreasonable, Bad server ,and unrated.
Unrated because of issues that affected less than 200 people?
Are you joking? It's not my mistake!Why should I suffer the consequences? `
Bro calm down . It is just a contest .
They made it unrated due to some error in problem D i guess, because starting 15-20 mins when server went down wouldn't hurt much in standings as they already extended the round by 15 mins
Now that it is unrated, would you please post the editorial ASAP?
No comment starting with
as a tester..., maybe this round has no tester?good contest and problems, love from codeforces
Any idea on how to solve F?
Segment tree optimization gragh？
Very nice problem E, satisfying to solve. Such a pity that round got unrated.
How to solve $$$D$$$, and what happened with it?
[deleted]
How to do B? God I've never been stuck at B like this before.
Suppose you increase your leg to M. It will take ceil(a/M) + ceil(b/M) to get to the point. Why ceil? Well, if a is multiple of M, just move (a/M). If it is not, then there is a remainder (a%M) < M. During the increase process you will surely get at this remainder at one point (because it is less than M and you increase one by one). When you get to it just move towards a by (a%M) then finish the increase processes and move to a (a/M) times.
The total cost for a given M is then ceil(a/M) + ceil(b/M) + M — 1 For each test case you can just iterate through all M up to 10^5. You don’t need to increase your leg more than that.
hope I could help
Nice thank you.
I couldn't understand the ceil thing. what if to reach some cell my leg length is 4 and then I have to reach the cell 9,0. Then what you are saying is I will require ceil(9/4) that is 3 steps?? But after 4 there is no number divisible by 9 so it should be impossible to reach 9,0
During the increase processes you will pass by number 9%4=1. Just move 1 towards the 9 then finish the increase and move 2 times 4 = 8.
You don’t need to increase your leg more than ceil(sqrt(1e9)). Why?
Counterexample: a = b = 1e9
This was a rough incorrect approximation, n = 10^5 should work.
anyway, looking at the larger input a=b=1e9, if you make your leg as big as x=ceil(sqrt(a)) your cost will be ceil(a/x) + ceil(b/x) + x — 1 which is about 3x ~ 96k. If you can get to the furthest point with cost about 96 thousand, you don’t need to ever increase your leg more than that, as the cost of increasing the leg would alone be more that that.
You are optimising a/m + b/m + m + O(1) and minimum of (a+b)/m + m is reached in $$$\sqrt{a+b}$$$.
I just found a minimum ans(m) = m — 1 + a / m + b / m + ((a % m == 0) ? 0 : 1) + ((y % m == 0) ? 0 : 1)
for m in interval $$$\sqrt{a+b}\pm10$$$ (optimal constant is less then 10, but it's safer to overestimate it)
Ahhhh, I got it. In the contest the formula having a minimum at a single point felt quite unituitive, and therefore I didn't follow that train of thought. I rather tried to minimize it at two points a / factorOfX and b / factorOfY separately, and hence used the factors logic. Just shows how easy it is to get lost in a wrong approach. But thanks a lot.
There are issues with problem D in the author's solutions even now. My hack got "Unexpected verdict".
It's wrong now. The solutions gives a wrong answer for 1 8 2 10 20 30 1 1 1 1 1 1 1 1 1 1 1 1 1
The correct answer is 8 instead of 3.
Hopefully the issues with the hacks for this problem are resolved now.
If there are still any, please report them as the answer to this comment.
I did binary search for B, but got wa. How to solve B?
binary search what
on AC
B solution: we know that we would never need to increase more than S = 2 * sqrt(max(a,b)) times. We can now try out each max increase from 1 to S. Each time we go from S and reduce the maximum possible for each a and b. This will be done in log(n) times.
https://codeforces.me/contest/1814/submission/201083355
Can you elaborate it a little more
yeah let say max(a,b) is 100, i don't see how we would ever need to make m go above 20. Idk how to prove it though. a looser bound would be 2 * sqrt(max(a,b). Let say you are going to increase m to more than sqrt(max(a,b), you would never need to go more than 2 * sqrt(max(a,b) because during that time you could just decrease the whole thing down to 0.
If you already know the max of m, then you can try out the max of m is from 1 to sqrt(max(a,b)) breaking down a and b is going to be like:
For test with $$$a = 39$$$ and $$$b = 49$$$ you need to set $$$m = 10$$$ to minimize your total number of operations(as far as I can tell). I just found a upper bound for the max values of $$$a$$$ and $$$b$$$ and saw that I could brute force for $$$m$$$ within constraints.
yea edited 2 * sqrt(max(a,b)) is the ceiling
it is 3*sqrt(...) actually.I had myself tried 2*sqrt(...) but that gave me a WA.
checkout my AC submission https://codeforces.me/contest/1814/submission/201083355
algoboi your intuition is wrong,we have to increase till 4 for the testcase a=8,b=4.
i edited the comment. It's 2 * sqrt(). So if its 8,4 then you increase until 5
You need to set S=sqrt(a+b)instead of S=sqrt(max(a,b))
i don't think it's (a+b). a and b is kinda independent. Like you only need to care about the max of (a,b).
so let say you increase m up to M. then for every 1 to M, you decrease some of that from a and b.
Btw it's 2 * sqrt()
The function for max steps by foot length is f(x) = x — 1 + ceil(a/x) + ceil(b/x) You can approximate this to g(x) = x — 1 + (a+b)/x And then to find the local minimum you take g'(x) = 0 so 1 — (a+b)/x^2 = 0 so x = sqrt(a+b)
can you explain how you got to that equation?
i got AC'ed with 2 * sqrt(max(a,b)) https://codeforces.me/contest/1814/submission/201083355
I used 64000 as the max here cuz of 10^9.
Well, it's optimal to first raise your foot length up to some value k before starting to walk towards (a, b). As someone else mentioned above, at some point you will reach the intermediary values a % k and b % k so that you can reach (a, b) exactly and not go over it. So the number of operations for max foot length k is k-1 to raise foot length to k, ceil(a/k) to reach a on the vertical axis, and ceil(b/k) to reach b on the horizontal axis. That's how you get the formula I mentioned. You can get AC by checking k from [sqrt(a+b)-25, sqrt(a+b)+25] https://codeforces.me/contest/1814/submission/201106352
It's not wrong to check all values of k up to 64000, you're just checking a lot of stuff that is not necessary to check. I'm just saying that the optimal k is around sqrt(a+b).
D solution: We know that we can always get a result at LCM(f1, f2, ..., fn) and the difference will be 0, and we would have to change all of di in this case. If we decide not to change all of di then at least one of them will be fixed. This can be tested by iterating at each ith and pretending we are fixing ith and try out every other di as at either the lower end or the upper end, Then compute the minimum number of changes fro every other positions. Complexity: f * k
A: If k is even, we can pay only even rubles. Otherwise, we can pay even rubles or all prices >=k.
B: Unbalanced problem. If the length of leg is increased t times, we need ceil(x/(t+1)) steps for moving along x-axis, and ceil(y/(t+1)) steps for moving along y-axis, so answer is t+ceil(x/(t+1))+ceil(y/(t+1)). If there's no ceil function, by the basic inequality (a+b>=2*sqrt(a*b)) the answer is sqrt(x+y)-1 and optimal t is around sqrt(x+y). So I passed this problem by brute force for t in range [sqrt(a+b)-1000, sqrt(a+b)+1000]. Also we can use sqrt-decomposition to solve in O(sqrt(a)+sqrt(b)).
C: The cost for first robot is s1, 2*s1, ..., k*s1 for each position, and for second robot is s2, 2*s2, ..., (n-k)*s2. To choose k we can let k=n first, and reduce k by 1 while (k*s1) > (n-k+1)*s2. After decide k we can arrange r[i] by the reverse order of the cost of positions.
D: No idea.
E: By some small test cases we can guess that we need to fill the path by some blocks of size 1 or 2, and the size of blanks between each pair of adjacent blocks is 1 (that's because we need to make something like (i, i+1) --> (i+1, i) or (i, i+1, i+2) --> (i+1, i+2, i)), and the answer is 2*(sum of weight of edges in these blocks). If from each range [l, r] we set siz=r-l+1, start=a[l], end=a[r], ans[i][j]=the answer of problem on range [l+i, r-j] (here 0<=i<=2, 0<=j<=2), we can solve the problem by segment tree.
for D : either change all element, or bruteforce on any one non changed element, and then use 2 pointers.
For B, can you explain why it requires ceil(x /(t + 1)) steps to move for 0 to x ?
Because we increase length by t times, the maximum step is t+1, so we need at least ceil(x/(t+1)) steps along x-axis. If x is multiple of (t+1), we can take (x/(t+1)) moves directly, and if x%(t+1)==k (k>=1), we can take a move when the length is k and do other moves after length become t+1, so we need at most ceil(x/(t+1)) steps.
I see, thank you!
My idea for B was to make sqrt n blocks of size sqrt n, then find the block with the minimum cost. Then I checked that block and its left and right adjacent blocks. Does this capture the idea of sqrt decomposition? This is the first problem I've tried it on.
Hey For problem B: how can I prove that, I need to increase length maximum one time. I mean, I can cover 'a' distance with some length and then I can increase length for covering 'b' distance. Why is this never an optimal choice?
just forget that it is like you are fixing it and finding minimum among all m
But this is not necessarily what question asks, my doubt is why this solution always gives the optimal answer. Because the other choice I mentioned is a valid move (may not be optimal) move according to question. So, there must be some proof that shows its always better or equivalent to consider this choice.
Hi. I just wanted to ask if you exploited the fact anywhere in your algorithm that the blocks are of size 1 or 2 only (because the editorial's solution has not)?
Any block of size n (n>=3) can be changed into 1 and n-2.
Yes. I agree with that. I'm asking if you exploited this observation anywhere in your solution. The editorial solution doesn't use this observation anywhere.
I exploited that. But actually we don't need this observation when implement solution with segment tree.
As a !tester, I'm proud to !be one.
How to solve F? I tried offline dynamic connectivity but don't know how to update the accessibility of vertices.
We can create a directed graph representing the components in the dynamic connectivity. Whenever two components merge, we create a new vertex representing the new component, and it gets two arcs into the vertices representing the components we merged.
We also mark each component that contains the vertex $$$1$$$; it can be done at the end of each call of the dynamic connectivity function (just before we roll back all the changes made in that call).
Then, the vertex $$$x$$$ (of the original graph) belongs to the answer if the vertex representing the component containing only the vertex $$$x$$$ is reachable from any of the marked vertices. All we need to do to check that is to run DFS from all marked vertices in this directed graph.
If you mean how to apply the method explained in this blog to this problem.
(I am referring to the solution on the blog) In the original algorithm go function returns nothing but if we modify it to return the nodes which will be at the same component with 1 after some number of branching we can solve this problem. For details, you can check my code (201073595)
I think complexity is $$$O(N\log_{}n))$$$ but works slower than solutions that have extra dsu complexity because of constant factor(maybe my implementation skills).
Do anyone know how to solve B? I didn't participate, but just looked at it, and it seemed interesting. My first thought was that if you can, you always want to increase the leg length up til its sqrt the distance you have to walk. So you look at the biggest square less or equal to x, and same for y. Then you subtract those two squares from x any y. Then you do the same process, all the way down. Keeping track of these squares you know when you have to move, and when you have to increase legs. Is this correct?
Problem B wa3 because I break when answer is greater than last answer.
Then I printed all answer, and found that although the answer curve "looks like" go down and go up, but sometimes $$$ans(i) = ans(i-1) + 1$$$ while the curve is "going down"!
In this problem, the answer is $$$\min \limits_t t - 1 + \lceil \cfrac{a}{t} \rceil + \lceil \cfrac{b}{t} \rceil$$$.
Because $$$t - 1, \cfrac{a}{t}, \cfrac{b}{t}$$$ all have the slope increasing, so $$$t - 1 + \cfrac{a}{t} + \cfrac{b}{t}$$$ have the slope increasing, and $$$t - 1 + \lceil \cfrac{a}{t} \rceil + \lceil \cfrac{b}{t} \rceil$$$ have the slope almost increasing. However $$$\lceil \cfrac{a}{t} \rceil$$$ obviously don't have the slope increasing, so it doesn't truly have the slope increasing.
It is really sad to see my verdict of D changed from Accepted to Wrong Answer. Althougt my solution is actually wrong.
Task E was very cute
First time to become orange. But unrated.
I think it's funny my first sqrt decomposition solution was for a problem B. Not sure if it's correct though or testcases are just weak. The problems were interesting, maybe just a little unbalanced. Shame this round had so many technical difficulties.
One solution for B:
Given the final leg length $$$m$$$, the result is $$$ceil(\frac{a}{m}) + ceil(\frac{b}{m}) + m - 1$$$. How to find $$$m$$$? Intuitively we want to search around $$$\sqrt{a+b}$$$, but the ceiling makes things complicated. Using the relationship $$$ceil(\frac{a}{m}) + ceil(\frac{b}{m}) \in [\frac{a+b}{m}, \frac{a+b}{m} + 2)$$$, we find $$$m$$$ such that $$$\frac{a+b}{m} + m - 1 \lt 2\sqrt{a+b} + 1$$$, so the safe search range for $$$m$$$ is $$$(\sqrt{a+b} + 1 - \sqrt{1 + 2 \sqrt{a + b}}, \sqrt{a+b} + 1 + \sqrt{1 + 2 \sqrt{a + b}})$$$, so time complexity is $$$O((a+b)^{1/4})$$$. solution.
Additionally, we can use sqrt decomposition to reduce this to $$$O((a+b)^{1/8})$$$. The execution time is actually slower because of more operations. solution.
We can search all natural numbers i, until i becomes > current answer. The complexity of this can be proven to be sqrt(max(a,b)).
That's probably the fastest way to come up in contest! I was stuck on this for such a long time.
Expectation: +delta Reality:unrated Action:Nothing to do except Down vote xD
Expectation: +delta Reality: unrated Action: Nothing to do except Down vote xD
Check the cost for each strength from 1 to 50k
Can i apply ternary search (as this is a unimodal function) in this problem...?
No. This is not unimodal function. For example, if a = 100 and b = 50, you can notice that after the function reaches its minimum it doesn't increase strictly.
I made a cubic solution in problem D and got AC (2870 ms) submission
Someone can hack me ? :)
Upd: I did it!
can someone tell me how the case "5 3" has 5 as the answer on problem B? edit: NVM
add move 2 right add move 3 right move 3 up
First, increase the length of the legs to 3 (this takes 2s), then 2s to go to (5,0) and 1s to reach (5,3)
Perfomance 2700 drop to 2350 (D hacked)TAT Fine unrated whatever
Can someone help me with D? WA on one test in case 4. Couldn't figure out the problem.
In your "state" vector, you are considering two values per element. But there can be a third value, which leads to a better solution.
Appreciate the help! But this is a bit counterintuitive for me. Say the target is 10. And fj is 3, isn’t testing 9 and 12 sufficient?
Figured out. Thank you!
Take a look at Ticket 16814 from CF Stress for a counter example.
Ah I see. Thank you!
i dont understand why full bruteforce works in B. it is 100*(2e9) operations in the worst case, isn't it? where am i wrong? https://codeforces.me/contest/1814/submission/201061363
It's not full brute force, ans is getting minimized. As you can see this comment the graph has a lower minima, so once the value of ans is minimised the condition for loop is also changed, so the value of m will be around 5e4 at max, SEE the variable name.
But there is no break condition on that
The thing is value of ans at first is 1e9, but once the loop is started, the value of ans is reduced, ans is NOT constant, it changes in the loop. See the variable names
Ohh I see now, thank you!
ah, thanks, i just have autism
ans variable in the for loop is not a constant..
FR. Same question, but why mine didn't pass then it has the same complexity. link
i iterate from 1 to 1e18 and it still passes..
upd: nvm im dumb
LOL. But guys in the comments above helped me out to understand. The range of the loop is ans, which decreases over time inside the loop, it makes sqrt complexity.
Why does not Um_nik's solution for B TLE? link to his sol
it seems that he brute forces a + b numbers for each test case. Wouldn't it be $$$10^4 * 2 * 10^9$$$ operations in the worst case?
Nope, see my comment above!
He's constantly decreasing ans
awoo ,Please upload the editorial.. IT will be helpfull for us.
For question B - its always better to first increase the value of m and then going on x and y. for finding the optimal value of m we have f(m)=m-1+ceil(x/m)+ceil(y/m) for finding the minimum value we can differentiate this function and should put it's value =0,so by putting d/dm(f(m))=0 we have 1-x/m*m-y/m*m=0 ,by this we can get m=sqrt(x+y),as it is a ceil value so to be on the safer side we should check for sqrt(x+y)-100<=m<=sqrt(x+y)+100
Probably my best performance in a contest just for it to get unrated (╥_╥)
Всем привет!
Решение для задачи https://codeforces.me/contest/1814/problem/A на JavaScript не проходит, но если переписать на Java, то отрабатывает.
Проблема в том что значение n = 10 ^ 18 не укладывается в стандартный тип Number.MAX_SAFE_INTEGER 2 ^ (53 − 1) и для таких целей есть BigInt, но при попытке его использовать тестовая система на движке JavaScript V8 4.8.0 выдает:
, а на Node.js 12.16.3 получаю ошибку исполнения на первом же тесте хотя локально у меня работает:
Это как-то можно поправить или как-то обходить такие кейсы, если я хочу продолжать решать задачи на JavaScript?
в JavaScript V8 4.8.0 еще не было bigint,
А в Node должно работать вот пример https://codeforces.me/contest/1814/submission/201080199
I'm a little disappointed that my O(N^2 log N) solution for Problem D timed out when using std::set<>, but passed when using a pair of std::priority_queue<>'s... I feel like the input constraints should allow bouth (3000 × 3000 × 2log(3000) = ~100,000,000, which seems okay for 3 seconds).
Priority queue is 3-10 times faster, than set. Also, unordered_set is 1-2 times faster than set, but has less applications.
You're right that priority_queue<> is faster than set<>, which makes sense because it doesn't maintain a complete ordering of elements, but it's less than 2x faster on this problem by my measurements, so I would expect the constraints to allow both or neither solution to pass.
std::unordered_set<> is a different story altogether: it's typically backed by a hash table, which makes it asymptotically faster than std::set<> (O(1) vs O(log N), average case) but it doesn't support extracting the minimum element, which is the operation I need for this problem, so it's not really helpful here.
edit: On second thought, I could still use a std::unordered_multimap<> since when removing elements, the keys (power levels) are known, just not the values!
i also had a my n^2logn solution fail and had to constant optimize it to get passed (my log was from a std::sort).
I dont get the point of keeping such a low k (yes i know n^2 + nk exists but its easy to get n^2 logn from there) and making TL tight for n^2 logn tbh.
Can you explain your solution?
Sure! The central idea is to assume that there is one power level
P[i]that doesn't change. Then, we have to consider possible ranges of[P[i]-K, P[i]],[P[i]-K+1, P[i]+1], ...,[P[i], P[i]+K]: all other power levels must fall in one of those ranges. It's easy to check for a range[P_lo, P_hi]whether the other values already are or can be changed to fall into that range, but that naive approach would create an O(N × K × N) solution which is too slow. The solution is instead to start with the earliest range and updated it incrementally (a sliding window algorithm).I think the priority_queue<> version is easiest to understand:
in_rangecontains a list of all power levels (pair with their index) that either already were or could be changed to become betweenP_loandP_hi, andnum_changedcounts the number of changes that were necessary. If a power level couldn't be changed to a value in range (sinceP[j]must remain a multiple ofF[j]), the smallest possible value greater thanP_hiis stored inover_rangeinstead. Now we can tell whether a range is valid (wheneverover_rangeis empty), and it's easy to update a range from[P_lo:P_hi]to[P_lo+1:P_hi+1]by removing the guns with power levelP_lofromin_rangeand adding guns with power levelsP_hifromover_range.For complexity (but not correctness) it's important that when changing the power level to be in range, we pick the largest possible value. An example where performance would be bad if we used the smallest value is K=1000 and P[j]=1: we'd be removing and reinserting the same gun index 1000 times. But by using the highest value we guarantee that each P[j] increases by at least K/2 every time (excluding the 1 time when we use the original value P[j]). This guarantees that the solution takes O(N × N × log N) overall, with log N accounting for the overhead of the data structure.
C is scary at first peek, but it turns out quite easy to solve. B is completely opposite...
back to back two educational rounds resulting in disappointment.
Most of the solutions here for problem B involve brute forcing a specific range of values for
m, but I passed it with a different technique.My technique just tries every minimum
mthat will cause eitherceil(a / m)orceil(b / m)to change, since trying other values will just increase the total moves. SubmissionI assume the number is bounded by
C * sqrt(max(a, b))whereCis some constant (maybe 4?) because the number of factors for a numbernis bounded by2 * sqrt(n). Can anyone tell me the bound on the distinct number ofms and why? Thanks.It is indeed sqaure root, google sqrt decomposition.
How is this related to square root decomposition? If I'm not mistaken, isn't that a data structure / strategy for range updates / queries?
Maybe I am messing up terms. So here is a sketch of proof.
Claim: $$$ceil(a/m)$$$ has $$$O(\sqrt{a})$$$ unique values.
Note that for $$$m \lt = \sqrt{a}$$$, there are at most $$$\sqrt{a}$$$ unique values. For $$$m \gt \sqrt{a}$$$, $$$\frac{a}{m} \lt \sqrt{a}$$$, so again, at most $$$\sqrt{a}$$$ unique values.
I cannot find English material on this yet, maybe someone else can point the way. Here is a Chinese OI wiki page: link
Thanks! I get it now. I assume the constant
CI mentioned will be equal to2, which makes the complexity the same as the number of divisors then.201082916 this is my simple solution for problem B ,you can basically see that this is a Brute forces problem as you will find the best minimum solution between all solution ,so i can simplify the problem as you wanna go from point Zero to point M in minimum operations so as an example if you want to go from Zero to 12 you have the following options :-******** make M = 1 so ans will be 12 make M = 2 so ans will be 1 + ceil(12/2) = 7 operations make M = 3 so ans will be 2 + ceil(12/3) = 6 operations make M = 4 so ans will be 3 + ceil(12/4) = 6 operations
and so on if you continue after the root the answer will be get bigger again so the optimized solution will be always increasing M up to root a or b and other key observation here that we will always take ceiling of the divisibility because for example if we want to go from 0 to 12 and M = 3 so ans will be 2 + ceil(10/3) which is 6 so it will go like that we will first move from zero to 1 (operations = 1) and then increase M to 3 (operations = 3) and then we will move from 1 to 10 in 3 other steps (1 -4 — 7 — 10) so totally they will be 6 operations . Thanks for advance and you can check My Submission for details
That solution gave you WA mate...
corrected
Please anyone to explain B in simple terms? I m not getting the formulas , also any problems like this to train on , getting some formulas, bruteforce it etc
Please anyone to explain B in simpler terms? I m not getting the equations! especially confused about how to know when to add +1 and when to go for multipliers , (how to mix them and how to get the equation for the mixing and how it's optimal )
thank you :(
First, find the optimal value when the maximum jump size is some fixed constant J. In that case, you know you must spend J — 1 seconds increasing the jump size to J. As for the number of jumps, we claim the optimal number is ceil(a / J) + ceil (b / J).
To prove it must be at least this value, note that J(ceil(a / J) — 1) < a (because ceil(a / J) is the first integer >= a / J) so it is impossible to cover a horizontal distance of a with less than ceil(a / J) jumps if the maximum jump size is J. Similarly, J(ceil(b / J) — 1) < b. This proves we need at least ceil(a / J) + ceil(b / J) jumps.
And you can in fact do it in ceil(a / J) + ceil(b / J) jumps by jumping horizontally by a % J, vertically by b % J (which one is first is determined by which is smaller), and then repeatedly jumping by J.
So this proves the answer is J — 1 + ceil(a / J) + ceil(b / J) when the maximum jump size is J. Now we just need to iterate over all values of J that could be optimal. Since a, b <= 10^9, J = 10^4 already gives a time < 10^5, and any J >= 10^5 clearly gives a time at least 10^5, so you only need to check J from 1 to 10^5.
jumping horizontally by a % J, vertically by b % J (which one is first is determined by which is smaller), and then repeatedly jumping by Jthen is it not a%j + b%j + a/j + b/j +j-1
IDK how J — 1 + ceil(a / J) + ceil(b / J) works, i am unable to understand and visualize it could you help me out with an example
Well the a % J and b % J are single jumps. For example, if J = 5, a = 24, b = 12, we should take the following steps.
Raise the jump size to 2 (i.e. 12 % 5)
Jump 1 time vertically
Raise the jump size to 4 (i.e. 24 % 5)
Jump 1 time horizontally
Raise the jump size to 5 (i.e. J)
Jump 2 times vertically
Jump 4 times horizontally
Total vertical distance: 1*2 + 2*5 = 12
Number of vertical jumps: 3 (i.e. ceil(12 / 5))
Total horizontal distance: 1*4 + 4*5 = 24
Number of horizontal jumps: 5 (i.e. ceil(24 / 5))
Total time raising jump size: 4 seconds (i.e. J — 1)
In general the first zero, one, or two jumps should be spent making the remaining horizontal and vertical distances a multiple of J, and then the remaining jumps should all have size J.
Thanks a lot , thats exactly what i needed. it was very helpfull
Mathforces
(BTW, I was doing the virtual participation and during the contest came here to comment this TT)
unrated wuwuwuwuwuwuwu
what can be the rating of problem B, C?
$$$1600$$$ and $$$1500$$$, respectively.
If the contest lasted for the entire 2 hours, my guess is 1400 and 1300
Is there any logic for the step size values to try in B? I was trying ceil(a/step1)+ceil(b/step2)+max(step1,step2)-1, but could not get what step1 and step2 should be.
Well the round didn't went as planned, but honestly I think the problems were great and indeed educational :)
Auto comment: topic has been updated by awoo (previous revision, new revision, compare).
Badmosi