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??

Task D took soul out of me but never showed Accepted

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 ?

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

C can be solved without handling cases separately.

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;
}

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

It felt like a Div 2 contest after C

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

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

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.

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

Video Solution to C and D

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.

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?

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

https://mirror.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

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

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.

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

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

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.

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

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

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;
  }

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)

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

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

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)

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)

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;
}

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

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

Video tutorial for problem E

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://mirror.codeforces.com/contest/1367/submission/83973628

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

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

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://mirror.codeforces.com/contest/1367/submission/84037953

what happened to problem D?

is problem D gone?

Why was problem D removed?

Is problem f actually the famous LIS problem?

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.

@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

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

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);
        }
    }

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

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

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++.

can somebody help me in implementation of F2

Video Solution to E: Necklace Assembly

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

What is upsolve?

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

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

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

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?

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