Vladosiya's blog

By Vladosiya, history, 5 months ago, translation, In English

1650A - Deletions of Two Adjacent Letters

Idea: MikeMirzayanov

Tutorial
Solution

1650B - DIV + MOD

Idea: Vladosiya

Tutorial
Solution

1650C - Weight of the System of Nested Segments

Idea: myav

Tutorial
Solution

1650D - Twist the Permutation

Idea: MikeMirzayanov

Tutorial
Solution

1650E - Rescheduling the Exam

Idea: SixtyWithoutExam

Tutorial
Solution

1650F - Vitaly and Advanced Useless Algorithms

Idea: Aris

Tutorial
Solution

1650G - Counting Shortcuts

Idea: MikeMirzayanov

Tutorial
Solution
 
 
 
 
  • Vote: I like it
  • +73
  • Vote: I do not like it

»
5 months ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

Thank you codeforces for this contest!

»
5 months ago, # |
  Vote: I like it +22 Vote: I do not like it

my solution for problem D using deque: https://codeforces.com/contest/1650/submission/148940490 I think it's easier, if you know data structure.

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

    Yeah+

  • »
    »
    5 months ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    please explain your solution

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

      First, The problem is he performed n operations sequentially. At the i-th operation, Petya chose the first i elements of the array and cyclically shifted them to the right number of times.

      we have the final array ! and before operations we know that the array is sorted

      so how can we do this operations reversely to sort the array ? _we will start from n instead of 1 _and shift left instead of shift right

      first we want to make the last number in the array equal n , how many times of shift left we can do to make that ? just loop make shiftes untill it happen and then now we will search for n-1 to put it in position n-1 in the array so to make the same thing easier we will remove n from the array, we won't need it again.

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

    Thank you!

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

    It was easy to understand . Thank you.

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

    thank you!

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

E has an answer binary search.

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

    Can you please explain your approach ?

    Thanking you in advance

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

      we send a value to the binary search If the value satisfies the condition then there is a solution greater than our value

»
5 months ago, # |
  Vote: I like it +14 Vote: I do not like it

If you are/were getting a WA/RE verdict on problems from this contest, you can get a small counter example for your submission on cfstress.com. To do that, click on the relevant problem's link below, add your submission ID, and edit the table to increase/decrease the constraints.

If you are not able to find a counter example even after changing the parameters, reply to this thread, mentioning the contest_id, problem_index and submission_id.

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

    Will this work for contest problems during the contest?

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

      Works for me. ¯\_(ツ)_/¯

      To make it work for you, you need to learn about 1) stress testing and 2) run a local development server of the website.

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

    Thanks, Was really helpful

»
5 months ago, # |
Rev. 3   Vote: I like it 0 Vote: I do not like it

Ok

»
5 months ago, # |
Rev. 3   Vote: I like it 0 Vote: I do not like it

Resolved

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

in the following statement

numbers from r−rmoda to r that have an incomplete quotient when divided by a equal to ⌊r/a⌋

1) can someone expain me the meaning of the incomplete quotient(does it mean that it will give remainder?)

2) How did we arrive at this conclusion?

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

    Can anyone plese explain this.

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

      I find the editorial difficult to understand. Here is my way of explaining a solution to problem B:

      Imagine a 5x7 monthly calendar where the rows represent work week and the columns represent Sunday, Monday, ... to Saturday. Suppose the upper left hand corner of the has the day start with 0. So, the first row are days 0 ~ 6, second row are days 7 ~ 13, and so on.

      Day / 7 represents the work week, the row on the calendar. Day % 7 represents the week day (Sunday=0, ..., Saturday=6), the column on the calendar. Suppose the question is to ask you which day from L (eg 20) to R (eg 29) has the Manhattan distance largest from the origin of the calendar.

      My approach is to check if the L and R are on the same row. If so, then R is the answer. Otherwise, I tried to move R to the closest Saturday on the previous row.

      Hope you get what I mean.

    • »
      »
      »
      5 months ago, # ^ |
      Rev. 2   Vote: I like it 0 Vote: I do not like it

      We want to prove that for every number $$$x$$$ in range $$$[r - r \ mod \ a; r] \ x \ mod \ a \le r \ mod \ a$$$; $$$r - r \ mod \ a$$$ is divided by $$$a$$$, because $$$r = a \cdot r \ div \ a \ + r \ mod \ a$$$, it means $$$r - r \ mod \ a = a \cdot r \ div \ a$$$, and $$$a$$$ multiply something always is divided by $$$a$$$. OK, we know that $$$r - r \ mod \ a$$$ is divided by $$$a$$$ and every number in range $$$[r - r \ mod \ a + 1; r]$$$ is not divided by $$$a$$$. That means every $$$x$$$ from range $$$[r - r \mod \ a + 1; r]$$$ has incomplete quotient $$$\lfloor\frac{r}{a}\rfloor$$$. For example, $$$r = 11$$$, $$$a = 4$$$. $$$11 - 11 \ mod \ 4$$$ = $$$8$$$. $$$8$$$ is divided by $$$4$$$ and every num in range $$$[8 + 1; 11]$$$ is not divided by $$$4$$$. $$$\frac{8}{4} = 2$$$, $$$\frac{9}{4} = 2,25$$$, $$$\lfloor(2,25)\rfloor = 2$$$. Maximum in range $$$[8 + 1; 11]$$$ is $$$11$$$, and for maximum value we still get result $$$\lfloor \frac{r}{a} \rfloor = 2$$$ ; $$$\frac{11}{4} = 2,75$$$, $$$\lfloor(2,75)\rfloor = 2$$$.

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

        We want to prove that for every number x in range [r−r mod a;r] x mod a≤r mod a is it because of this fact:- fact that [x/a] is maximum at x=r so if xmoda<=rmoda ,we can put x=r and make both [x/a] and xmoda maximum simultaneously

        • »
          »
          »
          »
          »
          5 months ago, # ^ |
          Rev. 2   Vote: I like it 0 Vote: I do not like it

          Yes, but if $$$x = r - r \ mod \ a - 1$$$ we get maximum $$$r \ mod \ a$$$, so we just need to check $$$x = r - r \mod \ a - 1$$$ and $$$x = r$$$.

          • »
            »
            »
            »
            »
            »
            5 months ago, # ^ |
            Rev. 4   Vote: I like it 0 Vote: I do not like it

            the more number of times i read the expainations, the more queries i am having( maybe because i am new to advance number theory concepts or it is the wording of the editorial)

            1)how did you arrive at the conclusion that every number in range [r−rmoda + 1;r] is not divided by a.

            i can observe it but i am not able to prove it mathematically

            2) what do we exactly mean by incomplete quotient

            3)why does the editoral say the statement (and are guaranteed to have a value fa less than fa(r)) if we find a x such that x%a > r%a, can't we get a fax>far ( i know that is what we are trying to prove but i want to know if i am interpreting this editorial statement correctly .

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

              Let's have an example: $$$a=7$$$. $$$21$$$ is divided by $$$7$$$, next number that can be divided is $$$21+7=28$$$. Every number in range $$$[21 + 1; 28 - 1]$$$ is not divided by $$$7$$$. So, if number $$$x$$$ divided by $$$a$$$ then $$$x + a$$$ also divided by $$$a$$$ and every number in range $$$[x + 1, x + a - 1]$$$ is not divided by $$$a$$$. $$$r - r \ mod \ a$$$ is divided by $$$a$$$, every number in range $$$[r - r \ mod \ a + 1; r - r \ mod \ a + a - 1]$$$ is not divided by $$$a$$$, we sure that $$$r < r - r \ mod \ a + a$$$, because number $$$a - r \ mod \ a > 0$$$, $$$r \ mod \ a < a$$$.

              2) $$$a \ div \ b$$$ is incomplete quotient or $$$\lfloor\frac{a}{b} \rfloor$$$.

