vovuh's blog

By vovuh, history, 7 months ago, In English

All problem ideas belong to MikeMirzayanov. And he prepared all problems himself. I just helped with testing, reviewing and tutorial writing.

1352A - Sum of Round Numbers

Tutorial
Solution

1352B - Same Parity Summands

Tutorial
Solution

1352C - K-th Not Divisible by n

Tutorial
Solution

1352D - Alice, Bob and Candies

Tutorial
Solution in O(n)
Solution in O(n^2)

1352E - Special Elements

Tutorial
Solution

1352F - Binary String Reconstruction

Tutorial
Solution

1352G - Special Permutation

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

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

so some of the participants are going to reach 1800+ ratings ? i believe this shouldn't be happening. CHECK THIS OUT

![ ](Capture)

edit : this is what cf predictor is saying.

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

    Obviously many experienced users made new accounts just to increase their ratings and Mike asked people not to do this but they won't listen. This is pretty bad and unintended.

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

      The contest is rated for only those people who have given at least 2 rated rounds I guess. Please correct me If I am wrong

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

        It is rated for unrated people too

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

          bro but i have not been rated and iu solved 1 problem

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

            The ratings haven't been updated yet

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

        NO, its is rated for those having rating <=1400

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

    I think there should be some limit on the max increase possible for this round. Otherwise, it is very unfair for participants with rating >= 1400.

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

      Removed, I realize I am wrong

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

        "unrated" starts off with 1500, then he gets 375, Add them up, what do you think?

        • »
          »
          »
          »
          »
          7 months ago, # ^ |
          Rev. 7   Vote: I like it -33 Vote: I do not like it

          Removed, I realized rating matters.

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

            "Regardless of whether you are a trusted participant of the fourth division or not, if your rating is less than 1400 (or you are a newcomer/unrated), then the round will be rated for you." - mike

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

        i agree that the big boost is bad but i don't think anyone who didn't deserve at least 1600-1700 rating could solve all the questions in like 30 mins. but 1800 rating is a bit yikes (which is the +300 rating), so i agree that the max gain should be lowered to around 250 at MOST (for when you solve it as fast as the reds). the problem lies more in smurfing though

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

      Also an important thing to notice is that out of the top hundred official participants, there are more than 60 users who have created a new account and these users increase as we go for further ranks, so this makes it even more difficult for the green/gray coders to increase their ratings.

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

    extension not working

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

    Just wanna know, how accurate this CF PREDICTOR have been in the past ??

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

      Completely!

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

      VERY. like only a difference of <=+5 or >=-5 is what I observed from the actual rating change in every contest I sit in.

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

    But even if someone with a low rating became Expert after this round, their rating will fall again drastically after a div 2 round due to the number of problems they will solve. So it doesn't make that much of a difference I guess!

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

      I agree with you,rating is not all,what the most important is we can improve ourselves by the codeforces

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

Can anyone explain the binary search solution for problem C?

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

    The number of integers not divisible by $$$n$$$ among numbers $$$1, 2, \dots, x$$$ is $$$x - \lfloor\frac{x}{n}\rfloor$$$, so you can do binary search to find suitable value of $$$x$$$ (such smallest $$$x$$$ that $$$x - \lfloor\frac{x}{n}\rfloor < k$$$).

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

    You may see my binary search implemented solution. 79500682

  • »
    »
    7 months ago, # ^ |
      Vote: I like it +1 Vote: I do not like it
    Binary search Code
    • »
      »
      »
      7 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      can you explain me why hi=1e10

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

        hi=2*k is sufficient for all the cases....taking hi=1e10 is unnecessary

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

          Yeah but with a runtime of O( logn ) it won't matter that much. I was just cautious (during contest) that's why I set a lenient upper limit.

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

      Your code should have been there in the editorial... also thanks for the comments

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

    Here is a video explanation of a binary search solution to problem C https://youtu.be/SuzXBjwRx7c?t=271

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

    Hi, I have solved the ques in O(1) time without binary search. You can see here 79680203

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

      can you please explain your code?

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

        I have used the fact that a number n for its every multiple adds (n-1) numbers to the tally of numbers not divisible by that number n. For example :- 3*1 = 3 leaves (3-1) = 2 numbers which are not divisible by 3 which are 1,2. 3*2 = 6 adds another two numbers to the list of not divisibility which are 4,5. total list becomes (1,2,4,5) i.e. 4 numbers. this is because a number will have n-1 numbers between its two multiples which are not divisible by that number and will have remainder 1 to n-1.

        d=k//(n-1)  # finding how many multiples of n-1 is that number
        r=k%(n-1)   # this is the remainder which will be added as an offset
        if(r==0):   # if r=0 i.e. n-1 divides k then it means the required number 1 less 
            r=-1    # therefore r=-1
        ans=(n*d) + r # this is the ans which depicts how many multiples of n has been used in k and + remainder to get the extra number
        
    • »
      »
      »
      6 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it
»
7 months ago, # |
  Vote: I like it +1 Vote: I do not like it

