Supermagzzz's blog

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

All problems were developed by me Supermagzzz and Stepavly.

1367A - Short Substrings

Author: MikeMirzayanov

Editorial
Solution

1367B - Even Array

Авторы: Supermagzzz, Stepavly

Editorial
Solution

1367C - Social Distance

Авторы: Supermagzzz, Stepavly

Editorial
Solution

1367D - Task On The Board Автор: MikeMirzayanov

Editorial
Solution

1367E - Necklace Assembly

Автор: MikeMirzayanov

Editorial
Solution

1367F2 - Flying Sort (Hard Version)

Автор: MikeMirzayanov Stepavly Supermagzzz

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

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

Thanks for fast Editorial!!

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

Fastest editorial i have ever seen !!!

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

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

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

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

Practice really helps you... After continuous practice my first contest where I solved A,B,C(yaa I know Div 3) but still it's a big achievement for me... Looking Forward to Global Round

I'm new here can anyone tell about CF Global Round... I mean is that different from Div1+2 round??

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

    I think it's that both div.1 and div.2 will participate in the same contest with the same tasks.

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

    Well you solved ABC in Codeforces Round #644 (Div. 3) too

    You sir just lied

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

      That Day all the three problems had more than 11k submissions they were easy and that time I was not that serious about CP as I'm now...

      But still I don't know why the sense of relief and satisfaction I got today was the best... It really felt good...

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

        I felt like Lewis Hamilton in a Mercedes! Get in there Lewis!

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

          I felt like Maldonado, getting wrong submissions here and there.

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

      Thanks a lot! E was really confusing me

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

      Thanx bro, nice explanations!

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

Task D took soul out of me but never showed Accepted

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

    You have 0 submissions in your profile right now. Probably you did not solve any question and still saying this (weird flex) or solved them from a second account. Either way, not healthy brother. Please refrain from doing this.

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

Hello guys! I'm new to codeforces and I enjoyed this div 3 contest even tho i only solved first 3 problems. Div 1 and 2 contests demotivated me..

can someone tell me is this contest was rated or unrated ?

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

    It's rated.

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

    Yes, it was rated for all the participants with a rating less than 1600 or are a new participant.

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

      Can you tell why my ratings didn't change even though i have a lower rating?? Is it the case for anyone else too?

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

        I had a look at your submissions for the contest. Apparently, you have been marked as "out of competition" (denoted by the asterisk above the username). I hope you followed the participation guidelines.

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

How to solve F2's last testcase for 16 operations?

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

C can be solved without handling cases separately.

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

    This is clever, very clever.

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

      hi I am getting wrong answer can you tell me why? My code is :

              int t = sc.iin();
              while (t-- > 0) {
                  int n = sc.iin();
                  int k = sc.iin();
                  String s = sc.sin();
                  int ans = 0; 
                  ArrayList<Integer> a = new ArrayList<>();
                  for (int i = 0; i < n; i++) {
                      if (str.idc(s, i) == '1') {
                          a.add(i);
                      }
                  }
                  if (a.isEmpty() == true) {
                      ans += Math.floor(n/k+1); 
                  }
                  else if (a.size() == 1) {
                      int j = a.get(0);
                      int ii = j-(k+1), jj = j+(k+1);
                      while (ii >= 0) {
                          if (str.idc(s, ii) == '0')
                              ans++;
                          ii = ii - (k + 1);
                      }
                      while (jj < n) {
                          if (str.idc(s, jj) == '0') {
                              ans++;
                          }
                          jj = jj + (k + 1); 
                      }
                  }
                  else {
                      int j = 0;
                      while (j < a.size() - 1) {
                          int l = a.get(j);
                          int r = a.get(j + 1);
                          if (r - (l + k + 1) > k) {
                              ans++;
                          }
                          j++; 
                      }
                  }
                  pp.println(ans);
              }
      
  • »
    »
    5 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    shit like this make me go *wtf is wrong with my brain. Anyway thanks mate.

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

    Give me five I appended k zeros at the beginning and k zeros plus 1 at the end. 83967055

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

    I did the same

  • »
    »
    5 months ago, # ^ |
    Rev. 3   Vote: I like it -14 Vote: I do not like it

    Can anyone say the approach?

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

      Appending 100..0 at the front and 0..001 at the end ensures that the distancing conditions from the ends are already satisfied. Alternatively, say count is the number of zeros lying between two ones. In that case, subtract k from count to satisfy distancing condition from one end and then dividing the remaining count-k by k+1 i.e, (count-k)/(k+1) would give us the number of seats that can be filled. As for the leftmost case, initialise count=k as we don't have to worry about the distancing condition from the left. For the rightmost segment count/(k+1) would give the answer. Here's the code implementing it 84039536

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

        Can you give an example, I am not getting it.

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

    I also did the same

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

    Actually i did the same

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

    How about handling no cases and doing using segment tree? xD

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

    That's smart, thanks.

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

    Another approach: You can iterate through the string and keep a count of zeros from the last '1'. If count becomes greater than k, increment ans by one and assign count = 0. If present element is '1' and count < k, decrement ans by one and assign count = 0. 84095691

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

    I got TLE for that.

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

    I did C using prefix sums. here is the link, https://codeforces.com/contest/1367/submission/83981310

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

You can actually solve problem c : social distancing in O(n) time complexity and O(1) space complexity like this :

#include <cstdio>
#include <cmath>
using namespace std;
 
int main() {
	int t;
	scanf("%d", &t);
	while (t--) {
		int n, k;
		scanf("%d %d", &n, &k);
		char room[n];
		scanf("%s", room);
		int max = -1, ans = 0;
		for (int i = 0; i < n; ++i) {
			if (room[i] == '1') {
				if (i-k > max) ans += ceil((i-k-max-1.0)/(k+1.0));
				max = i+k;
			}
		}
		if (max+1 < n) ans += ceil((n-max-1.0)/(k+1.0));
		printf("%d\n", ans);
	}
	return 0;
}
  • »
    »
    5 months ago, # ^ |
      Vote: I like it -20 Vote: I do not like it

    The space complexity if $$$\mathcal{O}(n)$$$ , and not $$$\mathcal{O}(1)$$$, because you create the vector room. Here is my in-place solution:

    int main() {
    	int tests;
    	scanf("%d", &tests);
    	while (tests--) {
    		int n, k;
    		scanf("%d%d", &n, &k);
    
    		int total = 0;
    		int last = -1;
    		for (int i = 0; i < n; ++i) {
    			char c;
    			scanf(" %c", &c);
    			if (c == '1') {
    				if (last == -1)
    					total += i/(k + 1);
    				else total += (int)((i - last - 1 - k)/(k + 1));
    				last = i;
    			}
    		}
    		if (last != -1) total += (n - last - 1)/(k + 1);
    		else
    			total = ceil(((double)n)/(k + 1));
    		printf("%d\n", total);
    	}
    }
    
  • »
    »
    5 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    can u explain the logic please?

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

