Shayan's blog

Codeforces Round 966 (Div. 3) — Video Tutorial
By Shayan, 10 days 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
  • -20
  • Vote: I do not like it

»
10 days ago, # |
  Vote: I like it 0 Vote: I do not like it

:)

→ Reply
»
10 days ago, # |
  Vote: I like it 0 Vote: I do not like it

how come people are downvoting this?

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

Only video Tutorial?

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

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

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

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

    → Reply
    • »
      »
      »
      10 days 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
  • »
    »
    10 days 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
    • »
      »
      »
      10 days 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
    • »
      »
      »
      10 days 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
      • »
        »
        »
        »
        9 days 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
»
10 days 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
  • »
    »
    10 days 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
  • »
    »
    10 days 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
  • »
    »
    10 days 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
»
10 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Can anyone hack this?

G

→ Reply
»
10 days 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
  • »
    »
    10 days 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
  • »
    »
    10 days 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
»
10 days 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://codeforces.com/contest/2000/submission/276369554

→ Reply
»
10 days 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
»
10 days ago, # |
  Vote: I like it 0 Vote: I do not like it

thanks for the good work !

→ Reply
»
10 days 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
  • »
    »
    10 days 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
»
10 days ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
  • »
    »
    10 days 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
  • »
    »
    10 days 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
»
10 days ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

[deleted comment]

→ Reply
»
10 days 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://codeforces.com/contest/2000/submission/276190128_

UPD. I HAVE ALREADY FIXED IT

→ Reply
  • »
    »
    9 days 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
    • »
      »
      »
      9 days 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
      • »
        »
        »
        »
        9 days 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
        • »
          »
          »
          »
          »
          9 days 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
  • »
    »
    9 days 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://codeforces.com/contest/2000/submission/276454055

    → Reply
»
10 days 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://codeforces.com/contest/2000/submission/276234404

→ Reply
  • »
    »
    9 days 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
  • »
    »
    9 days 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://codeforces.com/blog/entry/62393

    → Reply
»
9 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Can anyone help me understand why it is throwing TLE?

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

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

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

      → Reply
»
9 days 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
»
9 days 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
»
9 days 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://codeforces.com/contest/2000/submission/276453840

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

    i also did the same thing but it fails

    → Reply
»
8 days 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
»
8 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Only vedio TUtorial?please NO!!!

→ Reply
»
7 days 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