“It is not important to be better than someone else, but to be better than you were yesterday.” — Master Oogway, Kung Fu Panda
Hello, Codeforces! We are proud to present Codeforces Round 929 (Div. 3), and we hereby invite all of you to take part in it. This round will start on Feb/27/2024 17:35 (Moscow time). You will have 2 hours and 15 minutes to solve 7 problems. The penalty for a wrong submission is equal to 10 minutes.
This round will be rated for participants with ratings lower than 1600. However, all of you who wish to take part and have a rating of 1600 or higher, are welcome to register for the round unofficially.
The round will be hosted by rules of educational rounds (extended ICPC). Thus, solutions will be judged on preliminary tests during the round, and after the round, it will be a 12-hour phase of open hacks.
Remember that only the trusted participants of the third division will be included in the official standings table. As stated in this blog, this is a compulsory measure for combating unsporting behaviour and upholding gracious professionalism. To qualify as a trusted participant of the third division, you must:
take part in at least five rated rounds (and solve at least one problem in each of them)
do not have a point of 1900 or higher in the rating.
Regardless of whether you are a trusted participant of the third division or not, if your rating is less than 1600, then the round will be rated for you.
The problems were authored and prepared by erniepsycholone, snowysecret, dbsbs, jerryliuhkg, lomienyeet, and our beloved coordinator Vladosiya.
We would like to thank:
Vladosiya for his high-speed coordination;
arvindf232 for Legendary Grandmaster testing;
step_by_step for International Grandmaster testing;
physics0523, culver0412, AHappyPotato for Grandmaster testing;
pavlekn for Master testing;
moonpie24, anthony123, mariowong123 for Candidate Master testing;
peshkoff, ksodp, SashaT9, Elison, MoLotfi for Expert testing;
DBSHoShunNgai, Doncho_Bonboncho for Specialist testing;
CannotPupil, KyleLeungHS for Newbie testing;
MikeMirzayanov for creating Codeforces and Polygon.
We hope that this contest, regardless of your background, rating and result, will increase your exposure to competitive programming and make you better than you were yesterday. Have fun!
UPD: Let's continue the streak of announcements with photos of the authors. This time with our coordinator and testers :)
UPD2: We discovered the screencast from Um_nik a short while before the end of the contest, and it had around 400 views by the end of the contest. Round is still rated, however, people who have used his solutions will be punished.
UPD3: Editorial is out
As a part of the problemsetting team, we unfortunately cannot offer any competitive programming socks as prizes.
Doby wouldn't be happy about that
LMAO, good one.
{Get's a -200 Δ} "There are no accidents" $$$-$$$ Master Oogway, Kung Fu Panda
As a coauthor, I encourage everyone to participate, regardless of your ratings. I also hope you enjoy the problems. :)
Wish to become an expert with this round :)
As a grandmaster testing...
As an international master, I am disappointed that there has been no international master testing.
Time to unleash the inner Kung Fu Coder and make Master Oogway proud! #CodefuPanda
Will become Expert after this contest
As a tester, I cannot pupil
As one of the testers of this round (i definitely dropped to specialist on purpose to get my own line in the round announcement), I unfortunately did not receive any competitive programming socks for my testing efforts.
After rating rollback i became Expert so this is my first Unrated Div3 :)
Random meme:
tru
I think rainboy is also a genius
definitely, rainboy is one of my favorites :)
.
No offence to rainboy but there are other coders which surely belong in the Crazy Category.I have seen 2 of them (other than rainboy of course). Dukkha AND kaiboy. Comment if you know some other crazy and genius coders.
kaiboy is rainboy’s younger brother. I don’t know about dukkha, it might be an alt.
dukkha is rainboy's elder brother.
Thanks for informing me, Akshat369 and hashman
what is bro cooking
Why downvotes...
I'm going to be crazy at some point 😉
Alpha
Am I crazy?
no, you are Patrick Bateman
xD, true
5th type
I Hope To become a SIGMA — PUPIL this round ;)
Good luck, future sigma
but sir i think real genius is sporfky master wch 1226 !!!
he now grandmister !! he ver y much inspirin for fapipotato!
thank u so much coddfrces!! thx u so much sparky moster!!
much love, fapi potat O
looking at the number of submissions i made in the last contest. I might very well be on my path to becoming a true SIGMA.
maybe you can translate the saying into master turtle.
As a participant, CR7 is GOAT.
Messi == Ronaldo == GOAT and GOATS don't fight.
nice ạ
As a tester, I encourage every fellow programmer participating in the round to look at every problem to prevent skill issue. But anyways I hope everyone participating can have fun and hopefully learn something from this well crafted round~~
(The problemsetting team has genuinely dedicating a whole load of time to make sure this round runs smoothly with great problems!)
NEW DIV 3 ROUND YEAHHH
so many dbs students no kgv fame :( (dbs op)
Master Oogway quote beautifully encapsulates the essence of personal growth and self-improvement. Focusing on our own progress rather than comparing ourselves to others is a valuable mindset to adopt. Each day presents an opportunity for us to strive for excellence and become the best version of ourselves. Thank you for sharing such a meaningful perspective!
As a tester, I wish you high rating and hope you achieve the rank you aspire to be :)
Are questions easy?
you'll see
I know.
The secret ingredient is... !
Practice — Master Oogway
Actually, the secret ingredient is... !
Nothing -- Mr. Ping (Po's adopted father)
Big respect to Master Oogway though.
It's time to make yourself and you better♥♥♥.
"Goodluck.", — Master Oogway, Kung Fu Panda.
ok
I hope I get blue :)
the quote hits really hard...
Yes
i wish i could solve A,B,C.
DBS forces
Finally unrated for me!
GOOD LUCK !!!
Good Duck <0)
Cumulative sum of their age is less than me or they looks very young?
I think we should welcome our 150+ y.o. participant.
Kidforces
Talentforces!
Abilityforces!
Nice, new round, new training. BOTAAAAAAAT
Finally, another round where I can try hit pupil!
Good Luck for everyone!
Ohhhh,I see Atletico Madrid fan
I hope to solve AE
Kids are writing problems for a grownup like me. I guess that is the benefit of receiving a good education right from your childhood. The first time I used a computer was when I entered college :(
I predict that there would be a problem involving some range queries or stuff like that probably C or D It would have a simpler solution but will be overkilled by many using segment trees or something similar.
This didn't age well.
I hope to successfully enter the youth league tonight ：）
Hoping for a fun contest.
give me a chance that making my name become yellow!
Thanks for continuing streak of putting authors pictures on the contest blog
It's a good thing they have decided to keep the streak going.
Good luck to everyone!
Bro, please give job in microsoft
Hope fast ABCD
Mathforces
NumberTheoryForces
EFG are ok
Yes but BCD is not ok
Postpone them (like I did with B), solve the ones you like first to warm up.
LOL, umnik_team uploaded the solutions before the end of the div
Why did you write this here!? Now there will be a lot of cheaters!
um_nik is 1 hour ahead of us(iykyk)
WTF is this? why were the solutions posted before the round ends by Um_nik??? This is not fair. I hope they dont make this round unrated because of this.
The problem-setting team has acknowledged the issue, and I have already tried my best to contact Um_nik on the issue a while ago to try to remove the video. I also hope the round doesn't get unrated :(
What is the use of removing now? The damage is already done
the video was there for more than 30 mins too, why didn't here remove it earlier
We contacted him before the round ended of course.
Most of the participants wouldn't have even seen the video. Hope contest doesn't get unrated (even though I couldn't implement E), as I truly enjoyed the contest.
deleted
..
Thanks for the fast editorial!
Very fast =)
"If I don't have a rated contest, then no one has a rated contest."
I hate myself for not reading problem E correctly I was able to do it in 10 min once, I read the statement properly...
anybody did the same mistake?
is problem E binary search?
I used ternary search
yes
yup. DP to calculate sum i -> j. then binary search
search over what
to find out K such that Math.abs(aL + a(L + 1) + ... + a(K) — U — 0.5) is Max
why does that function work
n = 1 => U
n = 2 => U + U — 1
n = 3 => U + U — 1 + U — 2
...
n = m => U*m-(1 + 2 + .. + m-1) = U*m-(m-1)*m/2 = -1/2*m^2 + (1/2 + U) * m.
It max when m = 1/2 + U
=> find K such that aL + a(L + 1) + ... + a(K) closest to m or 1/2 + U
yeah sorry you're right, I misread the problem statement. shit. this is so much easier than what I was tryna do
I was able to do it using binary search
yes, binary search on convex function.
you can see my code for reference:
auto solve = [&]()->void { int N ; cin>>N ; vector<int>A(N); for( auto &x : A )cin>>x ; int Q ; cin>>Q ; vector<int>P(N+1,0LL); for( int i = 0 ; i < N ; i++ ) P[i+1] = A[i] + P[i]; auto range = [&]( int a , int b )-> int { return P[b+1] - P[a]; }; auto task = [&]( int L , int U )-> int { int l = L ; int h = N-1 ; int mx = INT_MIN ; int res = L-1; auto f = [&]( int m)-> int { int sum = range( L-1 , m ); return sum*U - ((sum*(sum-1))/2); }; while( l < h ) { int m = (l+h)>>1 ; int y2 = f(m); int y1 = f(m-1); if( y1 == y2 ) l = h = m ; if( y2 > y1 ) l = m+1; else h = m-1; } for( int m = l+1 ; m >= l-1 ; m-- ) { if(m >= L-1 && m < N ) { if( f(m) >= mx ) { mx = f(m); res = m ; } } } return res+1; }; for( int i = 0 ; i < Q ; i++ ) { int l , u ; cin>>l>>u ; cout<<task( l , u )<<" "; } cout<<endl; };its just a linearly increasing function.. the score is the convex function... only the index is needed so you can just use binary search on prefix sums
yes i saw after the contest, did not realise it in heat of the contest, as I misread the problem wasted 1 hour on completly different problem.
problem e was truly painful to implement
can someone tell me where it is giving wrong answer 248621389
Actual answer for 8 4 64 is 6 but your code produces 7
thanks
I used logic similar to finding peak element in array. But got WA. Could anyone please point out the mistake in my code?
Submission : https://codeforces.me/contest/1933/submission/248632005
Edit : Found the mistake. I was subtracting a[low-1] instead of a[l-1] :(
Thanks for the hint and your code,I tried implementing using peak element concept, but got stuck in the code, actually I did not initialize my ans to l and also did not make neighbour= -INF if they did not exist and your code came to my rescue.
It was a good bluff to require us to answer modulo 998244353 in problem G. (I intuitively knew that the answer could not be large given the harsh conditions, but because of this requirement, I was not sure of my consideration that there are at most 8 patterns even after writing an experimental code with a brute force.)
great contest! i really enjoyed A,B,C,D,E, but couldn't implement bs in E, I need to practice more bs problems( Anyway great contest!
anyone can explain the test case in problem G ?
Um_nik has uploaded a video about solving this contest before the contest ended: https://www.youtube.com/watch?v=Asqk4kXi8os&ab_channel=umnik_team . Will this contest unrated?
There is no point in making the contest unrated. Cheating happens and solutions get leaked on Telegram and YouTube in every contest.
But this is a public solution from a LGM while the contest is running. Anyone can AC all 7 problem with this video.
I dont think link was public during the contest.
I think it should be unrated because there used to be cheating to some level but this is not done, i was able to solve 4 in div 3 which is good enough, still suffered 44 rating decrease because of soo many cheaters. Ratings should be rollbacked for this contest. This was too much!
Brooooo my stupid "print" statement costed me PROBLEM-C ripppppp
print
without
This could have been the greatest clutch of my life but NOPE. I want to jump off a cliff :((
Hints for all the problems before the editorial comes out.
A: Collect all the negatives in one subarray.
B: Maximum answer can be 2. Think about the cases when 1 and 2 will be answer.
C: What if we fix values of (x, y)? Also, the value of k will not be always distinct.
D: What if you keep minimum element at first? What if there are multiple minimums?
E: The sum is increasing upto a point and then it decreases. It starts decreasing after the (u + 1)-th section.
F: Firstly, coming at the same position again is not optimal. Secondly, we don't need the UP move until the last column.
G: Constructive problem, try to come up with a pattern using second test of sample. Also, the answer can be max upto 8, ignore the modulo.
Thanks to the authors for some very interesting problems.
I liked problem F a lot, it looks a bit intimidating at first, but upon several observations, it boils down into an easy problem.
Happy to hear that you liked F a lot (I wrote it) Thank you very much you have made my day.
Hopefully, I don't get downvoted by saying this... ik this task kinda was a nightmare at first sight for some of you, but hope it was an interesting and insightful task. Hope it wasn't that hard to understand as well, I already tried to draw better graphics for the explanation.
Anyways, we will try to get the editorials out as fast as possible :)
Keep up good work making problems interesting to think about and easy but not boring to implement.
No no, I think it was fine for everyone. And, the graphics were actually cool.
I really liked F :> Might even take inspiration from it to create some educational DP problems myself
hi, about problem F, do we really this observation to come up with a solution,
"Secondly, we don't need the UP move until the last column."
I think we can use simple bfs to reach the end
The observation is correct, but there are also other ways to realize such an observation which will be mentioned in the editorials. Of course there might be alternate solutions that also work, but having this observation does simplify the question a lot and can be done through dp or bfs.
yeah, I do know that, just wanted to know if someone solved this by just first obs,
from each point, we move to three possible cells(up, down, right), using bfs we find the ans for last cell
In problem C, Why I am getting TLE in this code. It is O(max(13,sqrt(100))+ 3*10^3) .
My submission
You forgot to add the complexity of creating a 10^6 sized vector in each testcase.
Thank you. I realised that I don't need to create those arrays .
In E, how can you say that the sum is a convex function?
you may have misread the problem description just like i did. among tracks the decline by one continues.
Could you please explain why we dont have to use the UP move until the last column, it will be very helpful
When you're doing the UP move, your position relative to stones isn't changing, so basically the whole setup is same in a rotational manner. The only thing that changes is relative position of ending cell, which you can also change when you're in the last column.
Oh,now I feel dumb, thankyou so much
someone explain what does it mean by seeing the grid in the pov of grid? Everyone says see the grid as static? Someone kindly explain
Is this one about turtles?
Every question is about a turtle.
Originally we had a storyline, but it was decided to be removed in the end to improve the task's clarity. The idea came from a few sources. The first one is because the old workplace or "home" of my school's robotics team (I was the captain last year) was next to a turtle pond, and so I have a strong love for turtles :) FYI, each of the teachers having their seats next to the pond were also called turtles with different nicknames for each of them. The second reason was that we liked Master Oogway in the movie Kung Fu Panda, so we thought it would be a good choice to use it as a theme, both silly and inspirational.
Don't know! Should I be motivated or demotivated?! after seeing the problem setters...:/)
I could not even solve B. Every one here is discussing about problem E
Problems: Turtle
Editoral: Rabbit
W contest , W younglings who made these questions ,Hope its not gone to waste cause of the stream upload
Can anyone give any counterexample where this submission 248545787 doesn't work for C?
fastest editorial ever seen
I performed well in this contest but the contest is unrated for me because I became exactly 1600 after the rating roll back.
If I was 1599 I got +70 at least :)
suffering from success
is this contest getting unrated for some people ?
No. but the Div3 contests are always unrated for above Expert.
https://codeforces.me/contest/1933/submission/248622479 can anyone tell me what is wrong with this code for problem E
.
If this is true I think CF can spot cheaters and skip them. so no worry :)
i mean people always post the solutions on youtube while the contest is running and have alot of views as well. i don't understand why when umnik do it it will be unrated , F and G don't have a lot of ACs anyway.
[deleted] it's not intentional ,it's a mistake and he apologized
Edit: it was a great contest ,hope to see more such contest from authors
nvm
Few stupid guys!=whole india Stop using "Indians" "Russians" "Chinese" Do you compare umnik with this guys ? Definitely not
ok buddy I'll edit the comment and remove indians since this annoyed a lot of people.
No hate bro ,what you said is correct there is a mass cheating in every contest and we can't stop them
I know that umnik is not one of them
but we can't judge a country by some brainless individuals
really liked both F and G, they are great! though $$$n, m \geq 5$$$ and strong sample little bit spoiled main idea of problem G, IMO.
I guess n = 3 and large m is way harder than the current problem, thus they made such constraints.
hmmm, yeah, that's fair
Btw this is how we can solve for small n and large m.
It's not difficult to see that soln is a linear recurrence with period atmax
4*n.We can bruteforce in
O(2^20)forn<=4and the plug in linear recurrence solverPlease don't make this one unrated:(
In C, l could have been much larger.
UPD2: Since the editorial is not out yet...
2 options: to negate or not to negate. For a negative number, negating it is optimal and vice versa. The answer is $$$\sum{|a_i|}$$$.
It's easy to see you never need more than 2 operations. Let $$$sum = \sum{a_i}$$$.
0 operations: $$$sum$$$ divisible by $$$3$$$
2 operations: $$$sum\bmod 3 = 1$$$ and there is no $$$a_i\bmod 3 = 1$$$.
Brute force. Iterate over all possible pairs of $$$x$$$ and $$$y$$$. Be careful of duplicate $$$k$$$s and you can store distinct $$$k$$$s with a set. Time complexity $$$O(tlog(n)log(log(n)))$$$ (This looks ugly and I wonder if my solution is optimal)
Original Post: Solved ABCDEF and I had no non-trivial idea for G. I enjoyed this problemset, and DEF are good problems in my opinion.
D: Suppose the smallest element is $$$x$$$. If there is only one $$$x$$$, place it at the front and the result is $$$x$$$.
If there are more than one $$$x$$$: if there exists some $$$y$$$ so that $$$x \nmid y$$$, begin with $$$y$$$ $$$x$$$ and we have $$$y\bmod x < x$$$, which will be smaller than everything else, and the answer is $$$y\bmod x$$$. If all other elements are multiples of $$$x$$$: begin with $$$x$$$, and you will get $$$0$$$ at the second $$$x$$$; begin with other elements, and you will get $$$0$$$ at the first $$$x$$$.
So the answer is No only if there are more than one smallest element and all others are multiples of that.
E: The result is optimal if you can run exactly $$$u$$$ or $$$u+1$$$ segments. Build a prefix sum array $$$sum[n]$$$ and binary search $$$sum[l-1]+u$$$. Then check the 2 or 3 elements around it, do not forget bound checking.
F: If the grid is relatively static, the robot can move 2 tiles down, 1 tile down-right, or stay in-place. The target tile moves down 1 tile every second. We can run a BFS from $$$(0,0)$$$. After reaching each tile on the right edge of the grid for the first time, we can opt to wait for the target to come. Finally choose the best among all n tiles on the right. $$$O(nm)$$$
UPD: G upsolved. The ST was slow and I submitted 1 hour after finishing coding.
If 2 adjacent positions are both circles, prove that all 6 positions adjacent to them are squares.
int pattern[8] = {0x55aa, 0x5aa5, 0xaa55, 0xa55a, 0xc3c3, 0x3c3c, 0x9696, 0x6969};Please tell me what is wrong with my implementation of E. I can't think of anyother way to implement it and also cannot make this implementation work. 248638966
why are you going up to u+1?
I may be wrong about it. Is that the issue ? I tried submitting with
critical = uwhich also doesn't work.if two index that are adjacent make same answer then you should take the lowest one. I think in the first test case your answer is giving wa. 3 1 4 1 5 9 for l = 1 and u = 8 your code gives r = 4. But r = 3 also gives the maximum sum. You should go upto u and check the next index also which is res+1. if it makes greater sum then output res+1 otherwise output res.
see my solution.
Now I got it, thanks a lot. I thought of checking neighbouring elements to the r that I found, also but it felt very hacky to me and did not try it even once. :(
Good hint for F. I was able to code it up after looking at your hint
begin with other elements, and you will get 0 at the first x. can you explain this with proof? Thanks in advance
If the first $$$x$$$ is at position $$$t$$$ ($$$a_t = x$$$) , and the result before the $$$i$$$-th operation is $$$b_i$$$, where $$$b_i = b_{i-1} \mod a_i$$$. We want to prove $$$b_t = 0$$$.
Initially we have $$$b_1 = a_1$$$, and $$$x \mid a_i$$$ for all $$$i$$$. So $$$x \mid b_1$$$.
Prove that $$$x \mid b_{i+1}$$$ if $$$x \mid b_i$$$ and $$$x \mid a_{i+1}$$$.
This way we get $$$x \mid b_{t-1}$$$ so $$$b_t = 0$$$
For Problem-F
Can you please help me :
lets say that we reached the cell a[i][m-1] ...
Why currAnswer = dist[i][m-1] + abs ( n-1 -i ) is not correct ?? ( where dist[][] can be found by simple BFS ) and thus the final answer will be Minimum over all i...
How to correct it ?
What if you walk down and there are rocks in your way? The "wait" is to go up all the way(i.e. stay in place from the grid's viewpoint)
The best insane problem D ever !!
Great Contest
Please don't make contest unrated. Just check for plagiarism for problems E,F,G that were send last 30 minutes with the umnik's code from youtube.
in prob C https://codeforces.me/contest/1933/submission/248626484 I am getting wrong answer from codeforces judge but if I am testing the wrong test case on my local machine it's giving me the right answer? WA on test case 2 40th test 8 4 780
why Um_nik why
The contest was very interesting, thanks to the organizers of the contest. I just found this stream where Um_nik broadcast the last ~1 hour of the contest. I felt very sad because some of the participants cheated and one of the great codeforcers has ruined contest. In fact, it's not about cheating, but about respect for the creators of the contest.
Dear organizers you did really greate job!
heres why i solved this G 2x faster than rainboy.
https://imgur.com/dKUPRJ3
sirs
thank u the much for this roudn !!
but fapipitito notice G is pretty specil?? fapipotato confused !!
fapipotato find solution near end but cannot code fast be cause hand weakk :((((
i liek all problom and this very high qualiti round!!
mcuh love and look forward to more future later round from u guys!!
fapi potato
:)
Really Great Problemset!
I did a BFS implementation in Problem F. Sadly, I got a TLE on Test 12. Can someone point out how to avoid it from my code?
I did same. i did not observe that robot will move up only in last column :(.
so move up only in last column will reduce your time complexity from O(n*n*m) to O(n^m)
Ohhh man. This ignorant habit of mine just sucks af! :") Thanks btw.
Um_nik you are very bad
Everyone makes mistake
I guess Master Oogway's words work again, "There is always something more to learn. Even for a (Legendary Grand) Master" lol.
And despite such issues may be problematic, I think we shouldn't put all the blame onto Um_nik as him doing his videos were for a good cause in teaching programming, just that he may have accidentally posted it early. Additionally, he has already apologised as well and I agree everyone makes mistakes, me included. Hopefully, such issues will be prevented in the future. :)
but one thing i would say, umnik got really good taste in music xD!
Problem F is Awesome.
A bit different from usual problems.
was stuck at e, but then saw huge num of ac in E, around 4500 solve, now really upset after seeing the comments.
e is still not hard despite the cheating . you just have to find the first sum that's bigger than u, using binary search and find what's bigger this value or the one behind it
True. E was easy, but as i become super saiyan level dumb durning contest, i forgot to check the values behind
it happens don't worry . keep grinding
Problem F: BFS with one tricky observation. In this problem, the robot will move upward only when it's in the last column. Due to this constraint, the straightforward Depth-First Search (DFS) approach might lead to Time Limit Exceeded (TLE). This optimization should help improve the performance and prevent TLE.
I tried DFS, but getting WA 248632066. Any possible reason you could tell?
I haven't viewed your code but I don't think DFS will work, because BFS guarantees the lowest depth when each node is first visited but DFS does not
You don't need to ever revisit any cell, so it doesn't matter BFS or DFS. AC with DFS
You have to revisit cells if you are doing DFS and what you have linked is BFS
Whether it is a B of D FS is determined by the order of traversal, and not the function name or use of recursion.
Okay, the order of traversal in your linked solution is bfs order and if it was dfs order , you would need to revisit cells
does this satisfy your highness?
No, because it's untrue
my bad. didn't realise your 'q' was not a queue but a vector
Can anyone tell why my code for E is giving TLE on 8th TC after applying Binary Search. 248643885
you are passing vector by reference in binary search. use vector & pre
Accepted, Thanks.
Can anyone try and hack my submission for F? I just did a O(n^3) BFS and used bitset to store visited. It passed somewhat comfortably but I'm wondering if there's a case where it blows up. https://codeforces.me/contest/1933/submission/248595937
are u checking upward in all columns ??
Yes
i also did BFS. My Submission. But got TLE. How??
Because you are using a set for used values
So your solution becomes something close to $$$O(n^3log(n^3))$$$
Hacked.
I generated a $$$1000 \times 1000$$$ grid with all $$$0$$$'s to greedily maximize the number of neighbors of each cell.
Would it also work for my solution? It's also n^3 bfs
Thank you
I just added a condition where I move upward only in the last column and the runtime improved significantly, I don't think it can be hacked now. I think this implementation is very interesting because you are essentially doing the n^3 bfs with one little optimization for the transitions and the O(n^3) memory being reduced by a factor of 32 with bitset making it enought to pass the limits. https://codeforces.me/contest/1933/submission/248663273
bitsets are so dumb bro if u were really that good u would've figured out something easier noobie
shut up bro
hey friend,
just wanted to drop a quick note to say sorry for what went down the other day. i know i messed up and i feel really bad about it. didn't mean to hurt your feelings or make things awkward between us. i hope we can talk it out and move past this. let's grab a coffee or something soon and chat about it. again, really sorry, mate.
take care, [Your Name]
Nah man , he is onto something
I think with your new optimization the time complexity actually becomes $$$O(N^2)$$$, and your space complexity would be $$$O\left(\frac{N^3}{32}\right)$$$ as you have stated.
Moreover, I noticed that with your new optimization you don't even need the 3rd dimension for the
visitarray, since I think you can arrive at cell $$$(i, j)$$$ only if the time $$$t \equiv i + j \quad (\text{mod } N)$$$. So, you can optimize the space complexity further to $$$O\left(\frac{N^2}{32}\right)$$$. (see https://codeforces.me/contest/1933/submission/248668841)The time complexity is still technically O(n^3/32) as I need to initialize the bitsets, however your idea fixes that issue. The 100ms saved is most likely just due to the fact that there wasn't a need for so much data to be initalized.
It was indeed a good round, I just hope it doesn't get unrated.
I almost gave up doing competitive programming. After 19 months almost I thought, let's start again. I was reading the explanation of test cases of problem B. And I Couldn't even figure out how that explanation matches the output. Suddenly I see a message popping up, saying there was an error in the explanation of Problem B. How could the problem setters or the testers miss such error I don't know. I was totally frustrated and couldn't even focus anymore sadly. Such a frustrating experience -.-
You should build up your mentality for competitives
I hope the round doesn't get unrated.
really thank you It was a good math contest Just remember from now on, this is Codeforce not MathForces
Was this really a Codeforce contest, 4 math and number theory questions in a row
Most CP problems require math on some level. Maybe try learning it?
YES Most CP problems require math on some level. but all of them doesn't have math tag
oh bro Now I want to teach you something very friendly In Codeforce, tags are set for many questions that show the key ideas of the solution and the algorithms necessary for the solution. So it's better to learn how to use this site before you come and comment
help in problem C
here L = k * a^x * b^y, so, K must be a divisor of L. Now i need to check which of the divisors can be represented in (a^x*b^y) and count them. What is wrong with this idea? i think it shouldn't give TLE. My Source Code (WA on test 2)
Try putting your "k" values in a set. Maybe that helps.
You can keep the K values in hashmap for quick checking.
In the code, you are only considering the case where a^x==l, or (b^y)==(l/a). Instead of thinking for 'k', try to generate all the values of (a^x + b^y) and then check if it divides l. Store the value of corresponding 'k' in a map or a set if it does. To avoid overflow issues you will need to consider the values of 'x' and 'y' up to which a^x and b^y do not exceed 'l'.
Thanks for making the round rated.
Thanks for problem E, I finally learnt how to implement ternary search.
What's the idea?
My answer won't be perfect, but I hope you understand something.
If you solve the problem naively, you will iterate from r := l, and keep increasing r, as long as your answer increases. Suppose the best answer is at r=R. Then, the elements you will have are u,(u-1),....,(u-x+1) such that (u-x+1)-th element lies in the R-th section. For this answer to be optimal, you must keep increasing until the values in the Rth section don't become negative. i.e. sum of all of u,(u-1),...(u-x+1) is non-negative.
This behaves is like a convex function. The answer first increases, then decreases. So you can use ternary search to find the maxima of the convex function. To find the index, you can just use standard ternary search, and to find the sum of u+(u-1)+...+(u-x+1), you can use arithmetic progression formula.
A bit sad that I couldn't code the E problem in time, the prefix sum and a binary search was an obvious idea of the solution. Good contest tho, I assume that it is a perfect example of a well elaborated div3 round. Many thanks to the authors, it was a pleasant adventure!
Child labor... unbeliavable.
why trivial binary search not working on E! like lower_bound(pref.begin(), pref.end(), pref[l] + u) AAAAAAAAAAAAAAAAA!!!!
i mean that's literally my ac solution so idk bout you
you also need to think about the r+1 and r-1.
https://codeforces.me/contest/1933/submission/248653337
Why my this solution is not working for E? im checking mid and mid+1
Fixed. See 248687605
Wow.. thnks a lot.. btw can u pls explain why ans is coming at lo?
I am trying to hack Problem F using above generator. But got this Verdict "Validator 'validator.exe' returns exit code 3 [FAIL Expected integer, but "#include" found (stdin, line 1)]". Someone help me find the error.
You have to find and use the "generated input" tab in the hacking interface.
Besides that, you have to NOT print the trailing space in each line. Your test will be validated and then given to contestant, who doesn't have the obligation to work on malformed input. The validator does not fix formatting for you, it just reports that formatting is wrong (easier this way).
I think my code is wrong in problem D 248569476 can someone hack it
Thanks for keeping the round rated ❤️. It will encourage honest participants who invested their time in participating in this contest.
"Round is still rated"
Lets goooooooooooooooooo
You know u cant detect cheaters they can simply change the code u might find some but still its kinda unfair
really enjoyed G and F. I don't know why I wrote a dfs solution for F during contest(that was also wrong).
any hints for $$$F$$$?
You can remove the motion of the rocks by moving your reference frame up one unit each time step. From this point of view, at each time step the robot can either stand still, move down and to the right (if there is no rock at the end of this move), or move down two units (if there is no rock at the end of the move or at the intermediate square.) This may make it easier to see which squares the robot can reach and when it can reach them.
Hints for G?
Answer is at most 8, try to write a bruteforce for n=m=5 and observe patterns.
Thanks for the great problem F!
Thank you guys for an amazing Div3!
Wow, the system testing is earlier than usual!
Indian youtubers?
No, Um_nik
in Problem 'D', i used Unordered_map to save time and got TLE on testcase 30 ;(
my program got TLE because use unordered_map? 248557195 (problem D)
It is working with custom hash: https://codeforces.me/contest/1933/submission/248719307
I have a question! should we avoid the usage of un_map in contests? is this a thing in competitive programming? because the only way to find out that un_map will cost O(n) is by submitting the solution during the contest and wait LOL :)
You may refer to this blog.
I think that there's a problem of rank updating ychaaibi rating ( 1406 )
Thanks in advance, also thank you for the contest.
1599 after rating update. :( Does the rating increase after plag check is done?
Yeah the rank was updated and my rate was also increased by 3 ( 1406 -> 1409 )
Thank you so much.
Thank you to the question team for providing this tournament making it possible for me to pass 5 questions during the tournament. good bye pupil ， hello Specialist ：）
Is there anyway to get editorial of the contests (when over) at one-place.
In Question 1933C - Turtle Fingers: Count the Values of k,
Can anyone explain why do i need to iterate the values of x from 0 to (log(l)/log(a) + 1) ? Similarly i need to iterate the values of y from 0 to (log(l)/log(b) + 1) .
Why do i need to check for the last value (log(l)/log(a) + 1) ? Because anyway a power (log(l)/log(a) + 1) will be greater than l.
why does my solution fail when i iterate only till (log(l)/log(a)) ?
When you compute
log(l)/log(a)using floating-point arithmetic, you get rounding errors, so the value you compute may be less than the exact value. To see this, use a custom test to run the following program, which attempts to compute $$$\log 243/\log 3$$$:You will get not 5 but 4.999999999999999.
Okayyy. Thanks bro
Where is the editorial?
.
I made the same mistake using ideone.com. Next time, I will be more careful. Please, do not reduce my rating. These ratings are very important to me. Please do not block my account or impose penalties. I assure you that I will be more sincere in the future.
i was taking this contest in my school(not only this one) a place where lot of computers are place there were many people that were taking this contest simultaniasly
due to my strategic of taking exams and contest , i have breaks through the exam time and it includes changing my position , having some fresh air , eating something , .... i believe when i was walking outside , someone has checked on my computer for codes of contest and because there are schools property , i can not put passwords on computers for security i will be sure that nothing like that will happen again