In problem C, how need=(k-1)/(n-1) ?

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

    This can be explained more easily if you understand that before each multiplier of $$$n$$$ there are $$$n-1$$$ integers not divisible by $$$n$$$, so we need to "skip" some number of such blocks. $$$\lfloor\frac{k}{n-1}\rfloor$$$ doesn't match because when $$$k$$$ is divisible by $$$n-1$$$ then we don't need to count the last block.

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

      won't number of such multipliers be k / n ? if n = 3 and k = 8 there are 8 / 3 multipliers of 3

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

        Yeah, but we want the numbers that are NOT divisible by n.

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

          for n=3, k=8

          1,2,4,5,7,8,10,11 k-1/n-1 +k gives Ans=8+3=11

          However, a simple k/n gives Ans=8+2=10

          I guess, there is a more complex logic of using k-1/n-1. Can anyone explain it in a simple way? Stuck at this for quite some time.

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

            okay so idk how simple this is but like n = 3 k = 9 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15

            so k/(n-1) is kinda like accounting for the extra cycle, because you need 1 less N to traverse a cycle (a cycle is 3 numbers, you only need 2 indices in this case to traverse the cycle). then k/(n-1) accounts for that extra N every time it cycles through (if u write it out on paper it makes sense lol)

            and if the cycle perfectly lands (when k%(n-1) ==0) then you gotta subtract one because you overcounted a cycle. for example, in the n= 3 and k = 8 case, if you did this cycle counting normally you'll end up with 12, but because the cycle cleanly divides you gotta subtract 1. at least i think that's how you do it idk it made sense when i wrote it out and went through cases

            and of course catch edge cases k == n and k < n

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

            From 1 to N, there are N-1 numbers not divisible by N. In every block of N numbers, N-1 are not divisible by N. So if we want K numbers, there must be at least $$$\frac{K}{N-1}$$$ blocks.

            Each block with N numbers. Let the number of blocks be B. This will take you to $$$B\times N$$$.

            So, from 1 to $$$BN$$$, you have $$$B\times(N-1)$$$ bad numbers. Count how many more do you need and add that to your current value. If you are already complete, then $$$BN-1$$$ is your $$$K^{th}$$$ Number.

            I hope I'm not making this complex. Code For Reference

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

              Much simple to follow. Thanks

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

              i wonder how vovuhs solution is correct :)

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

              Thanks a tonne doubleux...

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

              I still didn't get why are we subtracting 1 from k??

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

                To accommodate tha case when the blocks fit perfectly with no remainders.

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

                  Why the blocks shouldn't fit perfectly? Seriously I didn't get why are we subtracting 1 from k.

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

              nice dude, beautiful explaination...thank you!!!

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

            I got stuck at this for an hour and ruined my contest. D was definitely easier than C and it is unfair to put it after C.

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

              Exactly I got stuck too. It was a horrific contest for me. The problems were unsorted and Mike had mentioned it in the announcements. I checked it afterwards.

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

              I think the difficulty is subjective. I couldn't do B for a long time, switched to C, and I felt it was easier. I totally agree that D was easy to understand but the implementation can get a bit complicated. C was thinking based and if you get the trick, it becomes really easy to implement.

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

                Spot on! I had a look at G now and I feel I could have done it within five minutes if I didn't waste all my time at C. For me the difficulty wud be: A<D<G<B<C<F<E.

                Though now I am feeling stupid that can understand all the solutions except for C. I totally cannot understand how the formula could be derived. :/ At least, I can understand the binary search approach to it though

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

          "Each multiplier of n shifts our answer by 1. The number of such multipliers is need = k — 1 / n — 1" so he finds numbers such that are divisible by n

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

    You can Refer This Explaination

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

I attempted to solve F using dp[n1][n2][n3][ends] : answer to the original problem when you have n1,n2,n3 and the resulting string ends in "ends" ("0" or "1"). My Python solution seems to TLE. Is it because this solution is basically O(10^6) and the number of test cases <= O(10^3), overall O(10^9)? or am I doing something silly

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

    It's even worse than that, because there can be $$$c_0+c_1+c_2$$$ digits in each dp state, so you get something like $$$O(T \cdot (c_0+c_1+c_2) \cdot c_0c_1c_2) \approx 3 \cdot 10^{11}$$$, which will very clearly not pass.

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

      Could you elaborate where (c0+c1+c2) constant factor exists in my code? I can easily change it so that each state does at most 1 recursive call?

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

      it can be done using DP, see this: 79628831

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

        nice solution, just one doubt, inside the main function, how do I know whether to call solve(n0,n1,n2,1) or solve(n0,n1,n2,0), I mean both are equally likely to happen(except when we only want 0s or only want 1s in our desired string). Sometimes, I stuck with such doubts and hence unable to decide which way to call recursive dp functions. Can you explain why in main(), you called solve(n0,n1,n2,0) first and then when s.length() was 0, then you decided to call solve(n0,n1,n2,1). Rest is fine to understand.

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

          I assume you understand DP state, using 0 means string with ending at 0 which has n0,n1 and n2 count, but if there is no such string let's calculate one that ends with 1

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

            ok, so you're first guessing whether it can be done with string ending at 0, if not then you try it with string ending with 1. Right?

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

    solution must be independent of number of cases, if you use dp here

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

this round was so good and i had so much fun as a pupil and learnt new things i hope u do more div4 as u can <3

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

Can we do Div4-E with segment trees?

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

    You dont need to use it and it will most probably give MLE . Segment trees take huge amount of space and building and quering them would take additional logn time which would prove to be costly .

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

      Segment trees take O(n) space. MLE won't be an issue, I guess. It is just that you don't wanna use a sword for cutting lemons.

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

        But TLE might be an issue for sure . MLE not sure but still a bad choice for 64MB question XD.

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

        Segment trees actually take O(nlogn) space

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

      Segment trees take 4*n space. So it won't be a problem with MLE.

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