This contest was almost DIV 2 ..... PS — Good problems

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

    yep div3 is getting more and more difficult.

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

It felt like a Div 2 contest after C

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

    You can do problem C using a simpler approach. Initialize ans = 1, count = 0. count stores the value of the present table with respect to the previous '1'. If count becomes greater than k then, place a person on the table, i.e. increment your ans by one and assign count = 0. If you come across a '1' and count <= k then that the previous person was wrongly placed on the table, so decrement ans by one and assign count = 0

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

      thanks for this approach even better then editorial give, I was struggling with that problem from several hours.

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

    Here is the code: 84095691

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

      Bro Your code gives wrong output for test case:

      1

      9 3

      100100000
      It gives 0 output whereas correct output is 1.

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

        For this test case k = 3, whereas number of empty seats between the first and fourth seats is 2. The problem statement says it is guaranteed that the rules of the restaurant are satisfied for string s. So this test case is wrong.

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

How to do D but while preserving the order of characters from s in t.

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

    I misread the question in contest, and actually tried solving this. The only solution I could come up with, was to generate all possible subsequences of size m from s, and check if b is valid for that string.

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

      It can be optimized a bit as different values in b will correspond to different characters and vice versa so we can choose p(no of different values in b) alphabets and construct a string t accordingly and check if it is a subsequence of s. I could not optimize it any further.

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

        But, different values won't necessarily correspond to different characters, for example take the following string.

        t: aac
        b: [2, 1, 0]
        different values correspond to same character

        In fact same values may correspond to different characters. Take the following example.

        t: cab
        b: [0, 2, 2]

        Although, I think the following can be done. Try to solve this question too like the actual question, but instead of assigning the greatest character to indices containing zero, assign a number which will be used to store information whether characters t[i] < t[j] or t[j] < t[i].

        1. Assign k = m;
        2. Assign k to all unvisited indices containing zeros, in a different array let's say ans.
        3. Now for each unvisited index containing zero, iterate over all non zero indices j and subtract abs(i - j) (where i is the current index containing unvisited zero) from them, and mark the current zero index as visited.
        4. Decrement k and go to step 2.

        The above algorithm is same as the solution to the original problem, but instead of assigning characters, we are assigning numbers.

        Dry run for "cab":
        1. b: [0 2 2], visited: [F, F, F], ans: [-1, -1, -1]
        2. b: [0 1 0], visited: [T, F, F], ans: [3, -1, -1]
        3. b: [0 0 0], visited: [T, F, T], ans: [3, -1, 2]
        3. b: [0 0 0], visited: [T, T, T], ans: [3, 1, 2]

        Now, in ans array if ans[i] < ans[j], then t[i] < t[j] must be true. Therefore, we can use ans array to generate a valid subsequence from s, using backtracking.

        Although, I am not sure what will be the time complexity of the same.

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

Can someone please tell me what's wrong with my submission to C? https://codeforces.com/contest/1367/submission/83970779

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

    The loop with the search with lower_bound is not ok. You check only the distance to the next 1, not to the previous one. And, you cannot only check every kth index, you would need to check each one.

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

    Try keeping upper bound for the rightmost and setting left as you traverse. check ithere

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

For E, we may observe the following:

Suppose the length of the necklace is l. Then the necklace can be decomposed into l/gcd(l,k) consecutive portions of length gcd(l,k). These l/gcd(l,k) portions must be identical by the k-beautiful property. Now we store the frequencies of every letter, and check if sum over all letters, frequency[letter]/(l / gcd(l,k)) exceeds k. If so we have a necklace of length l, else there is no necklace of length l.

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

It felt more of a DIV 2.5 contest. btw good problems, enjoyed solving them.

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

    please do make vedios of atleast e or f , this is div3 afterall.

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

    Please don't upload the videos just after contest. Do this at least 12 hours after contest is over. Some people will tend to watch your video immediately afer contest instead of upsolving. Thanks.

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

      Why do you think you have to tell people what to do?

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

        And why do you think i forced him to do anything? I just said my point in a manner of request. He is free to do anything what do he wants.

        And people downvoting my comment are same which regularly post shitty things like-- I have been practising for 3 years and i am not improving-- instead of upsolving.

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

          I think you also have an option of not watching the videos before 12 hours?

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

            He is worried about those who don't improve even after practicing for 3 years. Haha

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

          ur profile shows registered 4 months ago

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

I did the C in this way .. first marks all ones and make all invalid seats upto k as ones on the both sides. later simply occupy first seat which is zero and later occupy every zero which comes atleast after k seats from the previous zero. 84029131

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

I had a different approach for both E and F

1367E - Necklace Assembly , 84000671:

I created a count, c, of occurrences each letter, and then I iterated over each factor, f of k. Then I checked for the highest multiple of f that was a valid length using patterns of length f. For each multiple m * f, I took the sum of floor( c / m) for each count, and if the sum was >= f, it was valid.

1367F2 - Flying Sort (Hard Version) , 84030983

The main idea I used was that we would minimize the number of operations by finding the longest subarray of the sorted array that was also a subsequence of a . I kept a sorted map of numbers to a sorted list of indices the number appears at. Then I iterated through the map and kept track of the longest subarray found.

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

    E -> how about taking top f elements in count, c, array and then take the least element l among them. then, ans=max(ans, f*l)

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

      Your approach doesn't allow the same letter to be used more than once in the repeating pattern

      say you had this test case:

      1
      13 3
      aaaaaaaabbbbc
      

      Your counts would be 8, 4, and 1. The factors of 3 are just 1 and 3.

      For 1, applying your approach would give us 8

      For 3, applying your approach, the minimum is 1, giving us 3

      The correct answer, however, would be pattern of aab repeated 4 times, which is a length of 12.

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

    Check this solution. You could use gcd

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

    Any proof why it is true " the longest subarray of the sorted array that was also a subsequence of a" ?

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

      The elements that are not moved have to form a sorted subsequence. So if we can maximize the length the sorted subsequence, the number of operation is minimized.

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

    Thanks for helping me find my mistake in E.Was doing everything correctly except for adding the floor of C/2 instead of the floor of C/M. It just slipped my mind and I was rotating all necklaces by half of their length and hence trying to find a palindrome, I needed to find if there can be M similar blocks instead of 2 similar blocks. Thanks once again.

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

    can you please elaborate on keeping the track of the longest subarray . I don't think we can do that just iterating linearly .

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

      That's true, I did gloss over that a bit. When I iterate from one unique number to the next largest, there are 2 possible cases

      case 1: The last index in the previous number is less than the first index of the current number. Then we can just extend the subsequence and continue to the next number

      case 2: case 1 is not true. In this case, we need to start a new sequence, but there's 3 things we need to look at.

      a. We take the earliest index of the current number that is greater than the last index of the current number and add those number to the end of the current sequence.

      b. We then also look for the longest sequence of just the previous and current numbers. For each index of the previous number, we find the earliest index of the current number that is after it, and we have a subsequence with just those indices.

      c. We find the latest index of the previous number that is smaller than the first index of the current number and start our new subsequence with them.

      submission link: 84023424

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

        Thank you so much! Even though I didn't fully understand your explanation, it gives me some hints. Here's my c++ implementation 84279237 for those who are not familiar with kotlin (like me). The implementation is different but I believe the idea is the same.

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

