Please, try EDU on Codeforces! New educational section with videos, subtitles, texts, and problems. ×

Stepavly's blog

By Stepavly, 6 weeks ago, translation, In English,

All problems were invented by MikeMirzayanov and developed by me, Stepavly, and Supermagzzz.

1360A - Minimal Square

Editorial
Solution

1360B - Honest Coach

Editorial
Solution

1360C - Similar Pairs

Editorial
Solution

1360D - Buying Shovels

Editorial
Solution

1360E - Polygon

Editorial
Solution

1360F - Spy-string

Editorial
Solution

1360G - A/B Matrix

Editorial
Solution

1360H - Binary Median

Editorial
Solution
Tutorial of Testing_contest
Tutorial of div3 E-onwards #1
 
 
 
 
  • Vote: I like it
  • +89
  • Vote: I do not like it

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

    Really awesome, You try explaining your thought process as well while drafting editorials. Kudos!

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

    great i know the tutorial isnt that great but u r a programmer not youtube ,it takes time don't worry.

»
6 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it
  • »
    »
    6 weeks ago, # ^ |
      Vote: I like it +4 Vote: I do not like it
    if ((i <= n) and (n % i) == 0) {
        if ((n / i) <= k)ans = min(ans, i);
        if (i <= k)ans = min(ans, n / i);
    }
    

    Try using this block of code... your code is missing the (i<=k) condition

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

      I also missed out on this one and got the same 3rd testcase wrong. But I am not able to understand that if I am iterating from i=2 then if (n%i==0) then do we need to check that n/i is smaller? I mean i is already smaller and all the 'n/i's are on the other side of sqrt(n). So, when we get n&i==0 && n/i<=k we break and print the value of i. Is there an example to contradict this? The testcase is on a very large index so it is just ... and I'm not able to see it. Here is my submission : 81251157

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

        Try this case : n = 14 , k = 2 I am sure you will understand why both the if() conditions are necessary. Also seeing the constraints of the question I would not go for breaking out of loop just for the sake of execution time. Although one small improvement you can do is iterate on the smaller interval of [1,k] , [1,sqrt(n)]

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

          Thanks darshancool25! I now understand it. I was checking just the 'i's and the corresponding 'n/i's may dissatisfy the <=k condition and the 'i' is lost, although it was divisible. And since we are only iterating till sqrt(n) we might not get another divisor and the loop exits. Therefore I need to check both i as well as n/i for the minimum.

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

          thanks it helps me too.

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

        you are getting WA in tc3 ?

    • »
      »
      »
      6 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it
      • »
        »
        »
        »
        6 weeks ago, # ^ |
          Vote: I like it 0 Vote: I do not like it
        if(i <= k && n%i == 0){
            ans = min(ans,n/i);
            if(n/i <= k)ans = min(ans,i);
        }
        

        Instead of above code you should write below one and also start iterating i from 1 instead of 2.

        if(n%i == 0){
            if(i <= k)ans = min(ans,n/i);
            if(n/i <= k)ans = min(ans,i);
        }
        

        Also , your code gives ans as n only when (k==1) or (n is prime) which is incomplete. Try this case : n = 49 , k = 6

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

          Hey Can you help me with this submission https://codeforces.com/contest/1360/submission/81362630 @darshancool25

          What I am doing is, I am creating a 2D array of characters. I am going through each element. If I find a 1 I am checking if the right element or bottom element is 1 or not for cells that are not in the last row or last column. If that is not true I am printing no and breaking out of the loop.

          For the cells of last row or last column (i.e r+1==n ||c+1==n) i am just continuing to the next cell I am really stuck with this . please help :)) Thanks in advance

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

            Your logic is correct... basically if there exists a 1 with its right and bottom element both equal to 0 , then ans is NO , else it is YES. I saw your implementation , its a bit complex to understand. Here's my code (I have used same idea as yours!)

            if (s[i][j] == '1') {
              if (i == n - 1 or j == n - 1)continue;
              if (s[i + 1][j] == '0' and s[i][j + 1] == '0') {
                poss = false;
                break;
              }
            }
            
            • »
              »
              »
              »
              »
              »
              »
              6 weeks ago, # ^ |
                Vote: I like it 0 Vote: I do not like it

              Cool, Thanks a lot :))

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

              @darshancool25 could u plz clarify or explain me that ur solution is of order of n square where n is size of matrix.. how this is working fine for such constraints?

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

                There is no need to check the whether the last row or column is 1 or not ,that continue part in your code is unnecessary as u r always checking i+1 or j+1 thus you will always check a[i][n-1] or a[n-1][j] if the previous element is just before the border elements

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

                It is clearly mentioned in the question statement that : "The total area of the matrices in all test cases in one test does not exceed 10^5". I hope that answers your question!

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

            u must take input as 2d array of char and not int i was facing the same difficulty hopefully it helps u

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

      for(i<=k) why ans=min(ans,n/i) i m not getting the logic.plz help why we are using the 2 min conditions

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

      why this one is not working for(long long int i=2;i*i<=n&&i<=k;i++) { if(n%i==0) { ans=min(ans,i); if(n/i<=k) ans=min(ans,n/i); // ans=min(ans,n/i); } } if(k>=n) ans=1;

»
6 weeks ago, # |
  Vote: I like it +8 Vote: I do not like it

For problem C case 2, how can we be so certain that we are only looking for one pair with a difference of 1?

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

    A pair with a difference on 1 contains an odd number and an even number. Therefore removing that pair means that both the count of odd values and the count of even values is decreased by 1. We need both the count of odd values and even values to be even numbers (so that we can make pairs). Therefore if the count of odd values and even values are both odd, we can remove 1 pair with difference 1 to make them both even, and then do the rest of the pairing by parity.

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

    We create pair of those numbers with diff 1 and after that we have even $$$e' = e - 1$$$ and $$$o' = o - 1$$$, then it is first case.

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

    Suppose if you divide the elemnts in even and odd set(Notice then each set will have same parity elements), if both the set contains even number of element the it is straight "YES" because they will form pair among themselves. But if both the set are odd, and if we find just 2 elements (one from each of these set) with difference 1 then output "YES" else "NO" .This is because rest of the elements in each set will form pair among themselves since they were having same parity . I hope this is clear.

»
6 weeks ago, # |
  Vote: I like it -17 Vote: I do not like it

Max flow solution for G is easier and more straightforward. 81283859

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

Did someone else use flows in G xD? https://codeforces.com/contest/1360/submission/81285900

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

    Yes and it's very neat

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

      Bashing a simple problem with an overcomplicated tool is not "neat".

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

        I don't see what's over-complicated but anyway it's just my opinion you know

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

          If you don't see why flow is way more complicated than a cyclical filling pattern, then you're blind.

          Replacing thinking ability by direct application of knowledge will be harmful to your long-term progression, especially in the current CP meta.

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

            You didn't get me. I'm not saying my solution is easier than anyone's solution. But it's also not complicated as you're claiming, you just said it was direct application.

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

              Flow is extremly hard to come up by yourself, way more than coming up with an elementary solution to this problem. That's why I say it's an overcomplicated concept for this problem.

              Of course, copy-pasting Dinic is easy in itself. Everything is easy to copy-paste. But you're not training yourself to come up with new ideas. That's why I say it's not neat at all.

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

                I was tempted to implement a flow-based solution but I figured that it would take me less time to come up with a "normal" solution than to copy-paste dinic, and I was right.

                Also C can be done using the blossom algorithm

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

                  Meanwhile can any one explain the flow approach?

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

            "Replacing thinking ability by direct application of knowledge will be harmful to your long-term progression, especially in the current CP meta."

            How nicely you explained it! I always think that too. But couldn't come up with nice words like you.

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

    [user:andr0901]Can you pls explain , how did you apply flows in this .... I know max flow algorithn but not able to figure the way to proceed with that

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

    Can you please tell- since the graph will not be unit-graph so complexity will be $$$O(V^2E)$$$ instead of $$$O(EV^{1/2})$$$ for unit-graph. Also edges will be of order $$$V^2$$$ So for $$$1000$$$ test-case time will be $$$O(1000*(50)^4)$$$ but still it's not giving TLE. why? Am i wrong in computing complexity? Please Help.

»
6 weeks ago, # |
  Vote: I like it +8 Vote: I do not like it

In G, isn't shifting by $$$a$$$ enough?

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

    Worked for me 81291367

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

      is your code same as this explanation link:stackoverflow, if not could anyone explain what language is used in this and how to solve this using linear programming.

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

      Very neat code. Great!!

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

      I used count array for columns, at each instant I know how many 1s are in that column. So I iterate row by row and in each row, I find column having cnt[j] <b and do cnt[j]++ until I reach value a for that row. I don't know why it is not working. Please help 81417040

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

    Yes,Shifting by a when did the same thing for b times

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

    can you plz explain!!

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

    Can you please explain after shifting each row by 'a' how are we ending up filling each column by b ones ?

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

      I just put a 1 on the column that has the least 1's without exceeding $$$a$$$ for every row.

      Doing that from left to right is the same as shifting by $$$a$$$ the previous row.

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

      Sorry, I didn't answer your question.

      In the editorial, we have to find a $$$d$$$ such that $$$(d\cdot n)\%m=0$$$. If $$$a\cdot n=b\cdot m$$$, then $$$b=\frac{a\cdot n}{m}$$$, which makes $$$(a\cdot n)\%m=0$$$

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

    Yes,that works. 81375672

»
6 weeks ago, # |
  Vote: I like it +40 Vote: I do not like it

It was closer to a Div.4 than a Div.3, as far as I think!

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

    Do you mean Div 3.51-3.99

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

    True dat but this was previously a div 4 contest so yay similiraty is not that uncanny !

»
6 weeks ago, # |
  Vote: I like it +18 Vote: I do not like it
»
6 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

https://codeforces.com/contest/1360/submission/81263548 why is the ans wrong for test case 3

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

    You are calculating the maximum value of "count", i.e. the maximum number of pairs that are similar because their difference is 1. This value can be even in some cases. You should stop as soon as you find odd number of such cases (might stop simply at 1). So after subtracting "count" (which is odd) from "x" and "y" (which are both odd), the resultant "x" and "y" will be even.

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

    Lets say you have odd no of even no's and odd no's now as soon as you find a pair with diff 1 you can stop counting as in this case count of both even and odd no's will be (as x -y == 1 if x is even and y is odd or vice — versa ) so once you have gotten one such pair the job is done !
    https://codeforces.com/contest/1360/submission/81251269 you can check this for reference

»
6 weeks ago, # |
  Vote: I like it +9 Vote: I do not like it

Why unnecessary $$$O(n^2)$$$ editorial solution for B? Even the explanation describes a $$$O(n \log n)$$$ solution.

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

    I was also surprised, first they sort and then use O(n^2) complexity for judging all the pairs. xD

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

    After checking their code, I went to check my code again for checking its correctness.

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

    Haha yes. Thanks for confirming, I was worried my solution might get hacked as it is incorrect

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

Next time, please mark such contests as Div 4

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

    Totally agreed. Even the last questions were easy go.

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

can we do problem D using binary search?

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

    can you binary search for factors of a number? not sure if you can

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

    No maybe.

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

    Yes, you can. First you can store all the factors of n. Sort the array and then use the binary search(upper_bound) to get the biggest factor in the range from 1 to k (inclusive).[submission:https://codeforces.com/contest/1360/submission/81351614][submission:81351614]

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

      yes, i know it but can we do it in O(logk) or O(logn) [base 2]?

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

        I don't think we can do it . If a sorted array can be divided into two parts such that one part is true and other false, using binary search we can find out the first value that is true or last value that is false and vice versa.

        But in our case from 1 to k we cannot separate the numbers to two sets of true and false as mentioned previously.

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

      but why upper bound k since factor should not be greater than k

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

        Yaa, you are right about it. Its just my habit of using upper_bound() for finding an element as it saves an if check if I use a lower_bound and you can directly use the element previous to that index if using upper_bound().

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

          oo thanks got it similar approach is used by me but i used set ..anyway thanks

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

      I didn't get it, why do we need to sort array? It's already sorted, you're pushing factors in ascending order. Isn't it?

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

        No, I am not pushing the factors in ascending order entirely. I am iterating only to the square root of N and storing all the factors along with their multiplicand to get N.

        eg: 24 -> I will iterate till 4, Store 1 and 24, 2 and 12, 4 and 6

        As you can see we have to sort.

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

          My bad, didn't notice if(i*i != n) v.PB(n/i); statement.

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

Thank you for the tutorial!

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

In question H did you mean to say that after deleting n strings the median cannot change by more than n/2? I was a bit confused because of that, but I may be wrong.

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

I've noticed that many of the test cases for D — Buying Shovels are just the same two numbers repeated t times. Is there a reason for this ?

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

    It is a prime no. so O(n) solutions with a break statement would fail. A lot of same test cases as a the solution might barely pass on a single test case.

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

      Thanks! That makes sense.

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

I think there's a O(N*M) solution for problem F (and it works even if we aren't restricted to 26 letters).

Compare every string with the first string:

  • If all strings have at most one differing character from the first string, the first string works
  • If any string have exactly two differing characters with the first string, then there are two possible answers and you can verify them in O(N*M) each. For example if you found two strings "... a ... b ..." and "... c ... d ...", the only candidate answers are "... a ... d ..." and "... c ... b ..."
  • If there are more than 2 differing characters, return -1. This is because all strings should only have one difference with the answer which means they can only have at most two difference with each other.

Commented python solution: https://codeforces.com/contest/1360/submission/81330345

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

    I don't know much syntax in python but it is looking O(N*max(N,M)) to me. But n and m are small so no need to worry. If n>>m then it would cause problem.

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

      Where does your N*N come from?

      Diff N-1 strings with the first string, O(M) work per diff, for a total of O((N-1)*M).

      If you found any diff with exactly two differences, you generate 2 solutions of length M which needs to be checked with all N strings for a total of O(2*N*M).

      So total is something like O(3*N*M)

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

        for comparing every N-1 strings, you call the function twoDiffAnswer. In that function, you run this loop "if all(sum(1 for x, y in zip(w1, w2) if x != y) <= 1 for w2 in A):" which I think runs almost N times.This gives O(N*N) if N>>M. But I am not that much familiar to python so maybe I am incorrect.

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

          The line you quoted is O(N*M), not N.

          But it's only ever ran twice (you return the answer after), not N-1 times.

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

        I also found that your solution runtime(108,124,124,139) for first 4 test cases is larger than my solution runtime(30,0,30,30) https://codeforces.com/contest/1360/submission/81312565 which is same as editorial. Can you explain?

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

how did you guys approach, your thought process to find out how to arrange all the one's

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

.

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

In the problem F- Spy strings,

Can we reduce the complexity of O(m * 26 * n * m)? If so, can anyone explain how to do so? Thank you.

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

    You can probably precalculate the hamming distances of each pair then for each possible string, only check if the changed character affects the hamming distance.

    Precalculating=O(n*n*m) Trying each string=O(n*m*26*n)

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

    I have done it in O(n*m*m). Initialise your answer with the first string and test 'm' versions of this string such that in version 'i', the ith character can be changed. For testing a version of the string, check all the characters except the one that can be changed. If the strings differ in exactly one place, then the ith character can be fixed according to the string it is being tested with. After you have changed the string, all the characters of the string should be tested. You can refer to my Solution

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

    https://codeforces.com/contest/1360/submission/81249769

    you can check my submission

    Explaination: — Assuming s[0] as an answer now change every letter to a to z and check whether it is possible answer or not

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

      Wow, can you briefly explain?

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

        Lets take two strings a and b , and solve for these two only for now. Lets define getDiff(a,b) = No of positions i in which a[i]!=b[i]. Let currAns = a.

        if getDiff(currAns,b)<=1 , then you have found the answer.

        else if getDiff(currAns,b) = 2 , then we need to change our currAns

        else , we cannot find the answer you can prove that.

        Lets modify currAns so that getDiff(currAns,b) <=1. How ? Let a = "abc" and b = "ebd" and currAns=a

        We can see that getDiff(currAns,a) = 0 and getDiff(currAns,b) = 2

        We have two options to reduce the difference.

        One is change currAns[2]=b[2] , then our currAns = abd.

        After changing one character we can easily see that getDiff(currAns,a) =1 and getDiff(currAns,b) = 1.

        Second way is to change currAns[0]=b[0] , then our currAns = ebc and we can easily see that getDiff(currAns,a) =1 and getDiff(currAns,b) = 1.

        I have used this idea to solve for n strings. Since we have proved that for solving for 2 strings we have only two options if getDiff(a,b) = 2 , we can use these answers to check if one of them satisfies all the strings or not else the answer wont exist.

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

Don't you think Codeforces has decreased the difficulty level of Div3 very much as compared to past contest.Even Question F and G based on implementation.

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

    It is because this contest was previously designed as div4 and later converted to div3

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

If anyone is interested F-Spy-string Solution with explanation Here

»
6 weeks ago, # |
  Vote: I like it +1 Vote: I do not like it

Is there a more generalized solution for problem F? Not that the given solution is bad or anything.

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

In problem G, can anyone explain What is the idea behind choosing d such that 0<d<m such that (d⋅n)%m=0. Please explain.

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

how is the approach given in tutorial for F correct? I mean how can we prove the correctness of this approach ?

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

Can anyone tell me what is the test case #57 for test set 2 in problem F ??

»
6 weeks ago, # |
  Vote: I like it -12 Vote: I do not like it

Bi*ch where are the rating changes?

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

Did anyone try attempting problem E by BFS/DFS? or the trick stuck everyone right at the moment?

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

Video tutorial for problems A-F

https://youtu.be/l04suY9DjEA

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

Someone please explain the C problem ,I really dont get the tutorial logic;

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

    The problem wants you to partition the array in pairs. A pair is valid if both of its elements have the same parity. So if you have an even amount of, for example, odd numbers in the array, it means you can already put all of them in pairs. The issue is when the number of elements of the same parity is odd. If that's the case, you would be left with one element unpaired. So the only other way to pair that element, is if there's an element that's also unpaired, from the set of numbers of the other parity.

    So at the end, you can partition the array if the amount of odd numbers and even numbers are both even (as you can pair them between themselves), or if both are odd and if you can find a pair of elements of different parity whose difference is 1, making it a valid pair. Those two you choose would be the unpaired ones I mentioned. Also, this means if the number of odd numbers is even, and the number of even numbers is odd, or vice versa, you can't partition the array as you would be left with one unpaired element.

    Knowing all of this, approaching the solution is counting the number of even elements and odd ones, and if you have the special case where both quantities are odd, you can easily sort the array and check for adjacent elements if their difference is 1 (as in that case they would have different parity).

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

      Thank you very ,much. I was just doing some silly mistake while checking for the odd-odd case

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

really nice problem i like it and i hope DIV 3 round be like this

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

How H can be solved by binary search?

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

my rating is not updated

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

I am not able to find why I am getting run time error in test case 5 in problem H. Can someone please help. Link to my solution: https://codeforces.com/contest/1360/submission/81360379

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

    You are using int and stoi.

    m can be 60, but int has only 32 bits.

    So, you can see stoi throwing an instance of 'std::out_of_range'

    You should use long long and stoll instead

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

    Your idea to solve this problem was great! I solve it using u'r idea just implemented my stoll :) Thanks . And my submission 82378262

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

rating +300, LOL.

My solution for problem H in contest:

Realize that there's NO DIFFERENCE deleting TOO SMALL/BIG numbers and SMALL/BIG ENOUGH numbers. Just make [2^(m-1)-128,2^(m-1)+127] in a container, and delete numbers, output mid.

https://codeforces.com/contest/1360/submission/81278827

And another elegant solution. https://codeforces.com/contest/1360/submission/81358112

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

https://codeforces.com/contest/1360/submission/81364055
Why i am getting WA on test case 3.

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

Could anyone explain "Binary Median" editorial ,i did not get how to proceed with this problem?

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

    At the start, without removing any binary number, the median is 2^(m-1).

    Then for each string removed:

    1. If it is smaller than the current median, the median either goes up by 1 (if there is an even number of numbers left) or it stays the same (if there is an odd number of numbers left).

    2. If it is more than the current median, the median either goes down by 1 (if there is an odd number of numbers left) or it stays the same (if there is an even number of numbers).

    Note that you need to skip over all strings which have already been removed when you are going up or down by 1.

    Here's my submission if you need it: 81298077.

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

Can anyone please tell me why my solution 81366886 is getting TLE on TC5?

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

I wanted to share my solution for G as my approach was a little different from editorial's and is easier to think and implement. I decided to iterate over columns from 1 to m and put b 1s greedily based on the number of 1s in each row. For that, I used a set of pairs {number of ones in this row, row number}. So for each column, just put 1s on the intersection of that column with the b rows with minimum number of 1s that is, first b rows in the set (and update set after putting each 1). And then check for the validity of solution by counting number of 1s in every row and column. 81293437

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

https://codeforces.com/contest/1360/submission/81366312

Why am I getting TLE for this approach, please help me I have just started ! P.s: Problem is D

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

    And I really didn't understand the editorial for D !

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

    You are iterating for 1 to k linearly and k can be as large as 1e9. You can perform upto around 1e8 iterations in 1 second time limit. That is why time limit is exceeded. Find a way to find divisors of n in less than linear time. See editorial for that.

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

For today's G there is a pretty simple and nice-looking solution. Check it here: 81371851

  • »
    »
    6 weeks ago, # ^ |
    Rev. 2   Vote: I like it +5 Vote: I do not like it

    it's awesome, but why?

    update:
    understand, first n * a == m * b, that is count of '1', we can know that fact:
    n * a >= m and n * a mod m = 0 and n * a / m = b.
    make n * a divide by m, exactly perm b block, each block have m count of '1', distribute them by index [0, m — 1]. finally we get each index in [0, m — 1] count b times(for column).
    for row, distribute n * a by divide a, also get index in [0, n — 1] count a times.

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

how we can use the similar direct approach to get the largest divisor d of any no. n such that n/d is <=any number k??

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

Can anyone explain problem D to me? according to me the answer to the fourth test case should be 2 packages, 1 package of 999999732 shovels and 1 package of 1 shovel.

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

    You need to find the minimum packages required in order to buy n shovels. Hence, you need to find the maximum divisor of n (no of shovels) that is less than k (no of packages). Also all the packages bought must be same. You can not buy 1 package of 999999732 shovels and 1 package of 1 shovel. Thus, 999999733 999999733 Max divisor of 999999733 which is less than 999999733 is 999999733 itself. And you need to buy just one package

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

      I see, only one type of packages are allowed, thanks. I was talking about 999999733 999999732 test case, just so I don't look dumber than I already am.

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

Video explanation to Problem G. A/B Matrix | Codeforces Round #644 (Div. 3)

I found this video interesting, where he explains the edge case and the approach. I think this may help you guys to understand the solution of problem G.

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

I think rating change in this contest unjust,who agree with me?

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

can someone help me in this for problem D. It is giving wrong answer on tc 3. https://codeforces.com/contest/1360/submission/81375221

thanks

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

    You should put in if condition if (a%i==0 && i<=k) { ans=min(ans,a/i); if (a%(a/i)==0 && a/i<=k) ans=min(ans,a/(a/i) ) }

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

I was emailed about the violation that my solution 81275866 for the problem 1360F significantly coincides with solutions anishde85/81257823, ycui11/81275866, keep__calm/81282151. After I take a look at details, I found the only thing we are in commons is we used a template for FastIO to read input faster, and the template is used from the previous submmisoin, which the author published under contest blog, is it considered as a violation? Thanks! MikeMirzayanov

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

can anybody tellme why my code failed for 4th test case in problem A. my code: https://codeforces.com/contest/1360/submission/81283489

81283489 thank you!!! pardon my for asking silly doubts , but this is the first time i am asking and i am really trying hard to solve the problems but, i dunno why i am not able to solve even problem A . i am becoming desperate and loosing my mind. thank you for reading. plz help. i am not great at understanding others code too.

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

    Lets say a is the smaller side and b is the bigger one. Now we keep bigger sides parallel and make rectangles touch, which will make one of the sides 2a(Note: you can't make smaller sides parallel, because it will make one of the sides 2b, making square bigger than required). Now we have to contain both the sides into square, so we will make side of square equal to the bigger side. Here's my solution.

    Also, you don't have to use any other headers, when you use #include<bits/stdc++.h>, as it contains all the libraries of c++.

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

      Thnx man u were a great help. And ur code was also very easy to understand. Thnx a lot. And regarding the header file, And I use header file also so that I don't forget which functions are under which header file, but most ppl use bits/stdc++.h which some says is lazy so I kind of do both. And previous to this I was learning how to use sort() so that's why it's #include here instead it should have written #include . Phewww thnx agian

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

Can someone explain how you can notice the solution for G?

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

    First you must look whether answer is YES/NO. This can be easily be checked if a*n == b*m.

    Now as you have asked how to notice the pattern , let me explain my thought process in approaching the answer.

    First check on most basic cases. Ex. n=2, m=2, a=1, b=1. You may easily visualize it as a 2X2 matrix which has all the elements along main diagonal = 1 and rest = 0.

    Now try a=2, b=2. When you check such 3 to 4 basic cases you will start finding a pattern.

    So rather than trying to find answer for some random cases try building it step by step, you will figure out the way. This is not just an answer to a particular question, but rather applies to a variety of problems that require keen observation skills.

    I hope this is what you wanted.

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

      Thanks. I guess that's basically what I did, but I found the wrong pattern so I messed up :3.

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

      please can you explain why we have to find 0<d<m such that (d*n)%m = 0

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

Please explain to me why are we checking the parity in C as the number of elements in array is always even so the parity has to be same always.

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

    Yes, Bro the parities will always be same. The answer is NO only if the number of odd/even elements in the array is odd and there are no two elements x,y such that abs(x-y) == 1

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

      actually i referred to the editorial and they checked the parities first that's why this doubt occurred to me.

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

You forgot the -1 in the initial value of the median in problem H (the implementation has it).

»
6 weeks ago, # |
  Vote: I like it +1 Vote: I do not like it

Can someone explain that d*n%m condition geometrically or algebrically. I have no idea how that works

»
6 weeks ago, # |
  Vote: I like it +2 Vote: I do not like it

Can somebody please tell how to solve F without the brute force approach ?

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

Can someone explain me why the idea of binary search on D doesn't work?

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

    Because of the division condition. Suppose n = 100 , k = 10. Suppose your middle element is 7. So you conclude you can't use this number and go below and search.Which is wrong as 10 > 7 divides 100. So it fails because the property of BS that function should be monotonic basically fails here.

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

The last problem H can be solved even in more easier way than the explained method in the editorial. First calculate the index using the formula (2^m-n-1)/2. Then check all the numbers which are to be deleted and maintain a cnt and prvCnt variable, where cnt is incremented when there exists some number in the deleted list which is less than the index, then set prvCnt = cnt. If at any stage cnt-prvCnt == 0, break the loop and there you go, you got the answer. At last just convert the decimal number to binary. https://codeforces.com/contest/1360/my

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

this tutorial for problem G, no mathematical explanation, suck.

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

My Solution for problem H. I think it's more clean. 81425658

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

An easier to think of solution for G is instead of doing the cyclic shift, simply take the first a columns with the smallest number of ones, and add ones to those in the next row. Code is here: https://codeforces.com/contest/1360/submission/81428756

It's a lot slower, but it still manages to fit within the time limit

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

Editorial of problem G doesn't make sense to me. Can anyone help me ? why cyclically shifted by d works?

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

    In the matrix you can change the order of rows and columns, it is still valid. Which means order does not matter, we just have to distribute the 1 somewhat evenly.

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

    I have similar solution to that of editorial.We have to first check if $$$a.n=b.m$$$ . If it holds we can construct the solution in following way : in first row fill '$$$a$$$' number of 1's . In second row start from a+1 column and fill '$$$a$$$' number of 1's and so on (if anytime position reaches beyond $$$m$$$ , change it to 1) . Since $$$b.m$$$ is divisible by $$$m$$$ , thus 1's are evenly distributed across all the columns. submission

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

      i am not getting why we start to fill the next row with a+1 column

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

        It's a constructive algorithm. By doing the method i have described we can equally distribute $$$1$$$'s in all columns .

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

Can somebody help, why this is failing in test 2? Submission: 81434111

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

    You are only trying the largest factor <= sqrt(n) and n/largest_factor. So, you missed some factors.

    Wrong Test Case: 1 36 4

    Your Output: 36

    Correct Output: 9 (9*4=36)

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

      Yes, I rectified it some seconds ago and resubmitted with the submission 81439111, still it failed the same case.

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

        Ah. I found the problem. On line 30: "else if( k >= p ){" where p is the smallest factor larger than or equal to sqrt(n). But, k can be larger than one of the factors which is larger than p.

        For example: 1 36 18

        Your code: p=6, k>=p is true, print 6

        Correct answer: 2 (2*18=36)

        A solution: Try all factors between 1 and sqrt(n) and their inversions. O(sqrt(n)) is good enough.

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

          Oh yes!..thank you so much!

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

What's wrong with this solution for H:

Let $$$f_i=0$$$ if $$$i \in A$$$ else $$$f_i=1$$$. Let $$$b=\left\lceil\frac{2^m-n}{2}\right\rceil$$$. Then use binary searching to find the first $$$x < 2^{m}$$$ that $$$\sum_{i=0}^{x}f(x) = b$$$. Then $$$x$$$ is the result.

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

Can somebody help me with my solution to problem E?? my solution E

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

    please make your array char and add this to if

    i != n - 1 && j != n - 1
    

    P.S Do not forget a[i][j]=='1' not a[i][j] = 1

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

      Why does the array needs to be of char type??

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

        as you can see, the input numbers are not divided. if you write cin >> a[i][j], the compiler will not take only one number, he will take number before space or enter. just try to output your array.

        int a[n][n];
        for(int i=0;i<n;++i){
           for(int j=0;j<n;++j){
              cin>>a[i][j];
              cout << a[i][j] << ' ';
           }
           cout << '\n';
        }
        
      • »
        »
        »
        »
        6 weeks ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        or you can write like

        int a[n][n];
        for(int i=0;i<n;++i){
           for(int j=0;j<n;++j){
              char q; cin >> q;
              a[i][j] = (int)(q - '0');
           }
        }
        
»
6 weeks ago, # |
  Vote: I like it +1 Vote: I do not like it

Problem C:

Note that if the parities of e and of o do not equal, then the answer does not exist.

Given that n is always even, it is impossible.

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

In Honest Coach editorial i think that this code block is not necessary.

for (int i = 0; i < n; i++) {
	for (int j = i + 1; j < n; j++) {
		result = min(result, a[j] - a[i]);
	}
}

Since we've sorted the vector. When we slice it in the i'th position, maximum of left array would be (i-1)'th element and minimum of right array would be i'th element so that doing it in one iteration is enough.

for (int i = 1; i < n; i++) {
	result = min(result, a[i] - a[i-1]);
}

Please correct me if i'm wrong

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

In Problem H, why does the approach below Doesn't work?

Approach:- We Need to find the median (let's call that median X, basically X=floor((k-1)/2) ) from the K remaining strings.

  1. Since the numbers(binary strings) from 0 to 2^m are lexicographically sorted, removing given n given strings, should not disturb the lexicographical order of the strings.

  2. Our Answer Would be Xth number, but since we have removed some numbers( n numbers/strings), From all those n numbers, we will find numbers which are smaller than X, therefore we need to increase X, by all the smaller numbers we encounter, and increase X ... until there are no smaller numbers are left.

  3. And return the updated X to be our final answer.

My Code : 81399744

»
6 weeks ago, # |
  Vote: I like it +1 Vote: I do not like it

In the solution of G, why there are always $$$b$$$ ones in every column when the solution exists?

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

    For a matrix of size $$$h * w$$$, let's represent the total number of ones in each column as a frequency array $$$F$$$ of length $$$w$$$ initially filled with zeros and for each time we place a 1 in the $$$i-th$$$ row and the $$$j-th$$$ column we increment $$$F[j]$$$, and let's periodically fill this array as the solution states, for example let $$$h = 4, w = 4, a = 2, b = 2$$$,

    Iteration 1: $$$F = {1, 1, 0, 0}$$$ filling the first two columns in the 1st row

    Iteration 2: $$$F = {1, 1, 1, 1}$$$ filling the second two columns in the 2nd row

    Iteration 3: $$$F = {2, 2, 1, 1}$$$ filling the first two columns in the 3rd row

    Iteration 4: $$$F = {2, 2, 2, 2}$$$ filling the second two columns in the 4th row

    If a solution exists for a matrix of size $$$h * w$$$, we know for a fact that $$$h * a = b * w$$$. Observe from the example above that the total number of times we iterate $$$F$$$ (the number of times we iterated all $$$w$$$ elements of $$$F$$$) is equal to the total number of ones we have to place in the matrix divided by the size of $$$F$$$ which is equal to $$$(h * a) / w = b$$$, therefore, after we're done filling the matrix we know that for all $$$ (1 <= i <= w)$$$ $$$F[i] = b$$$

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

      No offense but I wanted a proof, not an example.

      I guess that is because if we sort the column numbers where we put ones in ascending order we will have m*b consecutive numbers, then we take $$$\bmod m$$$ and what we should have is the pattern $$$0,1,...,m-1$$$, b times.

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

Why (d⋅n)%m=0 tho , If anyone can explain than it would be of great help

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

I really like this format of Div 3. A lot of problems but just the right difficulty.

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

https://codeforces.com/contest/1360/my What's wrong ? Suitable pairs? Please help!!

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

anyone plz tell me why WA on test 3 Problem D, language: C++ https://codeforces.com/contest/1360/submission/81603503 thank you!!!!

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

    U r not taking into account that the CHOSEN TYPE of package should be <=k.

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

why my answer is just giving the opposite answer in testcase 5 my solution link is https://codeforces.com/contest/1360/submission/81710379

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

CAN ANYONE TELL WHAT'S GOING WRONG WITH THIS CODE, GETTING WRONG ANSWER IN TEST CASE 2 : int t=(int)Math.sqrt(n)+1; int divisor=1; for(int i=Math.min(k,t);i>0;i--){ if(n%i==0){ divisor=i; break; } } if(n/divisor<=k) System.out.println(divisor); else System.out.println(n/divisor);

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

How to Solve F using Hashing (I know another approach)as I am practising hashing so I just wanna know how to solve using hashing ...Please help :) stefdasca

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

I have a better solution for B Editoral complexity is O(n^2), mine is O(n) https://codeforces.com/contest/1360/submission/81951340

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

    I think, you've mistaken; time complexity of you're solution is O(nlog(n)) because you're using sorting.

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

I have a better solution for C Editoral solution is O(n^2) worst, mine is O(n) https://codeforces.com/contest/1360/submission/81952460

Same thing about B

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

Can someone explain editorial's construction for G. Basically I want to know how the following ensures the condition given in question:

Let's show how to construct the desired matrix if it exists. Let's find any number $$$0<d<m$$$ such that $$$(d\cdot n)\% m=0$$$, where $$$a\%b$$$ — is the remainder of dividing $$$a$$$ by $$$b$$$. In the first row of the desired matrix, we put the ones at the positions $$$[1,a]$$$, and in the $$$i$$$-th row we put the ones, as in the $$$i−1$$$ row, but cyclically shifted by $$$d$$$ to the right.

And how does one come up with this idea.. why shifting by such a $$$d$$$ always ensure the condition in question?

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

    I have the exact same doubt. I will try asking the contest setters in pm and let you know if they respond. Meanwhile please let me know if you get the answer :)

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

      Yes I got some partial intuition in this regard. Consider that we fill in the manner described in tutorial, shifting that number $$$d$$$ to the right each time we enter next row. So in tutorial we are already filling $$$a$$$ ones in each row, so the only thing we need to worry about is that all columns are getting $$$b$$$ or equal number of ones.

      Now the thing is that if we distribute the block of ones evenly, then each row will must have $$$b$$$ ones because $$$na = mb$$$.

      So now we worry about the amount $$$d$$$ by which we shift. Following $$$0$$$ indexing, if first row has no shift, then our filling is done evenly iff the $$$n$$$th or one past the last row also starts its filling with no shift, right? So that means total shift is $$$nd$$$ and that must be multiple of $$$m$$$ (Why? because of the above line.)

      The only other condition we must worry about is that $$$d \not\equiv 0 (\mod m)$$$ because in that case you keep filling the same columns!

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

        I didn't understood your third paragraph, "that if first row has no shift, then our filling is done evenly iff the nth or one past the last row also starts its filling with no shift"

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

          Consider this:

          • ooo..
          • .ooo. < Uneven filling for n = 3 rows
          • ..ooo (4th row does not begin its filling similar to first row)

          And this

          • ooo--
          • -ooo-
          • --ooo <- Even filling for n = 5 rows
          • o--oo (Notice that 6th row will start similar to initial row)
          • oo--o
»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Hi, can someone point out flaw in my logic for Minimal Square question? Below is the code snippet.

ll ans = 0;
    if(a == b) ans = (a+a) * (a+a);

    else if(a > b){
       if(a < (2 *b)) ans = (a+1) * (a+1);
       else{
         ans = a * a;
       }
    }

    else if(b > a){
       if(b  < (2 * a)) ans = (b+1) * (b+1);
       else ans = b * b;
    }
    cout << ans << endl;
  • »
    »
    5 weeks ago, # ^ |
    Rev. 3   Vote: I like it 0 Vote: I do not like it

    for a=7 and b=5 ans must be 100 but your program will give 64. For condition (a<2b) or(b<2a) incrementing the side length won't be sufficient to accommodate piece of length 2b or 2a.

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

      Thanks @aditi2899 for providing the test case!

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

Regarding Problem E: Polygon, the time complexity given is of order O(n^2), so Is there any solution possible through which we could improve it further or Is the given solution, the most optimal one?

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

Regarding F: Spy-string: Is there any faster approach to solve the question instead of just applying the brute force ?

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

Explanation for tutorial of G. A/B matrix

Let we fill the first 'a' one's in first row then fill the second row by shifting the first row cyclically and so on. Let the shift be d. Then as there are n rows total number of shifts will be (n*d) as we have to fill the one's evenly number of shifts has to be distributed evenly among all 'm' columns (Imagine equal distibution of (n*d) sweets among 'm' children).It means that (n*d)%m should be zero. We can find d and build the matrix;

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

Getting wrong ans in test 2?

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


int divv(int n, int k){
    int j= min(k, ((int)sqrt(n)+1));
    for(int i=j;i>=1;i--){
       if(n%i==0){
        if((n/i)<=k){
            return max(i,n/i);
        }else{
            return i;
        }
       }
    }
}

int main(){
    int t;
    cin>>t;
    while(t--){
        int n,k;
        cin>>n>>k;
        if(k>=n){
            cout<<1<<endl;
        }else{
            cout<<n/divv(n,k)<<endl;
        }

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

What is wrong with this solution for Problem C?? Code

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

Problem B: for test case: 4 1 1 3 4 shouldn't the solution be 1 rather than 0?

anyone care to explain

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

In Editorial of problem H,Kindly explain the following line: "After deleting n strings, the median cannot change (numerically) by more than 2⋅n"

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

Anybody please help me to figure out why i am getting wrong answer on test case 2 in problem H? https://codeforces.com/contest/1360/submission/83613220