»
5 months ago, # |
  Vote: I like it +9 Vote: I do not like it

finally a div3 contest after 2 month break^^

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

Why havn't the rating changed yet?

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

Why are the ratings not updated yet?

»
5 months ago, # |
  Vote: I like it +18 Vote: I do not like it

Hello there, and thanks for the enjoyable problems.

I liked the last two problems since they can have much to teach for people who are new to DP and graph algorithms.

Problem F was a combination of two merely classic ideas that are good to know for beginners, and the last problem introduces a useful property of the BFS algorithm and the BFS tree.

Thanks to both authors for their cool problems, and I would suggest everyone to upsolve these two problems since they may help you in the future :)

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

Problem statement could be more clearer as I wasted a lot of time in the 3rd question to understand just what I need to print.

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

Can anyone explain G, I'm having a little trouble in understanding editorial.

»
5 months ago, # |
  Vote: I like it +3 Vote: I do not like it

Can the problem D be solved in O(n) time complexity?

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

    I wasted whole time trying that, would be helpful if some did solve it using O(n)

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

Why I used memory search on G and got a TLE :(

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

I love practicing CP but editorials like this are really hard to read and understand

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

In problem E is it possible to reschedule one of exams to day one?

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

    yes but that would never help bc the time between the start of the session and the first exam is counted in the answer.

»
5 months ago, # |
  Vote: I like it +3 Vote: I do not like it

where can i found similar problems to G-Counting shortcuts ? i suck at dp on trees/graphs :(

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

Could somebody, please, explain how do we use dp in G-problem?

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

    I don't understand too :(

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

    You store the number of ways to reach a node from source by following a path of min distance and (min distance + 1). Like whenever you're reaching a node from some other node, just ask if the depth of the curr node is equal to min depth or (min depth + 1), based on the ans you get, update your dp values.

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

Question D is little tricky...

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

In problem E , I just used a multiset which stores the difference between every two consecutive exams dates and update it for each element (try to put it in the best place) I think its easier. here it is 148865257

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

    yea my sol was very similar haha, multiset is a lot more intuitive isnt it :p

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

Can someone explain with an example what are they asking for output in problem C ?

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

Problem 1650G - Counting Shortcuts can be solved in another way. Calculate for each vertex: distance and number of shortest paths from $$$s$$$ and $$$t$$$ (with 2 bfs). Then we can iterate over all edges $$$\left(u,v\right)$$$. Firstly, vertices $$$u$$$ and $$$v$$$ should be included in same level (same distance from $$$s$$$). Secondly, $$$\text{dist}(s,u)+\text{dist}(v,t)=\text{dist}(s,t)$$$. If both conditions are held, then we can build path $$$s \rightarrow ... \rightarrow u \rightarrow v \rightarrow ... \rightarrow t$$$ with length equal to $$$\text{dist}(s,t)+1$$$. We need to add $$$\text{cntShortestWays}(s,u) \cdot \text{cntShortestWays}(t,v)$$$ to answer. Solution: 150206150

  • »
    »
    6 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    can you explain why vertices u and v should be included in same level?