### Shayan's blog

By Shayan, 4 weeks ago,

Video

Video

Video

Video

Video

Video

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

• -17

 » 4 weeks ago, # |   0 :)
 » 4 weeks ago, # |   0 how come people are downvoting this?
 » 4 weeks ago, # |   +4 Only video Tutorial?
 » 4 weeks ago, # |   +4 how solutions with O(n*k*100*100) passes in F?
•  » » 4 weeks ago, # ^ | ← Rev. 2 →   0 maybe the right solution is O(nk(a+b)).
•  » » » 4 weeks ago, # ^ |   +5 Yes it's the intended solution but there are other solutions that passes with nk*10000
•  » » 4 weeks ago, # ^ |   +1 why in the last test in problem f the answer is 35 ? i tryed all the ways and the minimum is 36
•  » » » 4 weeks ago, # ^ |   0 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.
•  » » » » 4 weeks ago, # ^ |   0 thank you!
•  » » » 4 weeks ago, # ^ |   +1 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.
•  » » » » 4 weeks ago, # ^ |   0 Thank you so much I was really wondering why my greedy solution wasn't working
 » 4 weeks ago, # |   +40 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.
•  » » 4 weeks ago, # ^ |   0 I think it's pretty helpful if you don't want to get the solution right away.
•  » » 4 weeks ago, # ^ |   +2 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.
•  » » 4 weeks ago, # ^ |   0 And we will always have text editorial, it's just not out yet
 » 4 weeks ago, # |   0 Can anyone hack this?G
 » 4 weeks ago, # |   +2 I'm Chinese and I can't watch video on Youtube without VPN.
•  » » 4 weeks ago, # ^ |   +1 I am Syrian and in my country YouTube videos appear without ads, so you can change your region using a VPN to Syria
•  » » » 4 weeks ago, # ^ |   +1 Thank you!
•  » » 4 weeks ago, # ^ |   +6 I'm Chinese too,so I agree with it.Word solutions might better.
 » 4 weeks ago, # |   0 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
 » 4 weeks ago, # | ← Rev. 2 →   0 Such a bad problem explanation and details for E. so much changes during the contest.
 » 4 weeks ago, # |   0 thanks for the good work !
 » 4 weeks ago, # |   0 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?
•  » » 4 weeks ago, # ^ |   0 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
•  » » » 4 weeks ago, # ^ |   0 Thanks for the clarification.
 » 4 weeks ago, # |   0 why in the problem A, exponent can't have leading zeros
•  » » 4 weeks ago, # ^ | ← Rev. 2 →   0 because 10 ^ 0 is wrong since here x = 0 and it's given in the problem statement that x has to be >= 2 10 ^ 002, 10 ^ 01 etc are wrong too since it says in the problem statement that 10 ^ 5 has to be written as 105, making numbers like 1005 invalid.
•  » » 4 weeks ago, # ^ |   0 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.
 » 4 weeks ago, # | ← Rev. 2 →   0 [deleted comment]
 » 4 weeks ago, # | ← Rev. 2 →   0 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
•  » » 4 weeks ago, # ^ |   0 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.
•  » » » 4 weeks ago, # ^ | ← Rev. 2 →   0 Thank you for reply. It is impossible, cuz s[i] might be only L or R by the condition.
•  » » » » 4 weeks ago, # ^ | ← Rev. 2 →   0 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
•  » » » » » 4 weeks ago, # ^ | ← Rev. 2 →   0 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
•  » » 4 weeks ago, # ^ |   0 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
 » 4 weeks ago, # |   0 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
•  » » 4 weeks ago, # ^ |   0 Maybe you can break as soon as the string is found to be invalid. I can't test as the submissions queue is lagging.
•  » » 4 weeks ago, # ^ | ← Rev. 2 →   0 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
 » 4 weeks ago, # |   0 Can anyone help me understand why it is throwing TLE?https://mirror.codeforces.com/contest/2000/submission/276439386
•  » » 4 weeks ago, # ^ |   0 I'm also getting TLE in C 276445267
•  » » » 4 weeks ago, # ^ |   0 Instead of unordered_map use map. Will pass
•  » » » 4 weeks ago, # ^ |   0 Fixed it. The reason is some test case might contains appropriate prime number to make the complexity of unordered_map O(N^2)check this submission : 276448238 AC
 » 4 weeks ago, # |   0 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: 276449407Thanks
•  » » 4 weeks ago, # ^ | ← Rev. 2 →   0 In some cases you would skip smaller dimensions for the sake of larger ones. For example:Required points = 10Rectangles = 3 1005 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
•  » » » 4 weeks ago, # ^ |   0 Thank you, that is indeed what I was looking for.
 » 4 weeks ago, # |   0 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 ACjava solution --> Your text to link here...c++ solution --> Your text to link here...
 » 4 weeks ago, # |   +1 The video tutorial is good but I think the written editorial is the best.
 » 4 weeks ago, # |   0 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.
•  » » 4 weeks ago, # ^ |   0 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.
•  » » » 4 weeks ago, # ^ |   0 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.
•  » » » » 4 weeks ago, # ^ |   0 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.
•  » » » » » 4 weeks ago, # ^ |   0 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.
 » 4 weeks ago, # |   0 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
 » 4 weeks ago, # | ← Rev. 2 →   0 can someone explain the last eg of tc1 in problem F?
 » 4 weeks ago, # | ← Rev. 3 →   +5 SolutionApproach: 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.
•  » » 4 weeks ago, # ^ | ← Rev. 2 →   +1 I did the same logic and it fails in the following case:1 6 1 4 6 7 8 9 1 ? 1Answer is 2 but code give 5.
•  » » 4 weeks ago, # ^ |   0 i also did the same thing but it fails
 » 4 weeks ago, # |   0 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.
 » 4 weeks ago, # |   0 Only vedio TUtorial?please NO!!!
•  » » 4 weeks ago, # ^ |   0
•  » » » 4 weeks ago, # ^ |   0 VladosiyaPlease link it in the contest material I think most people didn't see it.
•  » » » » 4 weeks ago, # ^ |   0 Oh, thanks
 » 4 weeks ago, # |   0 For the 2nd last case 3 25 9 2 4 3 8 10 How the answer is 80?
 » 2 weeks ago, # |   0 why does problem G have binary search tag?