Why greedy approach for distributing letters to cycles works in problem E? Because I think that in general it shouldn't work. Let's say we have buckets of size 6 and 10 and want to fill them with values 5, 5, 6. Then the best choice is to put two 5s in bucket of size 10 and 6 in bucket of size 6. Greedy approach doesn't work in this case. Does problem E satisfy some constrains that allow for greedy approach to work?

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

    Because of the way to form the graph, all the cycles will have the same size, a graph of size n with edges between i and (i+m)%n, will have gcd(n,m) cycles of size n/gcd(n,m).

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

      Thanks! I get it now

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

      Thanks

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

      How cycle size is exactly gcd(n,m)? Is there any proof of it?

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

        Someone explain this. Same doubt.

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

        Imagine that you have a number i, and you replace it with (i+m)%n in one operation, now, we will calculate the first time that this number will be equal to i again, we can show that we want to find the smallest k such that ( i + k * m ) = i ( mod n ), we can substract the i's and left k * m = 0 ( mod n ), so k = n / gcd( n , m ). and, if we start with each number after n / gcd( n , m ) we will find a cycle, that's why all cycles will be equal, and if each one has size n / gcd( n , m ), there will be gcd( n , m ) cycles.

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

        In a necklace of length m, if you rotate by k, you notice that you require each subcycle (starting with any bead, and jumping k hops at a time) in the necklace to have same beads.

        Now each sub-cycle will be produced by starting at i, and then after jumping k steps for x no. of times we will reach back at i. This completes our sub-cycle i.e. ($$$i + kx \equiv i mod m$$$) where x as you can see is the no. of jumps taken to reach back at i, also is the length of this sub-cycle.

        Or, ($$$i + kx - my = i \implies kx = my$$$) for some integer y.

        Now to find the min. x such that above equation holds, you see k and m are fixed, so kx = my = lcm(k, m). And as we know lcm(k, m) = km/gcd(k, m) = km/g.

        Therefore, ($$$x = lcm(k, m)/k \implies x = km/kg \implies x = m/g$$$). Hence proved length, x of sub-cycle produced is size/gcd(size, k).

        Now to prove that no. of subcycle will be gcd(k, m):

        you can see that each sub-cycle will of equal size, starting with some i, j, ... , also each element has to be a part of exactly 1 such subcycle, thus product of no. of subcycles and size of each such subcycle must be 'm', hence the proof follows.

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

      But what's it's proof?

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

Can someone help me with my code for Prob.C: Submission

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

    see this test case :

    7 1

    1000001

    Your solution gives the output as 1, but it should be 2 because we can place '1' at 3rd and 5th position.

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

https://codeforces.com/contest/1367/submission/84030518 pls can anyone tell y it is giving error in test case 54 of pretest 2 thnks in advance

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

In problem C for block that is neither first nor last,why cant we do (number of zeros in block)/ (2*k+1)

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

I also explain solutions to these problems at the end of my screencast of the round if you would like a more visual explanation that what the excellent editorial here provides.

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

    thank you

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

    Can you give an elaborate explanation for the solution of question D? I did not understand it!:/

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

      What part was confusing?

      The idea is as follows:

      1. All of the zeros in the initial array correspond to the largest letter that is in the answer string.
      2. Therefore, we can insert that largest letter into all spots that contain a zero.
      3. Once we have inserted these largest letters, we can subtract out their contribution from all other spaces. This will allow us to easily locate all instances of the second largest letter, because those positions will be zeros.
      • »
        »
        »
        »
        5 months ago, # ^ |
          Vote: I like it -13 Vote: I do not like it

        oh i am so sorry! i meant question E! The one with the necklace beads! Can you please explain that in a elaborate manner?

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

        thanks...great explanation...

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

        Great Explanation ... please explain F1 too ---

        In the below code what we wanna do or what is the easiest idea to solve

            lli n;
            cin>>n;
            pair<lli,lli>a[n];
            loop(i,n){
                lli x;
                cin>>x;
                a[i] = make_pair(x,i);
            }
            sort(a,a+n);
            lli ans = 0;
            lli cnt = 0;
            FOR(i,0,n)
            {
                if(i==0 or a[i].S>a[i-1].S)
                    cnt++;
                else
                    cnt=1;
                ans = max(ans,cnt);
            }
            print(n-ans);
        
»
5 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Hello All, I have a question related to Social Distancing. Input: 6 2 000000 This input comes under the separate case mentioned in the editorial which is "a string consisting only of zeros". So we don't need to remove any zeros from the beginning or end. So answer should be floor(6/2) which is 3. But the correct answer as per the sample test case is 2. Can someone explain where I understood incorrectly? Thanks

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

I believe I have a really nice solution (as well as clean) for the problem E -> 84022899

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

    Looks like 84012097

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

      lol i was looking for ways to solve E and found my own code

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

    I don't understand the concept of GCD here...Please explain :)

    I did this -

    while(t--) {
        lli n,k;
        cin>>n>>k;
        string s;
        cin>>s;
        int a[26]={0};
        lli ans = -1;
        loop(i,sz(s))
            {
                a[s[i]-'a']++;
            }
        for(lli j=n;j>=1;j--){
            lli val = j;
            lli cnt=0;
            loop(i,26){
                cnt+=(a[i]/val);
            }
            while(cnt>0 and k%cnt!=0)
                cnt--;
            ans = max(ans, cnt*val);
        }
        cout<<ans<<endl;
      }
    
    

    AC solution : 84033889

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

      If you observe carefully, you will see there will be some cycles forming of same size. So we will check each size possible of the necklace. let's say we want to check if necklace size of x is possible or not. Let's say g = gcd(x, k). After g beards in the necklace, the letter has to be the same. So there will be g cycles. x sized necklace will consist g cycles of (x/g) size. Now we need to check if we can get g cycles of (x/g) size. This gcd idea can be a bit hazy, if you are finding it hard to understand, I will highly recommend you to draw some pictures and the thing... It really helps get a concept clearly :D And then let me know if you have further doubts. Happy Coding :D

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