How to solve problem G using DFS (Depth First Search) ? I tried by joining numbers whose absolute difference satisfies the given condition and then traversing. How can I modify to make it work.?

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

    Checking all possible paths would lead to an exponential solution I think.

    There can be cycles too [2->4->6->2] (>_<).

    Maybe as someone mentioned above, don't cut lemons with swords.

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

    One thing I noticed while trying to solve G with DFS is that you are sure to get a correct answer by traversing along the longest path possible.
    Take n = 4, if you perform dfs traversal from vertex 1, you won't get answer in the correct format. But if you perform dfs starting from vertex 3, you get 3 1 4 2, which is the only possible answer.
    This is where I hit a dead-end, we need to solve longest path problem, which is ¯_(ツ)_/¯
    Expert opinion required.

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

    removed

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

      I tried checking all paths, worked for me too. :)
      But checking all paths' worst case time complexity is O(V*(V+E)). Could definitely be improved.

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

        I tried that too. getting TLE. can you please share the link to your solution?

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

          Sure, here is my submission using DFS, and checking all the paths 79649023.
          I apologize for all the unnecessary comments, they were mostly used to debug the program.

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

            No worries!! Thanks :)

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

Could someone try to hack 79593227? It does O(n * n * log(n)), which should be cut by the strict time limit but I couldn't hack it.

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

Can anyone explain the tutorial of the B problem in a much simpler way?

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

    Since problem demands that the n should be represented as a sum of k numbers such that all k numbers are either even or odd . So to construct the solution:

    1. Take the case when all numbers are odd : For this we can take k-1 one's which will make the temporary sum=(k-1)*1 and now we need one number which is odd and is equal to n-(k-1). We will consider this number only when n-(k-1) is odd and n-(k-1)>0 (it is given numbers should be >0).
    2. Take the case when all numbers are even : For this we can take k-1 two's which will make the temporary sum=(k-1)*2 and now we need one number which is even and is equal to n-2*(k-1). We will consider this number only when n-2*(k-1) is even and n-2*(k-1)>0 (it is given numbers should be >0).

    So for the final solution check sub conditions mentioned above and decide whether its possible to construct the solution or not and print the constructed solution (if possible)

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

    First you cheack if we can make n even numbers we make (k-1)=2 and n-(k*2)==even number so print Then else cheack ood newcomers make (k-1)=1 abd n-k== ood number so print Then if we can't do any thing print no

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

    essentially, odd numbers can only be made with odd numbers, and an odd amount of numbers at that.

    even numbers can be made with any amount of even numbers and an even amount of odd numbers.

    then you set all the numbers to 1 or 2 (depending on if you want the array to be even or odd based on those rules) and then the last number is the amount that ur left with after subtracting all of the 1s and 2s

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

I think my solution to G is a bit interesting. For all quadruples of natural numbers till the floor(n/4)th tuple can be arranged in order : 2 4 1 3, eg. 2 4 1 3 6 8 5 7 10 12.... and for the last incomplete tuple, it is easy enough to insert them in between elements of the last complete tuple.

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

