2000A — Primary Task
Video
2000B — Seating in a Bus
Video
2000C — Numeric String Template
Video
2000D — Right Left Wrong
Video
2000E — Photoshoot for Gorillas
Video
2000F — Color Rows and Columns
Video
2000G — Call During the Journey
Video
2000H — Ksyusha and the Loaded Set
I initially solved this problem for a fixed value of k (by mistake), and then generalized it for varying values of k.
Video
:)
how come people are downvoting this?
Only video Tutorial?
how solutions with O(n*k*100*100) passes in F?
maybe the right solution is O(nk(a+b)).
Yes it's the intended solution but there are other solutions that passes with nk*10000
why in the last test in problem f the answer is 35 ? i tryed all the ways and the minimum is 36
Choose the whole first rectangle and the whole last rectangle and one column of the third rectangle. You will get 18 points in 35 moves.
thank you!
The last cell contribute to the answer with 2 not 1 because you then color a row and a column in the same time so the greedy solution doesn't really work because its not globally optimal to just take the current smallest number.
Thank you so much I was really wondering why my greedy solution wasn't working
Alright, I'm just gonna say it. This video tutorial is not very good. No offence to Shayan but this is not very helpful for someone who is just getting started. Wish we had a text editorial as well.
I think it's pretty helpful if you don't want to get the solution right away.
May i ask why you think it's not helpful? it's better for people to just focus on problems around your level, so it's common if you don't understand how to solve problems with rating above 1900 or 2000. Shayan did a great job on explaining the observation and the concept of problems which i think it's very helpful for beginner, not just about what algorithm/data structure we need to use.
And we will always have text editorial, it's just not out yet
Can anyone hack this?
G
I'm Chinese and I can't watch video on Youtube without VPN.
I am Syrian and in my country YouTube videos appear without ads, so you can change your region using a VPN to Syria
Thank you!
I'm Chinese too,so I agree with it.Word solutions might better.
I don't know why I spent so much time, this was much easier than I thought it was https://mirror.codeforces.com/contest/2000/submission/276369554
Such a bad problem explanation and details for E. so much changes during the contest.
thanks for the good work !
I participated in the contest and solved A,B,C, now it is my B and C are marked as red. Can anyone tell me why this happened?
System testing is going on. Your solution will be again judged on new added test cases thats why they are marked red. wait for sometime they will be evaluated
Thanks for the clarification.
why in the problem A, exponent can't have leading zeros
because
0015, 015, and 15 are the same in the number system, but in the question, the person misses the power as a proper number, not with any trailing zeros.
So 15, 25, and 35 are considered, not 015, 0025, or 00035.
[deleted comment]
Hello! Can somebody, please, help me with understanding the reason of the Excexussion Error on test 16, problem D. I have found out that a lot of ppl have the same test case and verdict. __ _Here is my solution: https://mirror.codeforces.com/contest/2000/submission/276190128_
UPD. I HAVE ALREADY FIXED IT
Hi I took a look but couldn't test due to submissions queue lagging. What if the string has no L or R? Your l and r pointer will go out of bounds when checking in the if statement.
Thank you for reply. It is impossible, cuz s[i] might be only L or R by the condition.
Hello, I might be wrong, it seems like the string could be “LLL” or “RRR”? I’m thinking that if the string was “LLL” your r pointer would go from n to be -1, then you would be checking s[-1]. If the string was “LLL”, your l pointer would be 4 when there are only 0~3 indices.
I’m not sure if I missed any statement stating that there is a guaranteed pair of L and R in the string at all times
I got you. I will check this case, but I think it is all OK cuz I make the checker for l < r, l = 1, r = n by default. UPD. Checked it. It is all good
I have found my mistake in the code. The reason of the error was not checking l < r in loop.
Here is AC solution:
https://mirror.codeforces.com/contest/2000/submission/276454055
someone knows why my solution gives tle in c? it seems its the unordered map but i dont understand why here is my solution: https://mirror.codeforces.com/contest/2000/submission/276234404
Maybe you can break as soon as the string is found to be invalid. I can't test as the submissions queue is lagging.
I saw that you use unordered_map. I read a post few days ago about it. Short story about: u can make the O(n^2) complexity to hack the guy who uses unordered_map in the default way. Here is the post, maybe it will help you: https://mirror.codeforces.com/blog/entry/62393
Can anyone help me understand why it is throwing TLE?
https://mirror.codeforces.com/contest/2000/submission/276439386
I'm also getting TLE in C 276445267
Instead of unordered_map use map. Will pass
Fixed it. The reason is some test case might contains appropriate prime number to make the complexity of
unordered_mapO(N^2)check this submission : 276448238 AC
Hello everyone.
I had a different idea for problem F, and I can't figure out why it does not work.
The idea is to use a greedy approach: Which rectangle can give us the most points with the least moves? I think (and I have no proof) that would be the rectangle with the shortest dimension of them all (width or height, it wouldn't matter). Because using points "would make the rectangles smaller", we know that we always use a full rectangle until we are very close to our required number of points.
So here is the approach:
1) We sort all the rectangles by their minimum dimension. 2) We iterate the rectangles, deciding if we use the full rectangle or if the loop ends here 2.1) We know if we use the full rectangle because each rectangle can give us (rows + cols) points, and we need k. A rectangle costs (rows * cols) moves. 2.2) If it's the last rectangle (we need less points than the ones that the rectangle can give) we process it differently.
Could someone tell me, if possible, why this approach wouldn't work, and perhaps provide a simple and illustrative test case?
I think the time complexity would be something like O(#rectangles + largest_height + largest_width) (but I am a noobie lol)
Here is a link to my submission: 276449407
Thanks
In some cases you would skip smaller dimensions for the sake of larger ones. For example:
Required points = 10
Rectangles =
3 100
5 5
In this case your algorithm would greedily fill 10 columns of the first rectangle and output 30. While if you used the second rectangle, the actual answer is 25
Thank you, that is indeed what I was looking for.
I need help
Can anyone tell me why my solution in proplem E got TLE when i write it in java , but when i write the same code in c++ i got AC
java solution --> Your text to link here...
c++ solution --> Your text to link here...
The video tutorial is good but I think the written editorial is the best.
For problem D, I know that it can be solved using 2 pointers or manually matching the L's with R's, but still I can't figure out what is wrong with my solution, it gives Wrong Answer on Test 7, i.e. it is working for smaller inputs but not for larger ones, (maybe, I don't know). It would be very helpful, if someone could point out the idea that I am missing.
My Submission: https://mirror.codeforces.com/contest/2000/submission/276453840
If you get WA try to debug your code. If that doesn't work implement a new code. Maybe that will work. In this problem you just need to match L's with R's. So there are many ways to solve, I suggest you to try a new implementation.
That's the point, I know that it can be solved in many ways and I do know the solution too. But I wanted to know what was wrong in my process such that it failed for larger testcases but not the smaller ones. Just as I said, it doesn't give WA for any Test before 7 so it bothers me to know what concept I missed/got wrong while implementing my solution.
may be try a ds like long or long long instead of int. Sometimes int fails to save larger numbers. idk the exact ds that have use in python but for cpp it's better to use long long.
I really appreciate that you are trying to help but the thing is instead of using 2 pointers or something else, what I did was I initially counted the number of R's in a for loop. Then I ran another for loop and incremented the number of L's as I got one, and I added the ans with a_i*min(num of l, num of r). If s_i is equal to R then I decremented the number of R's after updating the ans with the aforementioned expression. Do you have an idea why this would give wrong ans? And as for the fact about using a bigger ds, I did it using Java and I used long too for the ans variable. Once again, thanks a lot for helping me so far out.
Please help, in the H problem, I am re-initializing the segment tree of size 2e6 in every test case giving me MLE. How to do it efficiently? Thanks in advance
can someone explain the last eg of tc1 in problem F?
Solution
Approach: Stored the loads available in a map of int, set. Key is load, and the set stores the values just after which the available series of a particular load starts.
For query "?" just find the load greater than or equal to the this value in the map and print the first element of this set.
For query "+" find the values just greater and less than this value, this will give the available load and the value just before the start of series. Now remove this value from that set, and calculate two different loads and insert them into the respective keys of the map.
For query "-" find the values just greater and less than this value, this will give two available loads, remove from those and insert into the new load.
Please explain what is wrong in the implementation or logic.
I did the same logic and it fails in the following case:
1
6
1 4 6 7 8 9
1
? 1
Answer is 2 but code give 5.
i also did the same thing but it fails
Could you please provide a solution tutorial in text? In computer classroom we are not allowed to play a video with sound, because it may disturb others.
Only vedio TUtorial?please NO!!!
https://mirror.codeforces.com/blog/entry/132689
Vladosiya
Please link it in the contest material I think most people didn't see it.
Oh, thanks
For the 2nd last case 3 25 9 2 4 3 8 10 How the answer is 80?
why does problem G have binary search tag?