I could not understand the tutorial of Problem F. Can somebody please elaborate a little more. Thanks in advance. I just want to understand the logic here. The implementation part is clear to me.

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

    Let's say we have an array [3,10,10,1,3,7,7,0] . We can map it to [3,5,5,2,3,4,4,1] so the coding part become easier. Now let's sort it [1,2,3,3,4,4,5,5]. Now we need to find the longest sub-sequence in the original array, which is also a sub-array for the the sorted array (If you subtract it's length from n, you will get the answer) . You can see here a interesting fact that [3,5] or [2,3,4,4] can't be a answer because it is a sub-sequence for the original array but not a sub array for the original one. So it's clear that there there has to be body , prefix, suffix . Body has to contain all the all element fully (It means if there are 5 4's , it has to contain all the 5 4's.) and prefix would be the maximum you can take legally before body's first element (simply the amount of (body's first element)-1 equals element before the body starts) and suffix would be the maximum you can take after body's last element(simply the amount of (body's last element)+1 equals element after the body ends). This is the basic idea. But there is a case, you also need to focus on. You need to check all the possible sub-sequences containing only two different elements. I got AC doing this 84144777. Please let me know, if you have any further doubts. Happy Coding :D

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

      nice problems

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

        I never said we need to take the LIS. We need to take fulled connected increasing sub-sequence! In your case we if we sort the array, it would be [ 0 1 2 3 ] and the original array is [ 0 2 1 3 ]. We have take a the maximum sized subarray from the sorted array which also have to be a sub-sequence of the main array. We can't take [0 2 3] as it isn't a sub-array of the sorted array. We can take [0 1] or [2,3] ! Hope this helps you to clear the fact!

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

      Saw your code. Feels like you used priority_queue to store the no. of a[i]s present in the array by storing 1+p[a[i]].top() into p[a[i]]. Isn't it?

      But, still didn't get how are we finding the length of the increasing subsequence in the original array(after coordinate-comp.) which is also the subarray in the sorted array? How are we doing this using priority_queues? I noticed you are taking the maximum of the b[i]s which is, of course, the size of each priority_queue. So ain't we only considering all the elements of the same type(all elements being equal to "x") as the only candidate for increasing subsequence(which is subarray when array gets sorted). Please help !!

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

        If you look carefully in my code. I have not used priority queue! I just declared it as I was trying different methods. I tried 2-3 times with priority_queue before this and seems like implementing with it kinda impossible for me! To find the right sub-sequence, I am taking a number fully, (like if there is 3 1's, I will take all the three), then let's say before the first 1, there was 2 zeroes. So I will take them too. Now If all the 2's exists after the last 1, I will continue to the two and will take a prefix = ( 3 (one) + 2 (zero's before one) ). If not then I will take the number of 2 after the last 1 as suffix! And will move to two as 0 prefix. If get clear on this part, it would become really easy for you to do the rest!

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

I did F2 without dynamic programming.

Basic idea: The subsequence which should not be touched while making operations would have the set of numbers as $$$b_1, b_2 \ldots b_k$$$, where $$$b_1 < b_2 \ldots b_{k-1} < b_k$$$. And it must have complete segments for every number $$$b_2, b_3 \ldots b_{k-1}$$$, whereas it could have incomplete intervals for $$$b_1$$$ and $$$b_k$$$.

84032732

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

    The part of idea is clear for me. Can you please explain a bit about the implementation? I am finding it hard to understand.

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

      First case where I used deque(just for simple understanding, it's not even necessary) is the case when $$$k$$$ in the above sequence is greater than $$$2$$$. We can use sliding window for calculating it.

      Next case, where I used a queue is when $$$k=2$$$, so both $$$b_1$$$ and $$$b_2$$$ are incomplete intervals.

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

        I actually got a idea by myself and it took 5 WA to get the AC. Thanks a lot for the help and sorry I thought first to try my idea then yours.As It took me 28 hours to get AC, so I was late in reply.

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

    could you please elaborate more ?...thanks

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

What is the time complexity for this code ? (Question E ) , if |S| = 10 6

while(t--) {
    lli n,k;
    cin>>n>>k;
    string s;
    cin>>s;
    int a[26]={0};
    lli ans = -1;
    loop(i,sz(s))
        {
            a[s[i]-'a']++;
        }
    for(lli j=n;j>=1;j--){
        lli val = j;
        lli cnt=0;
        loop(i,26){
            cnt+=(a[i]/val);
        }
        while(cnt>0 and k%cnt!=0)
            cnt--;
        ans = max(ans, cnt*val);
    }
    cout<<ans<<endl;
  }
  • »
    »
    5 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    $$$ O(n\log n) $$$, because $$$cnt_j$$$ is bounded by $$$n/j$$$, so the whole thing grows at a rate of $$$H_n = O(n\log n)$$$. The added condition k%cnt!=0 will speed it up in some cases, but in the situation $$$k=1$$$ for example, it won't make a difference. It's hard to quantify how much it will affect the runtime in other cases, since it basically depends on the number of divisors of $$$k$$$ which are in the range $$$[1, n]$$$, as well as how "spread out" they are in that interval.

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

I guess C can be solved in an easier approach and straight forward way.

#include <bits/stdc++.h>

using namespace std;

#define ll long long
#define ull unsigned long long

void run(void)
{
	int n, k;
	cin >> n >> k;

	string x;

	cin >> x ;

	int c = k, i = 0, ans = 0;

	while(i<n){

		if(x[i] == '0'){
			c++;
		}
		else {
			if (c<k)ans--;
			c  = 0;
		}
		if(c>k){
			c = 0;
			ans++;
		}

		i++;
	}


	if(ans < 0) cout << 0 << endl;
	else cout << ans << endl;


}

int main(void)
{
	int t;

	cin >> t;

	while(t--) run();
	
	return 0;
}

Time complexity: O(N) Space complexity : O(1)

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

    What's with this new trend of $$$\textbf{O(1)}$$$ space complexity ? And in your code you have read the whole string using,

    string x;
    cin >> x ;
    

    That is clearly $$$\textbf{O(n)}$$$ space.

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

      I think they may be referring to auxiliary space usage

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

      He probably meant to say O(1) extra space.

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

      The space needed for storing the string is same for all the solutions. But my code doesn't need space which grows at the time to execution. Hope you understand brother.

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

Supermagzzz In Question C instead of floor((number of zeros)/k) it should be ceil((number of zeros)/(k+1))

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

For those scratching their heads about F2 test case 3 #4999, try the following input (the correct answer is 2):

1
6
1 0 0 1 1 0
»
5 months ago, # |
  Vote: I like it +20 Vote: I do not like it

Checker for problem D was wrong during the contest. My submission was hacked and it now fails on test 1 (it didn't during the contest)

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

I think the testing was not appropriate for the 4th ques during the round ,during the round it showed to pass on first test case but after the round it was hacked on same test case (I did not pay attention to change the code as it was shown accepted and lost the score after the hack)

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

PROBLEM C without formulas and handling cases seperately---->

Simply use greedy approach and put one's from left to right if it satisfies the condition (i.e currentindex-previousindexhavingone > K)and increase the answer by 1 whenever in future your condition gets violated (might be due to subsequent one) you decrease the answer by 1.Here is the code -------->

#include <bits/stdc++.h>
using namespace std;
 
int main()
{
    int t;
    cin >> t;
    while(t--)
    {
       int n,k;
       cin >> n >> k;
       string s;
       cin >> s;
 
       int curr = 0, ans = 0;
 
       if(s[0] == '0') ans++;
       curr = 0;       //curr means current index
 
       for(int j=curr+1; j<n; j++)
       {
           if(s[j] == '1') { if(j-curr <=k) ans--; curr=j; continue; }
           if(j-curr > k)
           {
               s[j]=1;
               ans++;
               curr=j;
           }
       }
 
       cout << ans << endl;
 
    }
 
    return 0;
}
»
5 months ago, # |
  Vote: I like it 0 Vote: I do not like it

There also exists an O(n) solution for C: 83977850

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

My noob solution for C. Iterated the array thrice.

			int n,k;
			cin >> n >> k;
			string s;
			cin >> s;
			int count=0;
			int free=0;
			for(int i=0;i<n;i++){
				if(s[i]=='1'){
					count=k;
				}
				if(s[i]=='0' && count){
					s[i]='1';
					count--;
				}
			}
			for(int i=n-1;i>=0;i--){
				if(s[i]=='1'){
					count=k;
				}
				if(s[i]=='0' && count){
					s[i]='1';
					count--;
				}
			}
			for(int i=0;i<n;i++){
				if(s[i]=='0'){
					s[i]='1';
					i+=k;
					free++;
				}
			}
			cout << free << endl;
	}
»
5 months ago, # |
  Vote: I like it 0 Vote: I do not like it

solved E without graphs.. just gcd and some basic operations: solution

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

In Editorial of Problem "1367C — Social Distance", it is mentioned that,

"all the tables in each block are free, then in each block we can put (number of zeros)/k. Sum these values over all blocks."

I find this as wrong. ( Referred some of the comments below, and collated this )

It is actually, for each block,

answer = answer + ((number of zeros) / (k+1)).

Also, if the remainder is greater than 0, then, add +1 to the answer. i.e., if(((number of zeros) % (k+1)) > 0)

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

My approach for problem — C

We need to find number of unoccupied table which can be occupied so lets marks those table, or change s[i] = 0 to s[i] = x. Than count number of x in our final string x. Working iterate from 0 to strings length (n).

1)if s[i] is 0 than check the index of prev 1 or prev x in the string

2)if i — prev1 is > k marks this 0 as x and store this position (prev x).

3) if s[i] is 1 check for prev x.(which is already stored)

4) if i — prevx <= k change s[prevx] to 0

5) marks prev1 = i.

