pikmike's blog

By pikmike, history, 4 months ago, translation, In English

1373A - Donut Shops

Idea: Roms

Tutorial
Solution (pikmike)

1373B - 01 Game

Idea: Roms

Tutorial
Solution (Roms)

1373C - Pluses and Minuses

Idea: Roms

Tutorial
Solution (Roms)

1373D - Maximum Sum on Even Positions

Idea: vovuh

Tutorial
Solution (vovuh)

1373E - Sum of Digits

Idea: BledDest

Tutorial
Solution 1 (BledDest)
Solution 2 (pikmike)

1373F - Network Coverage

Idea: adedalic

Tutorial
Solution 1 (adedalic)
Solution 2 (Ne0n25)

1373G - Pawns

Idea: Roms and BledDest

Tutorial
Solution (Roms)
 
 
 
 
  • Vote: I like it
  • +98
  • Vote: I do not like it

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

Been waiting for this editorial for so long...

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

Can someone explain E — Sum of Digits more clearly...? Thank you in advance.

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

Finally :):)

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

    Sir,Can you kindly help me regarding problem B?Can u kindly explain how alice and bob are giving the optimal moves according to the editorial? If the string is 1011010 alice shud remove that 01 or 10 on whose both sides the bits are same...

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

      No matter which one pair Alice and Bob remove there is always same number of total moves(equal to min(c0,c1)).So any possible move is going to be optimal.

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

        By taking several examples,i was able to deduce that but then How to relaize it during the contest??And I would also like to know how you deal with these problems that have these optimal moves in their problem statements?I find it difficult to decide what is optimality in terms of the given moves just like in this problem where each move as u say is optimal Thanks in advance if someone kindly replies to this

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

          Think of it this way. You will not be able to make a move only when 0s or only 1s remain but not both. Because if both remain there will always be at least a pair of 0 and 1 adjacent and we will be able to remove this. In every move, the count of 0s and 1s get reduced by one each. So the total number of moves are always equal to minimum of count of 0s and 1s.

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

            Sir,that much I have understood from the editorial.What I say is it is difficult for me to deduce what kind of move is actually an optimal move in terms of the given game.Sometimes,any move is optimal as in this given problem and sometimes there will be particular moves that will be optimal..

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

              You can easily prove this by contradiction. Assume there is no more moves possible and the string has both 0 and 1. But if both 0 and 1 exist then there must be at least one 0 with 1 as its adjacent neighbor and vice-versa.

              Hence the opposite only wins when there is only 1 or 0 in the string.

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

vovuh is really back

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

Please help me, i can't figure out what is wrong in my code. my code

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

    I am not sure about it but maybe the issue is with datatype, You can try to resubmit it with long.

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

In D, what does the author mean by " started reversing the subarray but didn't end it"?

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

    Reversing will not stop at this index. It will continue further

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

Problem 1 seemed to be harder than 2 and 3 to me!

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

Did someone tried problem D with Binary search approach??

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

Can anyone please help me figure out why is this O(n) solution for F getting TLE on case — 9 https://codeforces.com/contest/1373/submission/85147824

Thanks in advance for the help.

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

Didn't get the solution of E. Can someone plz explain.

  • »
    »
    4 months ago, # ^ |
      Vote: I like it -32 Vote: I do not like it

    Hey kavishlodha123

    Check out the detailed explanations of Problem E

    I am sure you will understand the logic by the end :)

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

      Bro, you are a newbie, no offense, but you should create a YT channel when you reach CM or master. Focus on studies.

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

        It's a team account for our student chapter We don't take rated contests with this account Our team members are Experts, CMs and Masters :)

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

You know a problem is beautiful when its an E but can still be solved by brute force.

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

In Problem D, may be I getting it wrong, please correct me. I am implementing the first approach for this test case.

10

7 8 4 5 7 6 8 9 7 3.

here, total sum for even position = 33

and, total sum for odd position = 31

v1 = [1, 1, -1, -1, -4], pairs are (8,7),(5,4),(6,7),(9,8),(3,7)

v2 = [-1, -1, 1, 1, 4], pairs are (7,8),(4,5),(7,6),(8,9),(7,3)

so reversing the first 4 elements provide 2. so 33 + 2 = 35.

