Блог пользователя Shayan

Автор Shayan, 3 месяца назад, По-английски

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

Разбор задач Codeforces Round 966 (Div. 3)
  • Проголосовать: нравится
  • -17
  • Проголосовать: не нравится

»
3 месяца назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

:)

»
3 месяца назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

how come people are downvoting this?

»
3 месяца назад, # |
  Проголосовать: нравится +4 Проголосовать: не нравится

Only video Tutorial?

»
3 месяца назад, # |
  Проголосовать: нравится +4 Проголосовать: не нравится

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

  • »
    »
    3 месяца назад, # ^ |
    Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

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

  • »
    »
    3 месяца назад, # ^ |
      Проголосовать: нравится +1 Проголосовать: не нравится

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

    • »
      »
      »
      3 месяца назад, # ^ |
        Проголосовать: нравится 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.

    • »
      »
      »
      3 месяца назад, # ^ |
        Проголосовать: нравится +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.

      • »
        »
        »
        »
        3 месяца назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

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

»
3 месяца назад, # |
  Проголосовать: нравится +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.

  • »
    »
    3 месяца назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

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

  • »
    »
    3 месяца назад, # ^ |
      Проголосовать: нравится +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.

  • »
    »
    3 месяца назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

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

»
3 месяца назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Can anyone hack this?

G

»
3 месяца назад, # |
  Проголосовать: нравится +2 Проголосовать: не нравится

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

»
3 месяца назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

I don't know why I spent so much time, this was much easier than I thought it was https://codeforces.net/contest/2000/submission/276369554

»
3 месяца назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

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

»
3 месяца назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

thanks for the good work !

»
3 месяца назад, # |
  Проголосовать: нравится 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?

  • »
    »
    3 месяца назад, # ^ |
      Проголосовать: нравится 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

»
3 месяца назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

  • »
    »
    3 месяца назад, # ^ |
    Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

    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.
  • »
    »
    3 месяца назад, # ^ |
      Проголосовать: нравится 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.

»
3 месяца назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

[deleted comment]

»
3 месяца назад, # |
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://codeforces.net/contest/2000/submission/276190128_

UPD. I HAVE ALREADY FIXED IT

  • »
    »
    3 месяца назад, # ^ |
      Проголосовать: нравится 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.

    • »
      »
      »
      3 месяца назад, # ^ |
      Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

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

      • »
        »
        »
        »
        3 месяца назад, # ^ |
        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

        • »
          »
          »
          »
          »
          3 месяца назад, # ^ |
          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

  • »
    »
    3 месяца назад, # ^ |
      Проголосовать: нравится 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://codeforces.net/contest/2000/submission/276454055

»
3 месяца назад, # |
  Проголосовать: нравится 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://codeforces.net/contest/2000/submission/276234404

  • »
    »
    3 месяца назад, # ^ |
      Проголосовать: нравится 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.

  • »
    »
    3 месяца назад, # ^ |
    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://codeforces.net/blog/entry/62393

»
3 месяца назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Can anyone help me understand why it is throwing TLE?

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

»
3 месяца назад, # |
  Проголосовать: нравится 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: 276449407

Thanks

  • »
    »
    3 месяца назад, # ^ |
    Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

    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

»
3 месяца назад, # |
  Проголосовать: нравится 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 AC

java solution --> Your text to link here...

c++ solution --> Your text to link here...

»
3 месяца назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

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

»
3 месяца назад, # |
  Проголосовать: нравится 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.

My Submission: https://codeforces.net/contest/2000/submission/276453840

  • »
    »
    3 месяца назад, # ^ |
      Проголосовать: нравится 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.

    • »
      »
      »
      3 месяца назад, # ^ |
        Проголосовать: нравится 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.

      • »
        »
        »
        »
        3 месяца назад, # ^ |
          Проголосовать: нравится 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.

        • »
          »
          »
          »
          »
          3 месяца назад, # ^ |
            Проголосовать: нравится 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.

»
3 месяца назад, # |
  Проголосовать: нравится 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

»
3 месяца назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

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

»
3 месяца назад, # |
Rev. 3   Проголосовать: нравится +5 Проголосовать: не нравится

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.

»
3 месяца назад, # |
  Проголосовать: нравится 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.

»
3 месяца назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Only vedio TUtorial?please NO!!!

»
3 месяца назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
3 месяца назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

why does problem G have binary search tag?