Submission Link — https://codeforces.com/contest/1367/submission/83973628

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

in the editorial of social distance i cannot understand the statement res += (len + k) / (k + 1); what this statement doing?

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

    It is basically $$$\textrm{ceil}$$$$$$(\frac{len}{k+1})$$$, $$$\textrm{ceil}$$$$$$()$$$ being the ceiling function. As C++ $$$\textrm{ceil}()$$$ function can be inaccurate, an alternative to avoid that is $$$\textrm{ceil}(\frac{a}{b}) = \frac{a+b-1}{b}$$$.

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

      Can u pls tell what is wrong in my code- its giving WA on 201 test case https://codeforces.com/contest/1367/submission/84069351

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

        I couldn't understand the logic, but here's a test case where your code fails:

        1
        7 2
        1000001
        

        Expected answer: 1, Your output: 0.

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

          yeah i got where i was wrong thanks anyways:)

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

      thank you your reply but can you tell me what is the role of this statement in this program.

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

      moreover how your coming up with this formula ceil(len/k+1)?

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

        After you obtain a block containing purely zeroes, and there is no restriction on the first table's selection, how do you fill tables optimally? Definitely you can start from the leftmost table, and fill subsequent tables accordingly. For a block of length $$$len$$$ $$$[0,len-1]$$$, you can fill tables $$$0, k+1, 2*(k+1),...$$$ until $$$s*(k+1) < len$$$.

        In short, we have to find number of multiples of $$$(k+1)$$$ present in $$$[0, len-1]$$$ (including 0), which is $$$\lceil\frac{len}{k+1}\rceil$$$.

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

this time editorials solutions are very bad there are other very elegant solutions with less time complexity

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

    yeah I am still not able to understand the approach of problem C and at same time finding my approach slighly easy to understand.

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

Here’s another solution for E. Upper bound on complexity is $$$O(\sigma(k) \log n),$$$ where $$$\sigma(k)$$$ is the number of divisors of $$$k,$$$ and $$$\sigma(k) = O(\sqrt{k}).$$$

A string $$$v$$$ is $$$k$$$-beautiful $$$\iff$$$ there exists a string $$$\pi$$$ such that $$$v = \pi^m$$$ and $$$|\pi|$$$ divides $$$k$$$.

Imagine we had a magic function, $$$F(p),$$$ that told us the maximum $$$m$$$ such that we can afford $$$v = \pi^m,$$$ for some $$$\pi$$$ with fixed $$$|\pi| = p$$$.

Then we could just iterate over the divisors of $$$k$$$ in order to find divisor $$$p$$$ such that the product $$$p \cdot F(p)$$$ is maximal; that product would be our answer.

Now let’s implement $$$F(p).$$$

We have an upper bound on the number of repetitions of $$$\pi$$$, it is $$$\lfloor n / p \rfloor$$$.

Also, if we can afford some string $$$v,$$$ then we can afford any prefix of $$$v$$$.

So we can do binary search on $$$m$$$ from $$$0$$$ to $$$\lfloor n / p \rfloor$$$ inclusively.

Given $$$p$$$ and $$$m,$$$ how do we check that we can afford $$$v = \pi^m,$$$ for some $$$\pi$$$ with fixed $$$|\pi| = p$$$?

Turns out this is pretty easy: the answer is $$$p \le \sum_{i=1}^{26} \lfloor t_i / m \rfloor,$$$ where $$$t_i$$$ is the number of letters with code $$$i$$$ in the original string $$$s$$$ (e.g., $$$t_1$$$ is the number of letters ‘a’).

It is assumed that $$$\lfloor t_i / 0 \rfloor = \infty, \, \infty + \infty = \infty,$$$ and $$$p \le \infty.$$$ In practice, you should treat $$$m=0$$$ as a special case. Here’s another explanation for it: we can always afford an empty string, even though the final answer (but not $$$F(p)$$$) is always $$$\ge 1.$$$

Code: https://codeforces.com/contest/1367/submission/84037953

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

what happened to problem D?

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

is problem D gone?

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

Why was problem D removed?

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

Is problem f actually the famous LIS problem?

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

    Not exactly. It is not just increasing.

    Ths subsequence should be a continuous subarray of the sorted array.

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

      i am unable to do implementation if F2 can you help me ...

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

      Then it can be done with a simple two pointer I guess(or am I wrong?) Then why is dp used?

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

        Can you elaborate more on how you use two pointers?

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

          first we iterate over the hole array. let R be 0 at first.(the array is 0_indexed) then let us be on step L of iteration. now as long as you can increase R such that sub array [L, R] is increasing. modify ans by size R — L + 1. (ans = max(ans, R — L + 1)) then at last ans is the answer. tell me if I'm wrong.

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

            Sorry for being unclear.

            • Let the original array be $$$a_1, ...,. a_n$$$
            • Let $$$b_1, ..., b_n$$$ be the sorted array of $$$a$$$.

            What I mean is that you should find the longest subsequence(not continuous) of $$$a$$$ such that it is a continuous subarray of $$$b$$$.

            I am talking about F1 for simplicity . the case for F2 is little more complicated.

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