can anyone tell me, how to solve G using bfs/dfs?

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

    The vertex set can be represented as the set of all numbers from 1 to n. The adjacent numbers for a node 'x' would be {x-4,x-3,x-2,x+2,x+3,x+4} provided they are in between 1 and n inclusive. Now you can perform DFS. The answer would be the DFS which satisfies the given condition in the problem. (NOTE: Edited: It will not be the DFS which visits all vertices...since the graph formed is connected, each DFS will visit all vertices) Even if you do a DFS from each number, the complexity would be O(n^2) (this include the time for checking the validity of the current DFS), which I guess would pass the problem constraints.

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

      i tried it earlier but its not working.

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

          Saw your code, inside the dfs() for a given node, you are try all possible relevant nodes to jump. I saw that you are only pushing nodes into your path array. Why ain't you popping the elements off, if you don't find the relevant path? Also, why in your main function are you checking val<2 && val>4, ain't you pushing the relevant nodes into you path array. You yourself first built the graph with reachable nodes, why is that condition checking even necessary?

          Kindly Help.

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

            I am not trying all possible nodes to jump. Take for example, N = 4, if you draw the graph the edges will be 1-3, 1-4, 2-4. If I start a DFS from node 1, the path array will contain elements in the following order {1,3,4,2}, which is not a valid answer. The correct answer would be the DFS that starts from node 2, {2,4,1,3}. A DFS generates a Spanning Tree, not a path. The path array is just storing the sequence in which the depth first traversal occurs and it may or may not be a path. In order to check whether it is a valid path (both in terms of the definition of being a path and the given condition of the problem), by just checking the given condition of the problem, I would be able to arrive at the solution.

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

              Wouldn't the if(val<2 || val>4) always hold false because you built the graph in way that only relevant nodes are traversed and after the dfs() call is over, you are again checking the same thing. Shouldn't you rather be checking if the lenght of path array is n or not. Because if it is n, then we always know that the path will be relevant(again because that's how you built the graph array and we will never be able to traverse irrelevant nodes(that do not hold the condition given in the question)). If you agree with me, then I still do not understand why without checking the path length that your solution is passing plus why that rechecking of (val<2 || val>4) condition when that's how your dfs function will traverse the nodes? Kindly explain.

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

                Please refer to my previous reply. In the example I have given, both have a length of n, but only DFS from node 2 is a valid answer. Refer to this link for better understanding.

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

                  You didn't get me, you stored nodes in the adjacency list such that they atleast differ by 2 and atmost by 4, then why are you doing checking it again after the dfs call. The dfs traversal will take care of jumping only to the relevant nodes. You said that the path array may contain {1,3,2,4} can you tell me how did you path store 2 after 3, when you don't have 2 in the adjacency list for 3?

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

    Check it out! 79806425

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

In the tutorial of problem D it is mentioned that we could solve the problem in O(n^2) but isn't the required complexity O(n) ? Correct me if i am wrong.

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

    O(n^2) is the time complexity and O(n) is space complexity. In this question space is unusually restricted so space complexity should not exceed O(n) but time complexity of O(n^2) works just fine

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

      I am talking about problem D not E.

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

        I think you overestimated the running time of O(n^2) in this problem.Simply (n^2)*T or (SUMn)^2 might not give the correct complexity in this problem. Just try using lagrange or some differential method and we get that worst case is when T=200 and all Ni = 1000, which can be optimized to 1e8 executions:Link

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

Can't this be a better O(1) approach for the C question testcases(t) { int n,k; cin>>n>>k; if (k<n) { cout<<(int)k<<nl; } else { int diff=n-1; int x=k%diff; int y=k/diff; int ans=(n)*y+x; if (ans%n==0) cout<<(int)ans-1<<nl; else cout<<(int)ans<<nl; } }

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

    Genius!! I read your code, and while I don't fully understand it yet, I'm sure that the time complexity can indeed be made O(1).

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

How to solve G question by dfs ? if anyone have done it by dfs mehtod can you provide me solution ? Thanks in advance .

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

The solution of G in tutorial is very good but how to come up with this solution? I mean the intuition for the tutorial solution.

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

    It's all about observation.

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

    I played with small permutations, trying to find a working block small enough so I could replicate it, and built the big N-elements answer. For me, it turned out to be a block of the first 4 numbers:

    2 4 1 3

    For N = 4 this is good. So as I said, I tried to make it work like a "brick" to build the answer, making chains of this block. So, if you have N = 8, you can "link" two of these structures:

    2 4 1 3 — 6 8 5 7

    And so on. Then I worked out on the case when N = 5 (more generally, when N%4 = 1), and I noticed that simply adding n to the sequence is ok.

    For N = 6, or N%4 = 2, you have to pop the last element (3) of your sequence, and mix the remaining two elements:

    2 4 1 5 3 6

    And lastly for N = 7 or N%4 = 3, an extra step, also removing the last element and mixing the remaining three elements:

    2 4 1 5 7 3 6

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

Am I the only one who solved problem G by graph?

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

    Can you explain your approach

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

      Make a graph of N nodes numbered 1 to N. Then for each node i add bidirectional edges between node i and i+2,i+3,i+4. After that Run dfs from each node separately, and check only for the straight path going from the node to any leaf node, if that path covers all N nodes then answer is the node of the path in the same order, otherwise if don't get any such path at the end, then answer doesn't exist.

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

        Got it. Thanks

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

        I saw in your code that in your dfs(), you have used break statement. If we don't get a relevant path by traversing from the given node then don't you think that then we should try for another node rather than giving yup our hopes that we won't find the right path if the very first node is unvisited. Moreover, in that case the path vector (in your code-v) will be not remain global but rather be passed in the function(in non-reference way)

        Kindly correct me, as to why your code used break?

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

    I just saw your solution for G, where you visit a node if it's not visited and then break out of the loop. What if you start from Node 1, then visit Node 3 and find out that permutation starting from 1->3 is not possible but permutation starting from 1->4 is possible ? You are not visiting node 4 from 1 as you have a break statement.

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

      What you are saying is theoretically not possible, can you give any test case?

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

        Yes, it seems like it's not possible after checking few cases. But can you prove that your solution always finds a solution if it exists? Also why is it theoretically not possible ?

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

        ok, nice, just one question, is that due to the order you store nodes in the adjacency list for a given node or what? Will that still hold if you change the order of placing elements in some random order inside the adjacency list?

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

          Did you figure it out ?

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

            Actually, changing the order of elements does not change the answer. But, I still didn't get the break; in the dfs in the for loop. If you got that, kindly reply.

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

      By looking at gjaiswal108's output it seems like you only need to start dfs from i=2.

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

is this contest unrated?

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

    Rated for participants below 1400 rating

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

Good contest! I only got 3 almost 4 but got stuck :"( I wish there will be another Div.4 round in future ~

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

Can anyone explain in Problem E why am I getting TLE when i am using map to count the frequency and find them 79611958 and it accepts the solution when i m using unordered map 79613165 i think in both cases overall time complexity is O(n*n). vovuh?

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

    Map has a time complexity of O(nlogn).

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

    The total complexity becomes $$$n^2*\log{n}$$$, which is higher than the expected complexity. The extra $$$\log{n}$$$ factor arises because of using map

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

      I used unordered_set instead of map. Which should be have constant Time Complexity for inserting and finding elements. Still TLE on subtask 3.

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

        I think unordered_set has a very high constant time factor because it uses hash table.

        Even though insertion could be O(1), the hash table updating is very slow. Therefore, the number of insertion operations that can be done in 1 second is lesser than that of typical constant time operations.

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

        You're using an array of size 1001 when the max input size is 8000

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

        Unordered (hash-based) sets/maps have average constant time complexity, but since the standard hash function is deterministic, a test case can be crafted specifically to cause a high number of items to be placed in the same bucket, degenerating it to a linked list.

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

Can anyone explain the case when n1 = 0 for problem F. Weren't we supposed to output a SINGLE string??????? I assumed that n1 = 0 would implicitly mean that either n2 = 0 || n0 = 0. Wasn't that supposed to be the case?????????

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

    yes you are right if n1=0 then only one of the n0 and n2 will be non zero in the testcase.

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

can anyone explain how case n0=1 , n1=0 , n2=1 will be handled in question F ??

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

    there is no valid answer for cases like n1=0 and n0 and n2 being both being non zero .your submission will not be evaluated on these type of cases.

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

could someone explain me the fallacy in my implementation of problem G using dfs..THX in Advance...

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

In problem C, why is need = (k-1)/(n-1) ?

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

Is there a way of doing E using sliding windows that doesn't cause TLE? or particularly any other way of doing E, I don't like editorials' solution for E, and was thinking if there is some other way.

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

    I got accepted with two pointers (which you can relate to sliding window). My approach was going through each element of the array and finding a subsegment with a sum equal to the element, as long as the difference between the two indices $$$l$$$ and $$$r$$$ is higher than 1. Two pointers has a complexity of $$$O(2n)$$$...so you can simplfy it to $$$O(n)$$$, and doing it for each element gives a complexity of $$$O(n^2)$$$.

    Here's my submission: 79549243

    Just to be sure, I also used printf and scanf instead of cin, cout and FAST I/O, as it can be even faster with large inputs. Also note that I could have also saved the result for previous numbers to make it faster when there are repetitions, but in the worst case scenario where that wouldn't happen, it wouldn't be of much help.

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

      Oh! I knew it can be done with a sliding window approach. Thanks for clarifying!

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

    use this function for each elements of array ,increment ans by 1 if this function return true,take care of the function it return true for subarray of length one also but in our case it should be at least two. overall time complexity O(n*n),space complexity O(n). my sol

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

did not receive a rating even after solving a question in the contest div.4

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

I partecipated in this contest and in Round 639 but they doesn't show up in the contests section of my account (I was unrated in both)

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

For the problem 1352G — Special Permutation

Many of the contestants have used some relationship of n with the modulo of 4

they have made cases like

n < 4 Not possible (Understandable)

n%4 == 1 some case

n%4 == 2 some other case

n%4 == 3 some other case

n%4 == 0 some other case

Can someone please share their approach here regarding the same?

Thanks

»
7 months ago, # |
  Vote: I like it 0 Vote: I do not like it
    ll two,one,zero;
    cin>>zero>>one>>two;
    string ans = "";
    bool started=false;
    char prev;
    while(two--){
        if(!started){
            started = true;
            ans += "11";
            prev = '1';
        }else{
            ans += "1";
        }
    }
    
    while(one--){
        if(!started){
            started = true;
            ans += "10";
            prev = '0';
        }else{
            if(prev=='0'){
                ans += "1";
                prev = '1';
            }else{
                ans += "0";
                prev = '0';
            }
        }

    }

    while(zero--){
        if(!started){
            started = true;
            ans += "00";
            prev = '0';
        }else{
            if(prev=='1'){
                ans += "00";
                prev = '0';
            }else{
                ans += '0';
            }
        }
    }
    cout<<ans<<"\n";

Can someone please explain me why this submission is WA. This is the link of my submission It went wrong on testcase 111, I do not understand why?

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

    1 1 8 1

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

      What do you mean by this Eureka17?

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

        Your code will output 110101010100. However there is 9 pairs that have 1 "1". The reason is that you probably didn't consider the case where there is even number of pair that has 1 "1". When this happens, before you add only zeros, the last digit of sequence will be 1 (the reason is you started with 0 and you add even number of digits). Because the last digit is 1, when you add zeros, one more pair that has 1 "1" appear.

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

          Thanks, I got it why I was wrong I cannot place the zeroes of n0 after ones of n1, since that will produce an extra n1 pair.

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

    For a case 1 2 0, your code is producing a output 10100. In your output n2 = 3, but it should be 2.

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

Can someone help me out, in problem A my code is working fine with testcase1 in Hackerrank editor and my terminal but it is giving different output when I submit it in CForces. Submission: https://codeforces.com/contest/1352/submission/79486521

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

    submit GNU C++14 or GNU C++17

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

    I had the same problem during the round. I fixed it by replacing pow function with a variable starting in 1 outside the loop, and multiplying by 10 each cycle.

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

I have used a hashmap in problem E but still TLE.Can anyone explain why i cant get it Accepted with this solution(https://codeforces.com/contest/1352/submission/79563004).I use java,can this be a factor as it is slower than c++.

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

    You are getting TLE because you are storing the sum of all consecutive elements in the map and then iterating it with loop. if there are n elements the map will contain nearly n*n elements. And then searching each element in the map will make your time complexity O(n^3).

    Also, you cannot use a map since it consumes a lot of memory. Your code's memory size is also greater than the memory constraints.

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

Solution

Please help me optimize it.

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

Consider case n1=0 separately and print the sting of n0+1 zeros or n2+1 ones correspondingly.

won't this make a 01 appear in the string while there should be no such pair in the string?

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

    (I kind of misunderstood what you said, so I'm rewriting my comment.)

    That sentence means how to handle cases like 3 0 0 or 0 0 4.

    For 3 0 0 you need 0000, and for 0 0 4 you should output 11111.

    Testcases such as 3 0 3 will not appear at all, since there must exist "01" or "10" somewhere so there is no solution for this case. The problem statement says that impossible testcases will not be given.

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

Video editorial of problem E.

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

Which libraries are allowed to import in python?

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

nice problems for rating<=1400....i learned a lot (mainly difference b/w sets and arrays)

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

Скажите пожалуйста почему в задаче C количество множителея не равно [n/k]?

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

Nice contest for beginners like me. Thanks Mike Mirzayanov.

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

ek baat batao saala tumlog B waale ka answer socha kaise? translated:- how did you come up the answer for B, I mean thought process.

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

    This wasn't the translation...

    If you understand properties of parity of numbers, then thinking a while you can come up with the solution.

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

      can you suggest some resource to study that might help for this type of questions?

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

        I learnt from a Bengali Language book. Assuming you won't understand Bengali, you may refer to very basic Number Theory book or tutorial which covers this:


        even ± even = even even ± odd = odd odd ± odd = even
        • »
          »
          »
          »
          »
          6 months ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          I thought you were talking about some solid stuff to study. I know this much. Thanks for your help.

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

These questions were really fun to solve, although I did horrible during the actual competition. I was motivated to solve all the questions for the very first time. Being new to the CC scene and facing Div 1/2 always seemed very overwhelming. Can't wait to get better and contribute to this awesome community!

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

Following is my logic for 1352F: Binary String Reconstruction:

First, if n0>0, I insert n0+1 0's and then if n2>1, I insert n2+1 1's, Now we have already created a pair of 01 in our string so we need n1-1 pairs. For this, I consider the last element of the current string and insert alternate bits in the end n1-1 times. For the last step, if n0 and n2 is 0, I insert 1 in the string and then insert alternate bits. The code is giving incorrect answer. My submission: https://codeforces.com/contest/1352/submission/79648402

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

Can anyone please tell me, will this solution pass if time limit was 2 sec? Thank you...

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

Can anyone tell me the problem with my Codeforces Round 640 (Div. 4) Ques B. Here is my code:

include<bits/stdc++.h>

using namespace std; int main(){ int t; cin>>t; while(t-->0){ int n,k; cin>>n>>k; if(k==1){ cout<<"YES"<<endl; cout<<n; } else if(n==k){ cout<<"YES"<<endl; for(int i=1;i<=k;i++) cout<<'1'<<' '; } else{ if(n%2==0){ if(k<=n/2){ cout<<"YES"<<endl; for(int i=1;i<k;i++) cout<<'2'<<' '; int number = n — (k-1)*2; cout<<number; } else cout<<"NO"; } else{ if(k%2==0) cout<<"NO"; else if(k>n) cout<<"NO"; else{ cout<<"YES"<<endl; for(int i=1;i<k;i++) cout<<'1'<<' '; int number = n — (k-1)*1; cout<<number; } } } cout<<endl; } return 0; }

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

    In your submission of that code, the judge says it failed in case 54 of the 2nd test, as you didn't give an answer to it, although it exists. Luckily that line of the test case is shown, and it seems that fails with 6 4. And as you can see, you can represent it with numbers 1 1 1 3.

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

Thank you for such contest!

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

thanks for editorial plz, add comments in code like the previous tutorial.it was more helpful

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

Anyone still struggling about writing a good comment?

I do :(

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

can anyone help me with problem c?

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

Can someone please explain me why in problem C the need is that specific value?( need=⌊k−1/n−1⌋) What is the math behind that. I've googled about it a lot but cannot find any answer. I would really appreciate if someone can help me understand that.

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

sorry if this is a dumb question ... but how for problem C (K-th Not Divisible by n) k-1/n-1 is correct.. i have got a little at the lower part is resetting the cycle but how n-1 and not n. hope for a answer with examples

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

    C Problem Explaination

    how n-1 and not n

    Because there will be n-1 numbers (which are non-divisible by n) between the two consecutive multiples of n.

    For Ex-n=7 k=97

    Non divisible numbers which are between first multiple of 7 and second multiple of 7 : 8,9,10,11,12,13 which is 6(n-1) here n=7.

    I did this Problem with the Formula k/(n-1) [Accepted] My Solution-79621837

    k/n-1 -> 97/6 = 16 + 97%6(Remainder)

    Now,16 means the n-1 elements are between the 16th multiple of 7(not included) and 17th Multiple of 7(not included).

    16th series of n-1 elements will be : 113 114 115 116 117 118

    Now we got the series where the kth element is present , Question is what will be the kth element in it?

    Kth element will be the Remainder of k/n-1 (k%n-1) So answer will be n*(k/n-1) + k%(n-1)

    But if Remainder is 0 which means the element is present in the last position of Previous(15th) series. Because 113 is the first element(97th position which is k) of the 16th series. So 0th element will be 111 which is 96th Position(if k=96)

    So Answer if Remainder is 0 is : n*(k/n-1) -1

    I Hope You Understood this!

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

Can Anyone Explain Why in Editorial of Problem D is it written that l<=r,why not l<r? Because if one of the two have already eaten that candy , how can the other one eat that particular candy?

Any Catch which i am losing in this?

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

    Because as said in the editorial: l is the position of the leftmost remaining candy and r is the position of the rightmost remaining candy.

    If you do l < r, then the one of the candy will remain uneaten (the one placed at when l == r) because for l == r, the loop will not run and the person with next turn would not be able to eat that candy.

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

      Thanks makkoncept For Replying. I understood your point but suppose if Alice has eaten that candy , and According to the loop's Condition(l<=r) bob can eat the candy but he shouldn't be eating that candy because Alice has already eaten it.

      Am I right?

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

    Can you explain to me why the tutorial of B is working?

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

My solution for 1352E had O(n^2) time and got TLE. Approach is quite similar to the one described in editorial. Perhaps the time limits are too strict

https://codeforces.com/contest/1352/submission/79526875__

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

    The issue with your code is that you are using map, and increases the complexity of your solution to $$$O(n^2*n log n)$$$, giving TLE.

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

    Use unordered_map or an array instead of map You will get AC.

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

Can anyone tell me if there is any mathematical intuition behind the derivation of formula ⌊k−1/n−1⌋ in .1352C - K-th Not Divisible by n

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

    You Can Refer this explaination

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

    for every n integers , there are n-1 integers before it which are not divisible by n; say n=4, then there are n-1=3 integers 1,2,3 which are not divisible by 4.

    so for after every n-1 positions,there is multiple of n . So our ans is shifted by 1; then for k postions, your ans is shifted by k/(n-1);

    but if k is divisble by n-1 , we dont need to count the final shift.

    So we can check for only k-1 pos , i.e shift= k-1 / (n-1)

    shift=(k-1)/(n-1); ans= k + shift ; print ans;

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

      Thank you for the explanation M.A.D.T.I.T.A.N

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

        the final shift is not added because the kth pos is the last element i,e n-1th pos in final series. since k doesnot cross the series we need not add it

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

      Thanks a lot. You know I read all the explanations for this problem but couldn't get my head around as why we were subtracting 1 from k, even some of the red coders's explanations. But yours is a brilliant yet simple explanation.

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

Can anyone Explain E with good explination. Thanks in Advance!

»
6 months ago, # |
Rev. 2   Vote: I like it -8 Vote: I do not like it

I'm trying to solve Problem F with this code.

#include <bits/stdc++.h>
using namespace std;

#define fro(i, s, n) for (int i = int(s); i < int(n); i++)
#define _fro(i, s, n) for (int i = int(s); i <= int(n); i++)
#define rfro(i, s, n) for (int i = int(n); i >= int(s); i--)
#define sz(a) int((a).size())
#define ll long long
#define pb push_back
#define in insert
#define F first
#define S second
#define E endl
#define R return
#define NL cout << endl;
#define gcd(a, b) __gcd(a, b)

// ********************************** C O D E ********************************** //

int main()
{
    int t;
    scanf("%d", &t);

    while (t--)
    {
        int n0, n1, n2;
        scanf("%d%d%d", &n0, &n1, &n2);

        if (n0 && n1 && n2)
        {
            _fro(i, 0, n0) printf("0");
            _fro(i, 0, n2) printf("1");
            fro(i, 1, n1) printf(i & 1 ? "0" : "1");
        }

        else
        {
            if (n1 && !n0 && !n2)
                _fro(i, 0, n1) printf(i & 1 ? "0" : "1");

            else
            {
                if (n0 && !n1 && !n2)
                    _fro(i, 0, n0) printf("0");

                else
                {
                    if (n2 && !n1 && !n0)
                        _fro(i, 0, n2) printf("1");

                    else
                    {
                        if (n0 && n1 && !n2)
                        {
                            _fro(i, 0, n0) printf("0");
                            _fro(i, 1, n1) printf(i & 1 ? "0" : "1");
                        }

                        else
                        {
                            if (n1 && n2 && !n0)
                            {
                                _fro(i, 0, n2) printf("1");
                                _fro(i, 1, n1) printf(i & 1 ? "0" : "1");
                            }

                            else
                                _fro(i, 0, n0) printf("0");
                        }
                    }
                }
            }
        }

        NL;
    }
}

and I got WA on test 2 in (test case 101). Help!

»
6 months ago, # |
  Vote: I like it 0 Vote: I do not like it
#include<iostream>
#include<map>
#include<set>
#include<vector>
#include<algorithm>
#include<cstring>
#include<string>
using namespace std;
typedef long long ll;
const int N = 8010;
int a[N];
int cal[N];
bool is[N];
int sum[N];
int main()
{
	int t;
	cin >> t;
	while(t --)
	{
		memset(is, 0 , sizeof is);
		memset(cal, 0, sizeof cal);
		memset(sum, 0, sizeof sum);
		int n;
		scanf("%d", &n);
		for(int i = 1; i <= n; i ++)
			scanf("%d", &a[i]);	
		for(int i = 1; i <= n - 1; i ++)
		{
			sum[i] = a[i] + a[i + 1];	
			is[sum[i]] = 1;   //here
		}
		for(int i = 3; i <= n; i ++)
		{
			for(int j = 1; j <= n - i + 1; j ++)
			{
				if(sum[j] != -1) sum[j] += a[i + j - 1];
				if(sum[j] > n) sum[j] = -1;
				else is[sum[j]] = 1;
			}
		}
		int ans = 0;
		for(int i = 1; i <= n; i ++)
		{
			if(is[a[i]])
			{
				ans ++;
//				cout << i << ' ';
			}
		}
		cout << ans << endl;
	}
	return 0;
}

why this code is accepted? where i mark "here",sum is out of bounds.

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

    problem E

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

    Arrays in C or c++ are allocated in contiguous memory. Let your array size is 6 and you store 8 elements in the array. Then the two extra elements may or may not be stored in the array. It depends on your memory location. If the two extra elements stored lie in another's memory location (i.e. stored in those locations where memory is already allocated) then the compiler will show some error, but if those additional elements get some unallocated memory or free memory then there will be no problem while running the program.

    In your case, the additional elements are getting free unallocated memory in the memory allocation (i.e. program's virtual memory), so your program is not showing any error. It varies compiler to compiler.

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

I feel div4B harder than 1329B - Dreamoon Likes Sequences, which is div1B. Div4B was too dirty kind of problem.

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

    That depends on the perspective and the mathematical background. For me 1329B is more or less unsolvable. I remember having read the editorial some days ago but still could not instantly tell how it works.

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

I Solved Problem E with two methods (One got Accepted Other got TLE)

1)I used an array to maintain the sum of every segment which Got Accepted Solution-79717264

2)I used map to maintain the sum of every segment which Got Time Limit Exceeded on test 6. Solution-79717344

Can Anyone Tell what is a reason behind it? Thanks in advance.

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

    zeph0yr , using array we can find the value at index i in O(1); whereas the value at index in map is found in O(logn) , as map uses Hashing. Basically the rest of the program uses O(n*n*checking value)

    For array sol: O( n*n*1)

    for map sol: O(n*n*logn). thus TLE!

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

I am getting WA on test case 2 of problem E Can someone help me know which test case can it go wrong? Link : https://codeforces.com/contest/1352/submission/79717403

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

    Hi! It seems that your code is a bit complicated and hard to debug You can refer the editorial which is good

    You can also refer my simple solution — 79717188

    You just have to calculate sum of all the subarrays possible except one. Complexity — O(n^2)

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

      Why are we doing if(cnt[a[i]]>0)ans++; and not if(cnt[i]>0)ans++; ??

»
6 months ago, # |
Rev. 2   Vote: I like it -8 Vote: I do not like it

say please, why the solution of C isn't k+[k/n]?

»
6 months ago, # |
  Vote: I like it -11 Vote: I do not like it

What is the binary search solution for problem C ?

Anyone please help !

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

In problem E. Special Elements, if I compute a prefix array and run two loops to take out sum and use hashing as used above to count the special elements, why does it gives TLE?

When this also takes O(n^2) and the above mentioned solution also takes O(n^2) ?

My Solution : https://codeforces.com/contest/1352/submission/79552941

Does it shows TLE even if memory limit exceeds ? If not then what does the judgement says ?

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

    You did not check the sum int k = pre[j]-pre[i]; to be in bounds of the array, but then write at that position. h[k]=0;

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

      Thanks, got an AC.

      Could you please state the reason as why does not checking the bounds gives TLE and not Runtime error ?

      Accessing something out of bounds gives Runtime error , right? Please correct me.

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

O(n) solution for problem D is also very simple. :)

(Ok, technically it is not O(n) since a.pop(0) is not O(1), but this can be easily taken care of at the expense of the brevity of the solution.)

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

No time complexity analysis. :(

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

n-(k+1)

n-2*(k+1)

I don't understand how almost everyone knows those equations except me..

Help me to understand how you guys come up with those formulae..

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

For Problem F .. The constrain (0≤n0,n1,n2≤100; n0+n1+n2>0 ) .

But n2 must be n2>=1 . if n0 = 1 n1 = 0 n2 = 2 output is = 00 . Why? and How !!!!!!!

if n2==0 there will no such solution that can satisfy the condition.

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

    It is guaranteed that the answer for given n0,n1,n2 exists.

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

      No , I guess for a case n0=(1..k) , n1=0 & n2=(1..k) we can't find any solution I guess. Please correct me If I am worng.

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

Can Anybody tell me the logic behind why l<=r and not l<r in alice,bob and candies sum??

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

    Because either of them will eat the candy at the index l=r. If you use l<r then 1 candy will remain uneaten.

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

      Harry122 Suppose if Alice has eaten that candy , and According to the loop's Condition(l<=r) bob can eat the candy but he shouldn't be eating that candy because Alice has already eaten it.

      Am I right?

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

        l is the index of leftmost uneaten candy and r is the index of rightmost uneaten candy. so when l=r happens, that means all candies from index 0 to index l-1 are eaten by alice and all candies from index r+1 to n-1 are eaten by bob. so candy at index l=r will be uneaten so in the loop we should proceed. Now if alice's turn is to eat candy then l++ will be done and all candies are eaten (l>r happens) and similarly if bob's turn is to eat candy then r-- will be done and again all candies are eaten (l>r happens).

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

          Thank you for the reply Harry122.I know the concept you are talking about , but Suppose Alice ate the candy at l=r then we should have not let bob eat that already eaten candy , because if bob also eats the candy then output will be wrong because it will be counted!

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

            Yes, Bob should not be able to eat that candy and the code given in editorial won't allow Bob to eat that candy as there is (l<=r) condition in the while loops inside the if-else condition.

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

              Yeah!I tried to prevent any risk by using an array which kept a count which candy is eatable and which candy is non-eatable.Which got Accepted!

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

Here is the easiest solution 79942144 for 1352C - K-th Not Divisible by n Though I am newbie, I have tried on my own way.You may have a look....

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

For F(Binary string construction), if n0=1, n1=0, n2=1, the editorial solution, gives output 00. Some other codes gives output 0011, which is incorrect. What should be the correct answer since no valid string is possible for this case.

Update- Missed the statement " It is guaranteed that a solution exists."

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

Guys I am a noob I need help with this problem 1352F Brinary String construction. ihave read the editorial I am trying a new approach need some help with that . Here's the solution : https://codeforces.com/contest/1352/submission/80051458

Hope you would help me out.

Gracias Lord_Thunder.

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

Can someone explain why am I getting TLE in question D, I know its an easy problem but I checked my while loops and none of them are recurring, idk why my code suddenly stops any bad practices you see,Thanks My Solution

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

how is f question tagged as dfs. How to use dfs to solve this

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

In problem D ,what if the both alice and bob took 2 steps and size of candies eaten by alice is array[0] and bob eat sumofarray-array[0].why this solution is wrong because on 2nd time bob eats all the candies remaining after the first move...plzzzz Helpe me upon this.

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

It's my solution (80618856) for D (1352D - Alice, Bob and Candies).Hope it will be easier to understand.

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

Problem 1352F Can someone please explain why am I getting TLE in this solution

This is my submission

Since maximum number of elements inside the string will be always less than 500 and number of independent test case is 1000 so we can solve the question in O(t*n) time right?? But why I am getting TLE here?

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

Why is my code getting the wrong answer in problem G: Special Permutation? I have made the permutation using all the odd numbers below n, then all the even numbers below n and if the number is less than 4 then the permutation is not possible. my submission- https://codeforces.com/contest/1352/submission/81379552

»
7 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Can anyone please explain to me why the approach given in the tutorial of 2nd question is working? Thank you

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

In C can someone explain why it is (k-1)/(n-1) and not k/(n-1)