Привет! В 18.02.2024 15:05 (Московское время) начнётся Codeforces Round 927 (Div. 3) — очередной Codeforces раунд для третьего дивизиона.
В раунде используются задачи JetBrains Academy Youth Challenge. Если вы участвовали в нем, не участвуйте в этом раунде.
Задачи подготовлены denk, step_by_step, goncharovmike, ikrpprppp, pashka, Vladosiya и MikeMirzayanov.
Большое спасибо awoo, BledDest, buyolitsez, EgorUlin, Gojova, GrandFruit, Hello_zoka, petyb, scanhex, ibraevdmitriy, shnirelman, SomethingNew, Toy_mouse, Zandler за тестирование раунда.
Как обычно для раундов третьего дивизиона:
- в раунде будет 6-8 задач
- длительность раунда 2 часа 15 минут
- раунд проходит по правилам ICPC, штраф за неверную попытку 10 минут
- раунд рейтинговый для участников с рейтингами до 1600
- после раунда будет 12-часовая фаза открытых взломов
Напоминаем, что в таблицу официальных результатов попадут только достоверные участники третьего дивизиона. Как написано по ссылке — это вынужденная мера для борьбы с неспортивным поведением. Для квалификации в качестве достоверного участника третьего дивизиона надо:
- принять участие не менее чем в пяти рейтинговых раундах (и решить в каждом из них хотя бы одну задачу)
- не иметь в рейтинге точку 1900 или выше.
Независимо от того являетесь вы достоверными участниками третьего дивизиона или нет, если ваш рейтинг менее 1600, то раунд для вас будет рейтинговым.
Всем удачи!
UPD: Разбор
All The Best (Zoom out if not visible)
Did You meant to say " All the best???" not quiet easy to guess in desktop...
All I can see is ??L the BE
Yes, here's the expected look.
"The round is based on problems from JetBrains Academy Youth Challenge. If you participated in it, please don't participate in this round." Does this mean if someone participated in that one ,they would have some advantage in this round?(wanted to clarify it)
Yes, because the problems are the same? It's quite a big advantage if you have solved the exact same problems before
So, isn't it unfair?
Is it unfair if someone knows the problems beforehand? Of course it is, that's why those people aren't allowed to participate
How would you validate that the person hasn't participated beforehand?
but why to validate, the people are very honest here.
They won't participate
Where are the problems of JetBrains Academy Youth Challenge? Asking for a friend.
Shit, I really found those problems. I feel guilty now. 😟
JetBrains Problems with Solutions
I got a youtube ad running lol
Can someone plz tell me why my comment got so many downvotes(genuinely want to know,to avoid/learn/improve)
What is the score distribution?
In ICPC rules, all problems are worth the same.
Can the timing be changed? It clashes with ARC. Moreover, this time is quite awkward for me, as I have an important appointment at that time.
Ohh why not sir. Please tell us when you're free and we'll change the timing according to your availability. Thank you.
Great that u understood. I prefer to have it on regular Cf time so that it doesn't coincide with Atcoder Regular Contest and people like me can go on with their regular Sunday Schedule.
Oh yes lets change the contest date because Six_Seconds has an appointment at that time.
2 of the biggest cp sites should try not to put contests at the same time....especially when one of them has been scheduled for weeks. (Note : leetcode does not count as cp)
Yes but I was just joking about the fact that he said he has an appointment like that makes it more reasonable to cancel the contest.
However tourist can still ak both of the 2 contests. That's awful.
Hey boy, are you a semicolon? Because my program is missing you ;)
bye
bye
bye
guys report him she is a he
as not a tester i would like to solve this round
Finally after a tedious global round which took away my *1800 it's time to relax. Hope to solve A-F
F in 94:59.
This comment has been deleted.
plz read the rules of extended ICPC mode and stop asking such useless questions.
Good start time for Chinese.
But I must finish my winter vacation homework!!!F**k
You can say more about it and I will be happy because I have already entered university and I have no homework this winter vacation. LOL
Originally you also play Genshin
I have a feeling this round will be amazing.
Me too.
If problems are already based on jetbrains youth academic challenge, then it means people already know the problems. Not just that, we can find them from internet also.
Therefore, let's not participate in this round.
problems of this contest are prepared "step_by_step"
My 1st unrated Div 3 !(;
Nice. Wont hurt to be legitimate this time.
Cheater
I would target solving >75% problems.
Good start time!
Yesterday i became specialist so i hope to reach expert again.
I also became a specialist yesterday and I hope not to become a pupil again
Please note the unusual start time: 18:05 UTC+6
The timing is great, but it overlaps with ARC's timing.
Good lucks for everyone!
Good luck to all of my grey friends :D
Redemption time
extra registration ??
.
c Problem is very tough :(
you can even use segment tree.(Thanks to n<= 2e5)
tourist speedrun the division 3 in 28 minutes to clinch first position,then started Atcoder regular contest 45 minutes late and still came 3rd(Standings ). GOAT stuff.
Tourist teaching nubs how it is done just like Dr Disrespect.
I got PTSD because of Problem C
Yup, I think I could've done both D and E but just wouldn't give up C because I thought I was going crazy and missing something way too obvious.
yes , i was not able to solve c , i decided to skip c , and i solved d and e both in contest.
hint: reverse LR string
Can you please elaborate?
https://mirror.codeforces.com/contest/1932/submission/247073793
Same thing, but maybe more intuitive because doesn't require to calculate starting point is to collect the order of indices (kind of topological sorting), and multiply them backwards.
Code
Ugh, I feel so dumb for not being able to figure out C
Silent moment for ones who tried so hard for bigint in E
Was F dp + segment trees?
Yes, although you actually don't really need segment tree
Yeah, I too only used dp
DP: Yes. I did not use segment trees.
didn't need segment tree, but still can be solved
dp + sweep line + multiset
when will i can see the editorial ??
how to solve the E?
For example S = "12345", then the answer is 1 + 12 + 123 + 1234 + 12345 (hope you can find out why it is)
Thanks I'll try that
observed that 3min before end but couldn't implement on time 😥
same 😥
In c++, doesnt the sum of these integers overflow long long for a large testcase?
yes, that's why you need to implement the addition by yourself, and store the digit in an array (that's my solution, I don't know if you can use string or not)
thanks
A key observation is decreasing 10->0 takes 11 seconds, 100->0 takes 111 seconds...
I did see that, but I didn't know how to implement it.
Think about count 1s for each position. Then add them up.
According to the statement, going from 10 -> 0 requires time = 11. going from 20 -> 0 requires time = 22. ... going from 100 to 0 requires time = 111. going from 200 to 0 requires time = 222.
Say you are given string S = 12345 First you make 2345 -> 0 (A) then you go from 10000 -> 0 which requires 11111 time. (B) A+B is the ans.
Let's make 2345 -> 0. First you make 345 -> 0, (A) and then you go from 2000 -> 0 which requires 2222 time. (B) A+B is the ans. and so on.
Thus we can observe each i will be the sum of the prefix digits upto i.
E and D are just implementation didn't like them that much.
went good for a first div3 unrated contest
How this code not able to pass C ? link anyway i solve it using Segment Tree link
I can't figure out why this code fails for C: 247057083
Maybe a long long overflow when calculating the product at the beginning.
Every value of A(i) can go upto 1e4. Now imagine 1e4 values in all the n elements... It will be (1e4)^n and as n can itself go upto 2e5.
So, (1000)^(20005). Do you think It can be stored?
OMG, I thought 1e4 * 2e5 at first,so it will not long long overflow
same
This line is definitely the problem:
Because you could end up with a number as big as $$$10^{8 * 10^{5}}$$$ which just can't fit into a 64 bit integer.
Nowadays Div 3 is harder than Div 2. I don't know if it is only for me or if other users also feel it. BTW happy coding...........
tourist definitely struggled a lot
E got TLE with python but in c++ with making bignum get AC.
Problem F was really nice. Thanks authors. :blobheart:
problem C was quite pleasure to solve
I felt like being Elegia
How to solve C?
I used segment Trees to find product of a range % modulo
Thanks
Just do it in reverse order, then you will multiply instead of dividing the current number.
Also, I've seen your code. If you tried to divide the current number, but in modulo form, you need to use modulo reverse rather than divide it directly
Thanks
dividing in modulo form might not work in general, as $$$m$$$ might not be prime
solve from the back
Am I the only one who is able to solve C but could not solve any other problem.
what is wrong with me... :(
could anyone tell what is wrong in :
Problem B submission
Problem A submission
EDIT: I found the small bugs in my code both above submissions are incorrect
for A i use recursive it's kinda similair to minimum jump problem code
For problem A: you will not be able to move further after two consecutive thorns cells. The answer to the problem will be the number of coins up to two consecutive cells with thorns
Is G just Dijkstra's but edge weights are computed using some x such that a + bx = c + dx, if the two sides of the equation are 2 different platforms?
For all edges $$$(i,j)$$$ we have $$$ l_i + xS_i = l_j + xS_j \mod H $$$. Regroup $$$ x(S_i-S_j) = l_j - l_i \mod H $$$
Find all solutions using the https://cp-algorithms.com/algebra/linear_congruence_equation.html gives you moments when can walk the edge.
Is there a more effective way to do D other than making an if-else chain?
backtracking
No, you can't. Each card can have 32 positions. I wasted 2 hours trying to implement it.
Check my submitted solution it is using backtracking
I imagine you could create a custom comparator and then sort, correct me if I am wrong.
I did the following. I keep the sorted values of the cards for each suit. For the non-winning suits, I can just have the cards beat each other in sorted order, taking 2 at a time until I have 0 or 1 left. If I have 1 left, I'll save it for later. Then afterwards I can just take the winning suit, eliminate all of the remaining ones from other suits, and eliminate the rest in the winning suit the same way as before.
Store in map
Sort card for each suit and greedily remove 2 cards at a time, if there is one card left, u need to match it with any trump. At last u do the same thing for the rest of the trump cards.
Group each card by suits. Then sort by rank for each suits
Now for each suit other than the trump, take two adjacent card rank. If there are some excesses, keep it and use the trump to beat them
Now use the remaining trump suit to battle each other
The impossible case is only when the excesses are greater than the trump suit
I used this comparator function to sort all the cards
Then my logic for the ans is just go from left to right
Spent a long time to understand what problem B wants
You too?
Yup me too, got to know by looking at the sample test cases. Poor writing of the problem statement.
Ac F at 2:14 i can't believe myself
If you need video explanations of C, D, E and F, you can check my video editorials here
Why long long doesn't work for problem C. Calculating the product in long long then dividing the product by left or right whatever element is deleted?
it's long long overflow, a[i] can be 1e4, and n can be 2e5 imagine array all the elements are 1e4 of length 2e5 so the product all of them is (1e4)^(2e5) that can't fit in long long
Because there is a test case which $$$n=2\cdot10^5$$$ and all $$$a[i]$$$ are $$$10^4$$$, then it will be $$$10000^{200000}$$$ :)
BE CAREFUL OF CARD SIMULATIONS 23min D, 7min E
I did F with linear DP, first finding out bar[x] = which spot is the leftmost viable spot on x's right if x is chosen.
Could someone explain how G works?
Can somebody tell me why deque can't solve problem c??? I can't pass test 3.
gonna make integer overflow
Is not accurate, because you need to use modulo inverse, although I think it is not usable in this problem (because m isn't a prime number sometimes)
Maybe i misunderstood the problem? The problem let us get the product of the current array elements,then the let product mod m, lastly remove one element。
You clearly understand it already
Whats wrong with the naive implementation of problem C?
If you have $$$2\cdot 10^5$$$ elements and all of them are $$$10^4$$$, your product will be $$$(10^4)^{2\cdot 10^5}$$$ so it overflows.
D can be solved by using Blossom algorithm, even though it is just an overkill of the problem
Must we use Blossom? I believed the graph wouldn't contain a cycle and is thus bipartite, so I tried to find the matching with max flow. However, I failed on test 3.
I suppose that it can be solved using max_flow algorithms, but max matching is more intuitive, i think
why greedy does not work for F? :(
how you suppose to do it greedily?
2 4, 5 7, 10 11
2 6, 7 7
4 5
Try this input:
1
7 5
7 7
1 3
6 6
3 7
5 7
The answer is 4 (feed the cat at step 1 and 7)
C problem is really hard for Div3 XD.
p.s Who solved this problem without trees? :)
I'm curious about the segment tree solution, can you explain a little bit?
Very simple problem if you think using segment tree.find my solution here..
It’s pretty simple just compute if offline in reverse order. Start from index after n-1 operations. This index is both l and r. in reverse order, if operation is R, append the righter value and increment.
yes very simple if you know how to solve it. not so simple if you dont.
basically the reverse approach is hard to think of but it is not the only one you can use segtree and just recompute again for every range thanks to segtree this will be done in n log n instead of n^2
I solved it with sqrt decomposition
Start from reverse. Start from one element that is going to be remaining at last, after removing every other. Then keep multiplying second last, third last… while taking modulo. And then print array of answers in reverse
I loved Problem E,Great contest
very good D and E problem,makes my rating down down down.
Nice contest! Anyway here is my solution for problem F :
Let call cover[i] means the number of segment that cover point i. We can find this by using a multiset.
Iterate from 1 to n. Let's call dp[i] : Consider to position i, what is the maximum answer can we make
Hope it make sense!
TYSM, that really help me
Слабые тесты фуу
Problems E & F were great! Nice contest! I enjoyed it!
Why is this impossible in problem D ?
1
S
7S 3S
Since both belong to trump suit, and 7S has a higher rank, it can beat 3S. ??
It is possbile, sixth line of output.
It's not impossible
Did anyone use DP to solve E? I usually don't use Python and thus had TLE at case 6. Submission
280ms
How to solve Problem G?
Here is my solution:
For each passages, find the times in which the levels of the connected platforms are the same. To do so, you need to solve the equation:
You can solve this equation using the extended Euclidean algorithm. Define $$$C = \frac{l_v - l_u}{\gcd(s_u - s_v, H)}$$$. Note that if $$$t_0$$$ is one solution, then $$$t_0 \pm C$$$ is also a solution.
So, for each passage, you know you can cross it if and only if $$$t \equiv t_0 \left(\text{mod } C\right)$$$.
Then, you can solve the rest of the problem using a simple modified Dijkstra algorithm, where when crossing a passage you update the new distance as $$$t_0 + C \cdot max\left(0, \left\lceil\frac{t_0 - curdist}{C}\right\rceil\right) + 1$$$.
Can you please explain this, we can find t using the extended euclidean algorithm but how will we get the smallest t ?
If $$$d = gcd(a, b)$$$ and $$$(x_0, y_0)$$$ is a solution to $$$ax + by = d$$$, then the general solution to $$$ax + by = dj$$$ is:
Thus, the solution with the smallest value of $$$x$$$ would be $$$\left(x_0j \text{ mod } \frac{b}{d}\right)$$$.
why is it x0j + (b/d)k and not x0j + bk, this will also keep the equation balanced, x0j + bk and y0j — ak
I am sorry I looked at many resources but no one explains this if you could please explain it
Honestly, I just memorized that as a fact without giving it much thought. However, if I have to try to justify it, it would go like this:
If we substitute $$$\left(x_0j + \frac{b}{d}k, \, y_0j - \frac{a}{d}k\right)$$$ in the the equation $$$ax + by = dj$$$, we have:
As for why we choose $$$\frac{b}{d}$$$ and $$$\frac{a}{d}$$$, it is becuase they are the smallest integers which can cancel each other out as above.
For example, note that $$$x_0j + bk$$$ also gives us a set of valid answers. However, they don't give us the full set of answers. More formally:
Thankyou so much,this was just basic LCM calculation,i completely understood this now
tourist used dp just to solve a Div3A lol 246990951
ingenious troll, I have 0 clue why and how that even work 😂
B getting hacked like potatoes!!
do you know why ?
If you try "brute force", by multiplying ai by 1,2,3... until big enough, you will TLE, for example if a1=1e6, and a2...a100 = 2, t=1000
Dunno about you all but this is imo very confusing descrption:
According to the legends, for the apocalypse to happen, the signs must occur sequentially. That is, first they wait for the first sign to occur, then strictly after it, the second sign will occur, and so on. That is, if the i-th sign occurred in the year x, the tribe starts waiting for the occurrence of the (i+1)-th sign, starting from the year x+1
Why use words sequentially? Why use "strictly after". If there werre not example input/output I would think that you have to find years p, p+1, p+2, ..., p+n such that first sign happens on p, second sign happens on p+1 and so on.
I "solved" only by guessing pattern from samples
me too.
Still got hacked though .
I tried solving C by calculating product of the range left after each operation using sqrt decomposition (247032959). It was giving TLE. Is there something wrong in implementation ? Because a same problem with similar constraints (243011064) got AC. I know it's not a good approach. It could be solved much simply but that's the approach I thought in contest.
I solved it using sqrt Decomposition and it got accepted. Your Implementation might be messy and slower.
Here is my submission : https://mirror.codeforces.com/contest/1932/submission/247026530
Why is B getting hacked?
1000000 1 1000000 1 1000000 1... causes tl for solutions that try to linear search next year every time
one of the best div 3s ever
thanks a lot
HackForces
Editorial when?
MikeMirzayanov I have an optimization for system testing. Instead of testing on whole set of test cases again, test just on new test cases because anyway the submissions which are being tested have passed the pretests. This can potentially speed up system testing.
Getting the system test done is like waiting for a snail to finish a marathon!
A testcase for A question has been missed in the system testing as well. The case is when the staring point is a goldcoin.Many users dint write the code to cover this edge case.Please look into it.
Starting or the ending point?
starting (the first cell)
It is guaranteed that the first cell is empty.Lesson: Read the input section clearly & completely.
Anyone knows when Editorial will be out?
Why does this C++ segment tree for problem C get a TLE? https://mirror.codeforces.com/contest/1932/submission/247091172
The code copied here:
You should pass vector through pointer in the build function. That is, replace the following:
with:
when's the editorial come out?
When is editorial?
When will the editorial be posted
pashka MikeMirzayanov Publish the editorial Bro.
Where can I get solutions of this round??
It haven’t been posted now(though it should have been posted), you can view other’s submission instead.
Hello I think this has been a mistake:
That contest was unrated for me and I didn't even got in the contest in the start time and I didn't even care? why would I cheat when it's unrated? and the codes aren't even alike like WHAT?? The algorithm looks alike I agree but the code doesn't like why would I even cheat in an unrated contest???
Sorry !!
Correct me please, Are you talking about anything I did? that solution you mentioned I am not even aware of the question!!
if I have misunderstood please let me know, I am sorry for my wrong understanding then!
no
Idk, why would you cheat in the unrated contest?
I haven't that's the reason I'm appealing
Dude I asked you why, not if you did it
I didn't bro, there doesn't exist a reason for a thing that hasn't happened
Bro, again, I didn't ask you to explain cause-and-effect relationship, I asked why you'd cheated in the contest
I think u're not getting the point I DIDN't CHEAT so I don't have a reason to cheat in an unrated contest
So what is your final answer?
I don't have a reason for something I haven't done
end of conversation
So you cheated because you didn't have a reason to cheat? But that makes no sense!
sounds like a u problem, end of the conversation
Well, it wasn't really a conversation since you pretty much ignored my question
Bro, When I haven't cheated, how can I answer it?
U think I cheated and asking me for a reason which I'd be doing the same in this situation, but I actually didn't cheat
Ok, I'm done now, I was messing with you, for a reason ofc
If the reason was get me to admit, I don't lie
peace
good contest
the question E has previously appeared in Atcoder Beginner Contest Question 233 E. Exactly the same