Why the F is problem D removed. It is so unfair. Finally after so long I had a good contest and now I'm so annoyed. The problem didn't seem wrong and if it was there should be some points given to the persons who attempted D first and wasted their time.

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

@MikeMirzayanov Why is the 4th problem removed? We didn't waste time on it for anything. You should get it back. It didn't seem wrong either

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

i dont think they remove the problem D deliberately, it's just somethings wrong with the testing system, right?

pls dont remove D, i spent an hour just to solve it

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

    I also spent hours to solve d pls don't remove it

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

Here is an intuitive and easily implementable solution for E : Consider a nested loop, the inner loop ('j') representing the length of the smallest segment which is repeated over the cycle and outer loop ('i') represents the number of times this segment will occur in the cycle. Both the loops will run from 1 to n. Now we just have to check which pair (i,j) is valid. This can be done easily using an array storing the frequency of each letter in the string and calculating the maximum length of the segment that can be achieved for given 'i'. Refer to the code snippet given below :

for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=n;j++)
        {
            if(i*j>n) break;
            int shift=k%(i*j);
            if(shift%j!=0) continue;
            int sum=0;
            for(int c=0;c<26;c++)  sum+=(cnt[c]/i);
            if(sum>=j) ans=max(ans,i*j);
        }
    }
  • »
    »
    5 months ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    please explain line int shift=k%(i*j); if(shift%j!=0) continue in more detail. Thanks in advance

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

      i*j is the total number of beads in the necklace. So shift represents the number of times I need to rotate before achieving the same configuration. I need to ensure that shift is divisible by j because j is the period after which same segment repeat. sum represents the length mentioned in the last line of my previous comment. I hope it's clear now. Ask again if it's still not clear, I will try to elaborate more. Do leave an upvote

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

Wouldnt it be easier to do F with 2d dp? then its actually pretty simple once you notice the trick to rewrite the array.

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

People like me who spent a lot of time to solve D are affected. So I think contest should be unrated.

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

    there is an issue in problem D checker and they are fixing it, hopefully it will return soon Your text to link here...

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

    Think of those who spend more than 1 hour and finally solved it , wouldn't be unfair for them if it becomes unrated .

    P.S.:- I couldn't solve D.

    Happy Coding!!!

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