I know I can get maximum value just by replacing 8,4. But what I missed from the editorial?

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

    Add another dp that changes 1 with 2, 3 with 4 elements etc. You are now only trying to change 0 with 1, 2 with 3, and so on.

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

    I don't know how u implemented but I guess u had not taken the case of subarray being started with a even positioned index. U missed comparisions of (i)th even index with (i+1)th odd index.

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

    I slightly changed the ordering when the two consecutive elements were considered starting from odd position and got accepted Check this 85213408

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

In Problem D, can someone explain the DP Approach. I get the idea but I'm unable to implement.

Transitions are pretty easy:

Not for Me , I guess ! Please someone explain them Thanks!

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

    Well I can try explainging the transitions. The transition dp(i+1,0) is straightforward.

    The transition dp(i+2,1):-> Suppose the array is ---(----)--- and the array elements within paranthesis denotes the subarray(from index 4 to 8) we need to reverse then when we are at index 4 then we start to reverse the subarray and the transition will be from 4 we need to got 6 with values reversed hence we need to take the value of dp(4,0) but at index 6 we will make a transition to 8 and notice that when making this transition the maximum value will be for dp(6,1) not dp(4,1). This type of reversal is taken into account because the reversal of an array of size 2x is same as reversing array of size 2 in x moves hence dp(i+2,1)=max(dp(i+2,1,max(dp(i,0),dp(i,1))+(i%2==0?a(i+1):a(i))

    The last transition dp(i+1,2):-> Now suppose we are at an index where we have ended reversing the subarray then at this index what transitions we are left with are the max sum until index i + the sum at remaining even indices therefore the transition looks like dp(i+1,2)=max(dp(i+1,2),max(dp(i,0),dp(i,1),dp(i,2)+(i%2==0?a(i):a(i+1)).

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

    For transition dp(i,0) It means the answer on the prefix till i and in which we didn't make any reverse. Here actually stores the sum of prefix even position values.

    For transition dp(i,1) It means the answer on the prefix till i and from where the reverse is started. if i is even and we started to reverse from that index that means the value of index i+1(i+1 th index value will going to be even parity index for reversing) will be contributing on the answer for dp(i,1) and if i is even and we started reverse from that index that means the value of i will be contributing on the answer for dp(i,1).

    For transition dp(i,2) It means the answer on the prefix till i and from where the reverse will be finished. If i is even the value of index i will be contributed to the answer, otherwise nothing more will be contributed. Because if i is odd then it is already added to the answer as the reversing started formerly.

    (sorry for my poor english)

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

    After about a half an hour of going back and forth between the editorial and the comments and thinking about it for a while, I probably can explain the approach better. Well, then.

    Problem: We need to determine the maximum sum that we can get after reversing at most one subsegment of the sequence, and this sum is defined to be that of the elements at even indices after the operation.

    Solution: Since we are changing at most one subsegment, we need to keep track of those changes, simultaneously while maintaining the maximum sum. Say, we need to update the range [l, r) (I'm deliberately using the notation with right endpoint open, you'll see why). This range will partition the sequence into three sub-ranges: [1, l) (the range to the left of updated range), [l, r) (the updated range), and [r, n + 1) (the range to the right of updated range). For each of these three sub-ranges, we'll maintain one dp-array (this explains why there are dp[][0], dp[][1], dp[][2]). Now onto the second dimension.

    1. The Left Part: dp[i][0] is the maximum sum that you get when i is in the left part. To maintain this, we just follow the definition of the sum(if i is even, we include it, otherwise, we discard it):

    $$$dp[i\ +\ 1][0]\ =\ dp[i][0]\ +\ (i\ \%\ 2\ ==\ 0)\ *\ a[i];$$$

    2. The Middle Part: dp[i][1] is the maximum sum that you get when i is in a segment that we intend to reverse. Note that it isn't necessary that the segment must start at i, it can be anywhere in-between. Now since reversing odd length ranges doesn't benefit even a penny, we'll simply ignore them and increment i by 2 for this array as we make transitions. To maintain this, we'll just take the maximum of dp[i - 2][0] (meaning the middle segment starts at i) and dp[i - 2][1] (it started somewhere earlier in the past but it continues still). The cost at this index just depends on the parity of i (as with everything else in this question apparently): if i is even, we keep element at i + 1 (since that'll be odd, and if we don't keep it we'd be ignoring it when we make the next jump of 2), otherwise, we simply keep the element at i:

    $$$dp[i\ +\ 2][1]\ =\ max(dp[i][0],\ dp[i][1])\ +\ (i\ \%\ 2\ ==\ 0)\ ?\ a[i\ +\ 1]\ :\ a[i];$$$

    3. The Right Part: dp[2][i] is the maximum sum that you get when i is in the segment where the reversal has already happened. It could either happen at this index or has already been sometime back in the past (or probably it never happened or never will be). To maintain it is to simply take the maximum of all these three possibilities. And the cost again depends on the parity of i: if it's odd, ignore it (because either it has been taken care of by the last dp[1][ ], meaning i = r or it's strictly in the right so it meets ignorance there too). If it's even, it's included nevertheless. Notice that the cost is exactly similar to the left part (as it should be).

    $$$dp[i + 1][2]\ =\ max(dp[i][0],\ dp[i][1],\ dp[i][2])\ +\ (i\ \%\ 2\ ==\ 0)\ *\ a[i];$$$

    Finally, the answer is just the maximum of dp[n][0], dp[n][1], and dp[n][2] depending on arguments that I believe you can pretty easily come up with now :)

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

      I unable to understand why we take a[i+1] for even index and a[i] for odd index in the middle part. Can you explain it in detail?

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

        Read the question properly. I'm sure you'll get it. Hint: we're flipping the middle segment, remember?

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

      wish everyone could explain like you. loved it. although you have something to fix in the middle zone i think. 'dp[i — 2][0] (meaning the middle segment starts at i)' might be ' dp[i — 2][0] (meaning the middle segment starts at i-2)'. and in the third zone, dp[i+1][2] = max(dp[i][1],dp[i][2]) + (i%2 == 0)*a[i] might be enough i reckon

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

      superb explanation

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

      Not sure tho, but i think u made a typo in the middle part, u wrote dp[i+2][0] instead of dp [i+2][1] ?

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

        Thanks, that actually was a typo. I fixed it along with some other typos that were there earlier.

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

One more and easiest solution of D can be as follows :

Firstly sum all values at even indices and replace them with value*-1 i.e.(arr[i] = -1*arr[i]) and after that find maximum sum subarray of even length using dp whose recurrence is simply

dp[i] = max({0,arr[i]+arr[i+1],arr[i]+arr[i+1]+dp[i+2]) .

My Code

Thank You and Happy Coding!!!

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

    great approach, thanks for sharing.

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

    nice approach but i am curious to know how and why this approach came to your mind??

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

Can anyone please explain logic of C... I did't get it.

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

    Firstly calculate the prefix sums of the string.

    Now let's look till which index we can go using the initialized values.

    When x=0, (Suppose x is the initialized value.)
    We can go till the first time we get -1 in the prefix sum.

    When x=1, We can go till the first time we get -2 in the prefix sum.

    In this way for x=n We can go till the first time we get -(n+1) in the prefix sum.

    So if we keep track of the first index prefix sum we get we can easily calculate till which length we can go using that initialize value. And the very first time for which initialize value we don't get any negative prefix sum that time we can go till end.

    Suppose the string --+-.
    Corresponding prefix sum -1,-2,-1,-2.

    Here for x=0, we can go till index 1 (Suppose 1 indexed string) for x=1, we can go till index 2 for x=2, we can go till index 3 for x=3, we can go till the end (As we didn't get -3 in prefix sum) So the answer is = 1+2+3+4 = 7

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

Please detail Es tutorial with proofs and explain more clearly.

  • »
    »
    4 months ago, # ^ |
      Vote: I like it -26 Vote: I do not like it

    Hey AM_I_Learning

    Check out the detailed explanations of Problem E

    I am sure you will understand the logic by the end :)

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

      After checking your video editorial only I asked you in comments there also for proof and also I asked here for someone to prove why this 9 philosophy works, but I have build some intuition now, which allow me to accept this.approach.

      UPD :- you replied nicely on YouTube, post it here as well so that it helps many others.

      • »
        »
        »
        »
        4 months ago, # ^ |
          Vote: I like it -8 Vote: I do not like it

        After watching the video: Link

        Below is my reply on YT comment where someone asked my why it's giving the min value of X.

        It's simple, we are looping through all possible values of nines (number of nines at the middle) and all possible values of the last digit d Now for a particular value of (nines, D) we are getting the sum of digits of the prefix which I am forming greedily which ensures that for a particular pair (nines, D) the number formed is smallest. And we store ans as the minimum of all possible X which is getting formed with the given pair of (nines, D) Watching the video will help :)

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

          thank you for your helpful video, i understand it now, btw i don't know why you got so many downvotes =)))

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

          I think the reason behind so many downvotes is that he is using a fake account.

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

            This is not a fake account brother Actually we are a team of coders and upload videos through a common account.

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

If anyone wants to do 1373E - Sum of Digits by Number Theory " short and precise" , you can see my submission here 85157600 I have given proper comments. Let me know if you have difficulty understanding any part of it.

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

    godsend!!

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

    I just have 2 questions, why are we looping from -1 to 120, the indices for array can stretch further and why are we going from -100 to 9 in the inner loop? Thanks

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

      The value of P is just an approximation of where the number lies.

      After we get the approx. position of the P. We brute force through for arr[] as it is not simple to know where the next (k+1) sum is equal to n, as it is using sum of digits of the number. And I stretched the ranges to [-1,120] and [-100,9] just to be safe. Also I was lazy to find a proper range for those.

      i ∈ [-1,120] is used to shift through arr[x+i],

      while i ∈ [-100,9] is used for arr[x]+i; // arr[] as in code

      If you see though some examples you will see it is a safe range and if an answer don't come in it, then an ans is not possible

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

can someone explain editorial solution of F..i am not able understand it from editorial

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

For Problem D, just use Kadane’s Algorithm twice ,

Just take the array of differences (Odd index — Even index) ;

1. First for difference pairs with indexed (0,1),(2,3),(4,5),..... eg,
2. Second for difference pairs with indexes (1,2),(3,4),(5,6),..... eg, 

At last add the maximum in sum(even indexes)

Here's my submission : 85055641

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

    great solution..i wasn't able to understand other solutions this was quite easy to understand thanks...

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

      Thanks bro, I'm glad it was of help. Don't know why people downvoted it though.

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

    85227537 Some help with this..

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

    This can also be referred

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

    can you please explain your approach why you are taking difference pairs and how it is leading to max sum?

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

      In my code the "even" variable" stores the sum of the even indexes. After that the "max" variable" uses Kadane's Algo for difference pairs(Odd — Even, because we need to maximize Even)so we check what sequence of Odd and Even should be interchanged, After interchanging, the sum of even indexes of the new array will be previous "even" sum + "max" difference of the sequence of pair which gives maximum means that if we reverse those pairs we will obtain the maximum for Even indexes.

      And to know why it gives max result see Kadane's algo.

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

    Thanks,this helped a lot!

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

    This is a really nice and clear solution :-)

    The dynamic programming approach with those dp[][] hmm... I guess I still need to think about it to understand it :-(

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

I still cannot understand A :(

"At first notice that if there exists a value for the second shop, then the value divisible by b also exists. " Why will it exist?

"For any x you can round it up to the nearest multiple of b." Where has this been used in the answer?

"then the value with 1 modulo b also exists (exactly 1 donut on top of some number of full boxes)." I really dont get this idea

Why have we split to x=b and x=1.

Thanks

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

    I also couldn't fully follow the solution from the editorial. What really help me is to visualize the problem. We have two functions: f = a*x and g = (floor(x/b)+1)*c. The g function looks like stairs. If you draw these two function, the solution is very intuitive. For example from the graph it will be clear that there are three cases (I) a>=c, (II) a<=c/b and (III) c/b<a<c. Only the case (III) is a bit non-trivial where either shop can be cheaper.

    Hope it helps.

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

      This helps but I cant see how hack each case further

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

        For item a, buying any amount of things will have the same price per thing. For item b, the cheapest price per thing will be when you buy b things. The most expensive will be when you buy 1 thing because you are forced to round it up to b since b > 1. From these deductions the answer is simple — to answer q1 compare prices for buying 1 thing: a < c — to answer q2 compare prices for buying b things: c < a * b

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

solution of D using kadane's algorithm code

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

For those who need some help with understanding the editorial :)

Check out the detailed explanations of:

Problem E

Problem D

Problem C

Problem B

Problem A

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

An alternative solution for problem F which uses this fact: There always exists a solution where nothing of $$$b_i$$$ is used to cover $$$a_{i+1}$$$ for some $$$i$$$ (this is true since we can transform any solution where this is not true to one where it is true by some sort of shifting).

If we know this $$$i$$$ we can just start assigning there with a greedy algorithm. To find $$$i$$$ in linear time we can just assume it to be $$$0$$$ and start with the greedy algorithm. If at some point we encounter an error we know that non of the indices between $$$0$$$ and our current position is a valid choice for $$$i$$$. So we can just choose $$$i$$$ as our current position and continue in the same way.

After the greedy algorithm reaches $$$n$$$, we have found one value for $$$i$$$ that either is correct or none such value for $$$i$$$ exists. We can then just run the greedy algorithm from $$$i$$$ and check if it works.

my implementation: 85071270

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

    Could you elaborate a bit more on why when we get error while assigning values with greedy approach then indices from 0 to current position aren't a valid choice for i?

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

      the error occurs because we can't satisfy a demand $$$a_j$$$. If we would choose any starting position between 0 and j we would have even less from $$$b$$$ available because everything would shift to the left.

      Or alternatively, if we start at $$$0$$$ we can use we can use some of $$$b_0$$$ and all of $$$b_1$$$ for $$$a_1$$$ but if we start at $$$1$$$ we can't use some part of $$$b_0$$$. Thus every choice between $$$0$$$ and $$$i$$$ would result in an error at position $$$i$$$ (maybe even earlier).

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

Video solution for problem G:

Link to the video: https://youtu.be/Nuym8ejFH_w

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

[Problem E] Can anyone proof that the answer should be in the form of "(prefix) (nines) (d)", where "prefix" does not end with 9, "nines" is a series of 9 and "d" is a single digit? For example, the answer might be like 198999992 (prefix = "198", nines = "99999", d = "2"). Or, am I making a mistake?

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

    "Oops"

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

      In that case, the answer is still in the form: "prefix" = 4998, "nines" = (empty) and "d" = 9

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

        Sorry seems like I misunderstood your question.... anyway the proof you are looking for comes from the fact when you find the smallest decimal numbers for which give digit sum : 1,2,3,4,..... the obtained series are: 1,2,3,4,5,6,7,8,9,19,29,39,49,59,69...199,299,399,499,.......1999,2999,3999,..... you can see it in by submission the formed arr[] 85157600

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

          your code is giving 799897 for 150 2 which does not match pattern

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

            Sorry, but I didn't quite get you. Which pattern are you matching it with??

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

              this pattern (any number)(nines)(not a nine)

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

                It is following the pattern:

                In the number 799897, (any number)(nines)(not a nine) => (7)(99)(897)
                
                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  3 months ago, # ^ |
                    Vote: I like it 0 Vote: I do not like it

                  but the last number has to be a single digit

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

                no the last digit need not to single, it can be greater than or equal to 0.

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

                  they wrote this(don't forget that the last digit should not be 9) in tutorial

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

              Bro, the tutorial is talking about middle part (x)

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

            (7998)(9)(7)

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

    Finally, I come up with the proof. At first, we have to notice that ALL numbers can be expressed by the form "( prefix ) ( nines ) ( d )" as in my previous comment. Please note that prefix and nines are allowed to be empty. Then we just greedily construct prefix part (of course to minimize the answer) while checking constraints:

    • the sum of k +1 numbers is equal to n
    • prefix does not end with 9
»
4 months ago, # |
  Vote: I like it +8 Vote: I do not like it

Can someone explain Solution 2 for problem F?

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

can anyone pls tell me what is happening in the question plus and minus

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

    just iterate from i = 0 to inf by taking cur = i, and for each iteration traverse the string from 0 to s.size(). while traversing if the character is '-' so decrease cur by 1 (cur--) otherwise increase it(cur++). if the cur < 0 so stop traversing otherwise stop iteration. Hope its help.thankyou.

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

D can also be solved using a sliding window approach. Did anyone else do that? I wanna check if I can reduce the lines of code in my solution :D

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

I find B so elegant. I submitted a suboptimal solution that also passed, I guess because it was B both were allowed. But the editorial solution is so so elegant!

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

Can someone explain the second solution of F?

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

In prob E, how can we be sure that the 2nd LAST digit of the answer should not be 9 (in the case our last digit may go over 9 only, like 99 100 101)

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

on the problem D .. "first array DEONTE the profit"....

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

Why did I get time limit exceeded on problem F when I solve it in o(n * log(maxval)), by binary searching how many houses the first station contributes to the second city? https://codeforces.com/contest/1373/submission/85451412

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

    Nevermind, I managed to get accepted. The problem was using cin for input, I switched to scanf.

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

Can someone help me with problem c? I really did not get why these formulas used?

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

can someone please help me in this submission link https://codeforces.com/contest/1374/submission/85383254 problem (E) i am getting error in test case 5.

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

Can someone explain the dp solution of question D in detail?

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

can any one explain me why i am getting TLE on 5th test case

my sublission is 85516199

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

    you will get TLE when the test case is many -1 -1 -1 -1 ... -1,at this time ,your code is O(n*n)

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

Don't need two dimensional DP for problem D, & I do believe this an easier dp to understand. https://codeforces.com/contest/1373/submission/86189153 If you require an explanation just comment.

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

    Please do explain your code

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

      Ok so the best ans can either be the sum without any reversals or : 'prefix up til i + reversed sum from i to j + suffix from j onward'. Since a reversal can start from any index i we will evaluate for all indices.

      So dp(i) is the best sum from i to end such that the reversal starts at i or there is no reversal.

      If i is odd, then dp(i) = max(dp(i + 2) + a[i], suffix) now whats happening here is that we can start reversing from this point on which would the mean to remove a[i + 1] ie even indexed position value & add a[i] instead and then take the best sum from i + 2 onward (omitting the even indexed value). We can also choose to do nothing & if we do make that choice then we have to take the suffix according to the definition of the dp (if you're wondering why I didn't take dp(i + 1) you'll find in doing so there is a risk to do multiple subarray reversals which isn't allowed & also because it goes against the definition of the dp).

      If i is even, then dp(i) = max(dp(i + 2) + a[i + 1], suffix) same reasoning as odd, to reverse we'll just add value at i + 1 instead of i & that will basically work as a reversal or if we do nothing just use the suffix uptill ith index.

      Now since our dp table is ready we can compute the ans like so, for all i: ans = max(prefix from 0 to i — 1 + dp(i), ans). Since all dp's are best sums from i and onward, such that reversal start from i, the only choice for the sum before i is the preifx sum.

      If there are any more queries just comment.

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

can someone explain problem c

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

If anyone need Detail Explanation(not a video tutorial) of D (without DP,prefixsum) Here

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

Can someone explain the solution 2 by Ne0n25 for problem F?

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

can some one explain how can i made this code more efficient (pluses and minuses) my submission is 85773685

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

For problem D, I am unable to understand the 2nd and 3rd transitions for the dynamic programming approach.

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

I came up with a greedy solution for F:

First make each $$$i$$$ th station give as much as possible to the $$$i$$$ th city without going over $$$a[i]$$$ and give the rest to the $$$(i + 1) \bmod n$$$ th city.

Then make each $$$i$$$ th station transfer as much excess as possible from the $$$i$$$ th city to the $$$(i + 1) \bmod n$$$ th city.

Code: 86164186

This was my first guess, and it turned out to be correct. I'm wondering why this works though, is anyone able to prove it?

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

how can we get 4 for testcase 42 7 for problem E

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

nlogn soln for F :) We just need to check for every subarray of circle that sum of bridges surrounding to cities (considered in subarray) is greater than equal to sum of households in cities (considered in subarray).

link to my submission

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

when a pawn is added or removed, we should add +1 or −1 to all values on some suffix

I think we should add +1 or −1 to all values on some prefix.

we don't need to look at the values on some rows with large indices, if...

So this sentence does not make sense.

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

For Probelm D, in the transition for dp[i+1][2] why are we taking max over dp[i][0] ? If we have stopped reversing the array then dp[i][0] can never lead to dp[i+1][2] since 0 means we have not reversed the array. Am I missing something? Same code without dp[i][0] expression passes the test cases. Here is the link

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

What is the Hall's theorem based solution for F ?

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

    For every circular segment, you need to ensure that the total number of connections provided to them is not less than the number of households. It can be shown that this condition is sufficient and necessary using Hall's theorem. This results in a simple $$$O(n)$$$ algorithm. 94510173

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

How does the dp transition in D ensure that there won't be multiple flips. For example — if dp[i][1] at some stage gets bigger than dp[i][0] and so in calculating dp[i+1][2], we used the former but later dp[i][0] gets larger and so,we use it in the calculation.

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

My solution For problem D is giving wrong answer. Problem is with maxSubarray function which calculates maximum subarray in an array. I ran same function on geeks for geeks and leetcode and it is getting accepted there. Can someone point out any problem with that function.