Shayan's blog

Codeforces Round 966 (Div. 3) — Video Tutorial
By Shayan, 4 months ago, In English

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

  • Vote: I like it
  • -17
  • Vote: I do not like it

»
4 months ago, # |
  Vote: I like it 0 Vote: I do not like it

:)

→ Reply
»
4 months ago, # |
  Vote: I like it 0 Vote: I do not like it

how come people are downvoting this?

→ Reply
»
4 months ago, # |
  Vote: I like it +4 Vote: I do not like it

Only video Tutorial?

→ Reply
»
4 months ago, # |
  Vote: I like it +4 Vote: I do not like it

how solutions with O(n*k*100*100) passes in F?

→ Reply
  • »
    »
    4 months ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    maybe the right solution is O(nk(a+b)).

    → Reply
    • »
      »
      »
      4 months ago, # ^ |
        Vote: I like it +5 Vote: I do not like it

      Yes it's the intended solution but there are other solutions that passes with nk*10000

      → Reply
  • »
    »
    4 months ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    why in the last test in problem f the answer is 35 ? i tryed all the ways and the minimum is 36

    → Reply
    • »
      »
      »
      4 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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.

      → Reply
    • »
      »
      »
      4 months ago, # ^ |
        Vote: I like it +1 Vote: I do not like it

      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.

      → Reply
      • »
        »
        »
        »
        4 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Thank you so much I was really wondering why my greedy solution wasn't working

        → Reply
»
4 months ago, # |
  Vote: I like it +40 Vote: I do not like it

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.

→ Reply
  • »
    »
    4 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I think it's pretty helpful if you don't want to get the solution right away.

    → Reply
  • »
    »
    4 months ago, # ^ |
      Vote: I like it +2 Vote: I do not like it

    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.

    → Reply
  • »
    »
    4 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    And we will always have text editorial, it's just not out yet

    → Reply
»
4 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Can anyone hack this?

G

→ Reply
»
4 months ago, # |
  Vote: I like it +2 Vote: I do not like it

I'm Chinese and I can't watch video on Youtube without VPN.

→ Reply
  • »
    »
    4 months ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    I am Syrian and in my country YouTube videos appear without ads, so you can change your region using a VPN to Syria

    → Reply
  • »
    »
    4 months ago, # ^ |
      Vote: I like it +6 Vote: I do not like it

    I'm Chinese too,so I agree with it.Word solutions might better.

    → Reply
»
4 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
4 months ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

Such a bad problem explanation and details for E. so much changes during the contest.

→ Reply
»
4 months ago, # |
  Vote: I like it 0 Vote: I do not like it

thanks for the good work !

→ Reply
»
4 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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?

→ Reply
  • »
    »
    4 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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

    → Reply
»
4 months ago, # |
  Vote: I like it 0 Vote: I do not like it

why in the problem A, exponent can't have leading zeros

→ Reply
  • »
    »
    4 months ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    because

    1. 10 ^ 0 is wrong since here x = 0 and it's given in the problem statement that x has to be >= 2
    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.
    → Reply
  • »
    »
    4 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

    → Reply
»
4 months ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

[deleted comment]

→ Reply
»
4 months ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

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

→ Reply
  • »
    »
    4 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like 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.

    → Reply
    • »
      »
      »
      4 months ago, # ^ |
      ← Rev. 2   Vote: I like it 0 Vote: I do not like it

      Thank you for reply. It is impossible, cuz s[i] might be only L or R by the condition.

      → Reply
      • »
        »
        »
        »
        4 months ago, # ^ |
        ← Rev. 2   Vote: I like it 0 Vote: I do not like it

        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

        → Reply
        • »
          »
          »
          »
          »
          4 months ago, # ^ |
          ← Rev. 2   Vote: I like it 0 Vote: I do not like it

          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

          → Reply
  • »
    »
    4 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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

    → Reply
»
4 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
  • »
    »
    4 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Maybe you can break as soon as the string is found to be invalid. I can't test as the submissions queue is lagging.

    → Reply
  • »
    »
    4 months ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    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

    → Reply
»
4 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Can anyone help me understand why it is throwing TLE?

https://mirror.codeforces.com/contest/2000/submission/276439386

→ Reply
»
4 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
  • »
    »
    4 months ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    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

    → Reply
    • »
      »
      »
      4 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Thank you, that is indeed what I was looking for.

      → Reply
»
4 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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...

→ Reply
»
4 months ago, # |
  Vote: I like it +1 Vote: I do not like it

The video tutorial is good but I think the written editorial is the best.

→ Reply
»
4 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
  • »
    »
    4 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

    → Reply
    • »
      »
      »
      4 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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.

      → Reply
      • »
        »
        »
        »
        4 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        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.

        → Reply
        • »
          »
          »
          »
          »
          4 months ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          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.

          → Reply
»
4 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
4 months ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

can someone explain the last eg of tc1 in problem F?

→ Reply
»
4 months ago, # |
← Rev. 3   Vote: I like it +5 Vote: I do not like it

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.

→ Reply
  • »
    »
    4 months ago, # ^ |
    ← Rev. 2   Vote: I like it +1 Vote: I do not like it

    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.

    → Reply
  • »
    »
    4 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    i also did the same thing but it fails

    → Reply
»
4 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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.

→ Reply
»
4 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Only vedio TUtorial?please NO!!!

→ Reply
»
4 months ago, # |
  Vote: I like it 0 Vote: I do not like it

For the 2nd last case 3 25 9 2 4 3 8 10 How the answer is 80?

→ Reply
»
4 months ago, # |
  Vote: I like it 0 Vote: I do not like it

why does problem G have binary search tag?

→ Reply