There is a solution for C which is pretty easy. Let's compute prefix sum array for our string. Now let's iterate over string with a window from i-k to i+k and check if there is any '1' already sitting there or not (prefix[min(n,i+k)]-prefix[max(1,i-k-1)]. If it does not then place '1' over there ( increase answer by 1) and go i+k+1 else just do i++.

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

can somebody help me in implementation of F2

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

Can someone please help me spot the bug in the code as my code is failing on test case 2? I'm a beginner. Thanks in advance

https://codeforces.com/contest/1367/submission/84063733

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

Can anyone help me out...I am getting WA on 175th no. of 2nd test case of Social Distance(1367C) problem of this contest.

#include<bits/stdc++.h>
using namespace std;
#define ll long long int
#define tc ll t;cin>>t;while(t--)
#define lp(i,j,k) for(ll i=j;i<k;i++)
#define lpr(i,j,k) for(ll i=j;i>=k;i--)
#define pb(x) push_back(x)
#define F first
#define S second
#define mod 1000000007
#define fast ios_base::sync_with_stdio(false);cin.tie(NULL);
#define vec(pk,pk1) vector<ll> pk(pk1,0)
#define vect vector<ll> v

int main()
{
	fast
	tc
	{
		ll n,k;cin>>n>>k;
		string s;cin>>s;
		ll prev=-1;ll c=0;
		
		if(s.length()==1&&s[0]=='1'){
			cout<<"0"<<endl;continue;	
		}
		ll bc=0;
		lp(i,0,n)
			if(s[i]=='1')bc+=1;
		
		if(bc==0){
			if(n<=(k+1))cout<<"1"<<endl;
			else{
				c=(n/(k+1));
				if(n%(k+1))c+=1;
				cout<<c<<endl;
			}
			continue;
		}
		lp(i,0,n)
		{
			if(s[i]=='1'&&prev>-1){
				ll x=(i-prev-1);
				if(x>=(2*k+1))c+=1;
				prev=i;
			}
			else if(s[i]=='1'){
				c+=(i/(k+1));
				prev=i;
			}
		}
		//cout<<c<<"----"<<endl;
		ll zero=s.length()-1-prev;
		c+=(zero/(k+1));
			cout<<c<<endl;
	}
	
	
	
	
}



`

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

can someone help with a bit more clear explaination of probelm F2?? I'm not happy with the above explaination

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

Can anyone please check my solution? https://ide.codingblocks.com/s/259679

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

What is upsolve?

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

Why not for F1 editorial? Anyone please explain the logic of problem F1?

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

    F1 is only an easy version of F2. In F1 the constrain are small and some additional conditions are given.

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

debug my code please for problem c

#include <bits/stdc++.h>

using namespace std;

int main() {
    int t;
    cin>>t;
    while(t--){
        int n,k;
        cin>>n>>k;
        string str;
        cin>>str;
        if(k>=str.length()){
            bool r=false;
            for(int i=0;i<str.length();i++){
                if(str[i]=='1'){
                    cout<<0<<endl;
                    r=true;
                }
            }
            if(!r){
                cout<<1<<endl;
            }
        }else{
            int newst,res=0;
            bool newstr=false;
            for(int i=0;i<str.length();i++){
                bool br=false;
                for(int j=i;j<i+k+1  && j<str.length() ;j++){
                    if(  str[j]=='1'){
                        newstr=true;
                        newst=j+1;
                        br=true;
                        break;
                    }
                }
                if(br){
                    break;
                }else{
                    res++;
                    str[i]='1';
                    i=i+k;
                }
            }
            if(newstr){
                for(int i=newst;i<str.length();i++){
                    bool br=false;
                    for(int j=i;j<i+(2*k)+1;j++){
                        if((j>=str.length()  && j<i+k+1  )|| str[j]=='1'){
                            i=j+1;
                            br=true;
                            break;
                        }else if(j>=str.length()){
                            break;
                        }
                    }
                    if(br){
                        break;
                    }else{
                        res++;
                        str[i+k]='1';
                        i=i+k;
                    }
                }
            }
            //cout<<str<<endl;
            cout<<res<<endl;
        }
            
       
    }
}
»
5 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Can someone tell me why did my rating not increase after giving the contest??

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

is there anyone explain me problem E editorials briefly? i can't understand the the given editorial.. thanks a lot

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

For $$$E$$$, one could also do the following . Notice that, we must construct strings which are cyclic and repeat after "$$$k$$$ $$$rotations$$$" . Let's think that we need to construct some $$$x >= 1$$$ number of blocks of the form {$$$a_1 , a_2, .. , a_t$$$} , {$$$a_1 , a_2, .. , a_t$$$} , {$$$a_1 , a_2, .. , a_t$$$}, .... $$$x$$$ $$$times$$$. The length of the answer in this case is $$$t * x$$$. We immediately observe that $$$t$$$ must be a factor of $$$k$$$. So, let's loop over all factors of $$$k$$$. For each factor ($$$t$$$) we need to determine the maximum $$$x$$$ that works. Notice, that if $$$x$$$ works, then $$$x - 1$$$ also works. So, we can binary search here . The complexity is $$$O(\sqrt{n} * 26 * log(n))$$$ . Implementation of the above approach : https://pastebin.com/pjajDF0a

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

Please help! In C, why does (#of0 — k) / (k + 1) work?

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

I saw someone solved F2 using std::set, here's the link 84018692. Can someone help explain it? Or can anyone tell how to solve F2 with shorter length of code?

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

    Wow, this solution is very clean, no DP needed at all. The basic idea is as follows: we can pre-sort all of our values and use two pointers to find the largest segment that appears as a subsequence in the original array. Now, say your sorted elements are [0, 0, 1, 1, 2, 2]. If we wanted to find out whether, say, [0, 1, 1, 2] appears as a subsequence in our original array, we need the following observation: we need all of the middle elements (i.e. 1's) and only some 0's and some 2's. Which 0's and 2's should we take? Well, it would make sense that we should take the earliest 0's that appear and the latest 2's that appear. This is the core idea behind that solution.

    Now, to explain the actual code: v stores {element, -index} pairs and sorts it so that when we start iterating over a new element, we will be looking at the latest occurrence. The set s1 stores the indices of all of the elements of the current value, and the set s stores the indices of all the other elements that are currently in our subsequence (note that the segment from [i, f] is the current subsegment). To decide whether we can add a new element, we essentially need to make sure that the only elements in s are the ones that appear after our current one, so we increment our back pointer and delete from the set until this is the case.

    At the end of each iteration, s and s1 contain the indices of the longest subsegment of the sorted array ending at index f that can be found as a subsequence in the original array, so we update our answer with the current subsegment size.

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

      It's a really strange idea. With the help of your extremely clear explanation, I now understand how it works. Atfer sorting, the author's aim is to find a longest subsegment which satisfies some kind of restriction as the following picture shows.

      Then when adding a new element, we need to delete those elements illegal in s as the following picture shows.

      And actually, s1 is not needed. It can be replaced just by a stack.

      Thx a lot for your clear explanation!

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

      Thank you so much iamhpp and Kognition for this solution! This is a very elegant and concise way to solve such a difficult problem.

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

what's wrong with this code? it's not working for 4th test case. can anyone help me please? the 4th question.

include <bits/stdc++.h>

using namespace std; void fastio(){
ios_base::sync_with_stdio(false); cin.tie(NULL); }

define ll long long

int main(){ #ifndef ONLINE_JUDGE

freopen("input.txt", "r", stdin); 
freopen("output.txt", "w", stdout);

#endif
int t; cin>>t;
while(t--){
    string s; cin>>s;
    sort(s.begin(),s.end());
    string d=s;
    auto n=unique(s.begin(),s.end());
    s.resize(distance(s.begin() ,n));
    //cout<<s;
    map<char,int> mpp;
    mpp.clear();
    for(int i=0;i<d.size();i++){
        mpp[d[i]]++;
    }        
    int m; cin>>m;
    vector<char> ans(m,'0');
    vector<int> v(m,0);
    for(int i=0;i<m;i++){ cin>>v[i];}
        int b=s.size()-1;
        int i=m;
        while(i>0){
        int c=0;
        for(int j=0;j<m;j++){
            if(v[j]==0){
                c++;
            }  
        }
        //cout<<c;
        while(mpp[s[b]]<c){
                b--;
        }
        //cout<<s[b];
        int x=0;
        for(int j=0;j<m;j++){
            if(v[j]==0){
                ans[j]=s[b];
                x+=j;
                v[j]=-1;
            }
        }
         b--;
        for(int j=0;j<m;j++){
            v[j]-=abs(j-x);
        }
        // for(int j=0;j<m;j++ ) cout<<v[j]<<" ";
         i-=c;
    }

for(int i=0;i<m;i++){ cout<<ans[i]; } cout<<endl;

}

return 0; }

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

if anyone can please point out error in this code 84093874 thanks

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

Here's a similar question to Problem F (Flying Sort): Click.

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

    I remembered I did this before and I was looking for this problem during the contest but couldn't find it. Thanks for bring this out!

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

I'm not understand dynamic programming approach in F2. Can someone give me example and simulate step by step ? What's dp[1], dp[2] , .....so on in this example ? What's the relation between dp[i] and dp[i-1] ? Thanks.

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

I am not able to understand the following lines that were written in the editorial of the f2 question ( refer last line of the editorial contest 650 of problem f2). can anyone explain me? It is necessary to separately consider the first numbers in the subsequence and the last, since the first should include their suffix, and the last should have their prefix.

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

In the last sample problem, of F2 After modifying the array,

20

16 15 1 10 0 14 0 10 3 9 2 5 4 5 17 9 10 20 0 9

It becomes,

20

10 9 1 7 0 8 0 7 3 6 2 5 4 5 11 6 7 12 0 6

and the highlighted ones are sorted largest sorted subsequence in length 5 so the answer should be 15, or am i missing something.

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

    In this subsequence how will you enter the no 5, which is not highlighted, into the subsequence you have formed by following the algo mentioned in the question??? I think that's what you missing (I too had the same problem)

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

Can anyone point out to why this code is not working https://codeforces.com/contest/1367/submission/84133718 problem C: Social Distance

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

You can also use suffix and prefix strategy to solve problem C. https://codeforces.com/contest/1367/submission/84069306

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

why am i not rated for this contest ?

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

Can anyone please explain how the answer is 10 in the fifth sample case of E

20 5 ecbedececacbcbccbdec
answer->10

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

    Have this combination of beads.. this satisfy the condition mentioned ccbccccbcc

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

For D in the editorial code, how are we ensuring that we aren't picking a letter which appears lesser times in S than needed?

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

Can Someone Explain this following line in the editorial of Problem C.

"then in each block we can put [number of zeros/k]".

Suppose Example is n=6 k=1 So maximum tables will be 3 but according to this formula answer will be 6 i.e (6/1)

Any Catch which i am missing?

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

    No, the editorial is wrong.

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

      Thanks spookywooky for replying,

      I checked the solution there it's written (len+k)/(k+1). Can you explain me how our we getting this formula?

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

        The blocks (ie. len) is of calculated length, see the three points above in the editorial. Then, the meaning of len is as if the whole string would be of len zeros. No 1 left, no 1 right.

        In such a string we can put a 1 at first position, then for every block of k+1 positions one more. This is exaktly (len+k)/(k+1)

        I would have preferred to write (len-1)/(k+1) + 1, which is the same.

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

          why (len+k)/(k+1) ? and not (len)/(k+1)? Not able to get it.Can you explain?

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

            You can put a 1 at position zero. Then you are left with len-1 items, and can place (len-1)/(k+1) items. So answer is (len-1)/(k+1)+1

            Since $$$(a+b-1)/b = (a-1/b)+1$$$ it is that $$$(len-1+k+1)/(k-1)=(len+k)/(k-1)$$$

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

              I am very much near to it brother Just one thing i wanna ask,

              Why it is (len+k)/(k+1) and not (len+k)/(k)?

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

                If the string is like 1000000... and has n zeros, then you can place n/(k+1) ones in it.

                Because you need to let k zeros as is, then change one to '1', and so on.

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

                  Thank You So Much for the explaination Brother.

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

Can anyone help me understand these last lines of F2 editorial — It is necessary to separately consider the first numbers in the subsequence and the last, since the first should include their suffix, and the last should have their prefix.

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

I can't understand the editorial for problem F2. Can anyone explain me what's wrong?

That is, the task came down to finding the maximum sorted subsequence in the array. So if we have testcase:

5
0 1 2 4 3

The max sorted subsequence in the array will be 0 1 2 and the answer will be (n = 5) — 3(length of the max sorted sequence)? But if we move 4 to the right we can get sorted sequence only in one move?

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

    In the original array, you just need a non-decreasing subsequence(not necessarily contiguous), but those values must be contiguous in the sorted array (otherwise you would have to insert something in between them without moving the elements themselves, which is impossible with given operations). So the max sorted subsequence is 0 1 2 3 because it is contiguous in the sorted array but is a non-decreasing subsequence in the original. Therefore the answer is 5 — 4 = 1 as expected.

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

In F , for the case: n=4 , a=[0,2,1,3] longest sorted subsequence is 3 , then as per editorial answer is 1 (4-3=1) right ? But expected answer is 2 ? Can someone explain what i am understanding Wrong ?

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

    It is supposed to be the longest non-decreasing subsequence that is contiguous in the sorted array. In this case, the sorted array is [0, 1, 2, 3]. The only longest subsequences that satisfy this are [0,1] and [2,3]. There is no contiguous set of 3 elements in the sorted array that are non-decreasing in the original. So as per the editorial, 4 — 2 = 2.

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

      Missed the point that elements have to be continuous .got it now . Thanks

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

Can someone provide strong test case for E? I got this: wrong answer 65th numbers differ — expected: '15', found: '12' from test #3

This is my code.

void solve(int n, int k){
	vector<int> v(26,0);
	char ch;
	for(int i = 1 ; i<=n; i++){
		cin >> ch;
		v[ch-'a']++;
	}
	for(int i = n; i>=1; i--){ //i is length
		int repeat = (k%i==0)? i:min(k%i,i-k%i);
		if(i%repeat!=0){
			repeat = 1;
		}
		int b = i/repeat;
		bool ok = false;
		for(int j = 0; j<=25; j++){
			repeat-=(v[j]/b);
			if(repeat<=0){
				ok = true;
				break;
			}
		}
		if(ok){
			cout<<i<<endl;
			return;
		}
	}
	cout<<"1"<<endl;
	return;
}
»
5 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Can someone explain the implementation of F2. When doing the dp for the longest non-decreasing subsequence, how is the 'contiguous in the sorted array' requirement checked? Also isn't LIS an O(n^2) dp, so how does it fit in time constraints?

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

    LIS wont work here

    and LIS can be done in O(nlogn) using binary search.

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

why (len + k)/(k + 1) in problem c. why not (Len)/(k) ??

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

If anyone is stuck in C here is some example with case discussed in the tutorial Here

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

In editorial it's said that in F2 the answer is always n — length of the longest sorted subsequence. But there is no proof for that. Tell me if I'm right or wrong. Having found the longest sorted subsequence, I can in one step make it one element longer. So it's gonna take (n — length) steps to sort the whole array. Suppose there's a way to sort the array in even less number of steps. Then on some step I'll make current subsequence at least 2 elements longer which is impossible because I only move one element per step.

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

In anyone of you is wondering why your code for F2 failed for test case : 3(4999th), well it's because you didn't consider that case when your subsequence will contain two different elements.

For the sake of reference here is the test case:

t = 1 n = 20 array = 3 2 7 9 14 8 6 11 10 7 5 7 2 8 8 4 7 1 13 12 16 answer : 15,

if yours is 16 this might be the reason

My submission AC: i too ignored that case :)

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

Can someone please explain me how did this code snippet help in finding the maximum sorted subsequence? for(int i=0;i<N;i++) { if(a[i].fi!=a[i-s1.size()].fi) { for(auto x:s1) { s.insert(x); } s1.clear(); } while(!s.empty()&&*s.begin()<a[i].se) { s.erase(a[now].se); now++; } s1.insert(a[i].se); ans=max(ans,(int)(s.size()+s1.size())); } printf("%d\n",N-ans);

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

Can anyone please explain what is dp2 and dp3 for in problem F?

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

I'll try to explain my solution of 1367F2 - Flying Sort (Hard Version) in details.

Disclaimer: it's hard way to solve it.

Horrible wall of text
»
5 months ago, # |
  Vote: I like it 0 Vote: I do not like it

For problem E why can't we just iterate and the find the number of repeating modk directly.

For example if we have length 6 = 0 0 0 0 0 0 and k = 3. Then by going over once, we know the array is = x 0 0 x 0 0. So our array is now [2,2,2] which we need to fit with our beads.

Similarly for k = 4. And a necklace of length 6 = 0 0 0 0 0 0 We get this array after traversing through mod = x 0 x 0 x 0 So now our array is [3,3] which we need to fit with our beads.

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

a

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

Codeforces round#650 Div 3 Problem: 1367C Social Distance https://codeforces.com/contest/1367/problem/C my code is not working . Please help me. My code: https://ideone.com/Dt76cw

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

How to solve D?

I am unable to understand editorial ............pls Help!

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

Hey. guys! About problem C: we DO NOT NEED to write s[j]=='1' in line int right = j<n && s[j] == '1' ? k : 0; If j<n then j will stop on s[j]=='1'(read code). But if j=n (after last char) we have such situation : "....100000". I have got another solution: let is put exactly k '0' before and after the string and then put exactly 1 '1' before and after string. Such as '1000...00' + S + '00..0001'. Then easy code: res=0; for(int i=0; i<n-1;){ if(s[i]=='1'){ len=0; i++; while(s[i]=='0'){ i++; len++; } if(len>2*k)res+=(len-k)/(k+1); } } cout << res << "\n"; My sol: 91778273

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

Can someone help me with F1?

»
13 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Hello!! I don't undertand why in problem 1367E Necklace Assembly, If I take the position way i+k÷ m I have a cycle Sorry for my english. I need your help.