vovuh's blog

By vovuh, history, 4 months ago, In English,

1335A - Candies and Two Sisters

Idea: vovuh

Tutorial
Solution

1335B - Construct the String

Idea: MikeMirzayanov

Tutorial
Solution

1335C - Two Teams Composing

Idea: MikeMirzayanov

Tutorial
Solution

1335D - Anti-Sudoku

Idea: vovuh

Tutorial
Solution

1335E1 - Three Blocks Palindrome (easy version)

Idea: MikeMirzayanov

Tutorial
Solution

1335E2 - Three Blocks Palindrome (hard version)

Idea: MikeMirzayanov

Tutorial
Solution

1335F - Robots on a Grid

Idea: MikeMirzayanov

Tutorial
Solution
Solution (actually _overrated_, fastest O(nm log nm))
 
 
 
 
  • Vote: I like it
  • +115
  • Vote: I do not like it

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

That anti-sudoku approach is the coolest approach ever possible!!

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

I like Problem D, it's really interesting.

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

    Idea is good, but problem is obvious.

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

      Maybe.

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

        How to solve problem A ?

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

          that's simple, you've to output (n-1)/2. you can see it on your own its obvious.

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

          learn stars and bars algorithm it will help you even if there are more than 2 variable

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

    how to solve candies problem ?

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

      if n is even then there are n/2 — 1 ways to distribute eg : n = 6 , ways are (5, 1) , (4, 2) but (3, 3) cannot come as condition is a > b , so if n is even then equal pairs cannot come thus ans is n/2 — 1 if n is odd then answer is obvious n/2

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

for question B,why my solution is wrong.Can you give me some advice?This is my first time participating in a contest. Thank you!

	string alphabet = "abcdefghigklmnopqrstuvwxyz";
	while (t--) {
		int n, a, b;
		cin >> n >> a >> b;
		char *s=new char[n+1];
		for (int i = 0; i < n; i++) {
			if (i < a) {
				s[i] = alphabet[i % b];
			}
			else {
				s[i] = s[i - a];
			}
		}
  • »
    »
    4 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    check this: 78 39 26

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

    In alphabet string, you have repeated 'g' twice, hence for test case 10 10 10 It fails.

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

    Instead of hardcoding alphabet to get 'c' letter you can write 'a'+2, to get 'h' write 'a'+7.

    Also, managing char* is more difficult than strings. You can make an empty string of length n by typing string s(n) and then you can access elements by s[i].

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

    except the mistake of alphabet, this solution is wrong itself...

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

      I found this mistake, thanks, I'm really stupid:)

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

      My fault, when a gets bigger, so does the step.

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

    take input char str[1000000]='abcdefghijklmnjklmnopqrstuvwxyz' and yes u repeat g twice

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

Can someone please help me with my submission for problem C? Here is the link: 76600537

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

Last Round we saw the easiest A possible but I think this round's A was easier than it. And thanks for another great Div3 vovuh.

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

My solution for C is similar to the one mentioned here just that I use map instead of vector but something weird happens when I input first two numbers i.e t and value of first 'n', it gives me an unexpected output instead of waiting for the array elements 'a[i]' . Not asking anyone to debug my whole code (logic) just point out why this happens because I am not able to solve this issue. If I seem too desperate, don't down-vote me and tell me to correct my approach.

#include<bits/stdc++.h>
using namespace std ;
map<int , int > m ;
map<int , int >::iterator itr; 
int main ()
{
	int t ;
	cin >> t ;
	while(t!=0){
		int n ;
		cin >> n ;
		int a[n] ;
		for(int j = 0 ; j < n ; j++){
			cin >> a[j] ;
			m[a[j]]++ ;
		}
		int mx = 1; 
    	for (itr = m.begin(); itr != m.end(); ++itr) { 
			mx = max(mx, itr->second) ;
		}
		int ans, s = m.size() ;
		if(s == mx )
			ans = mx &mdash; 1  ;
		else
			ans = min(mx, s) ;
		cout << ans << "\n" ;
		t-- ;
	}
	return 0 ;
}

  • »
    »
    4 months ago, # ^ |
    Rev. 3   Vote: I like it 0 Vote: I do not like it
    1. You need clear your map at the starting of each test case using m.clear()

    I submitted your code 76658706

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

      It still shows the same problem, moreover I think will be better to put

      map<int , int > m ;
      map<int , int >::iterator itr; 
      

      inside the while loop to avoid using clear()

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

      What is the logic behind this approach?? And why s==mx gives ans as mx-1?? Plz help me out

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

        consider the case

        1
        7
        1 1 1 1 2 3 4

        here s = mx = 4

        if we use 4 distinct elements 1 2 3 4 in the first set, we are left with only 3 1's for the second set and as the size of both the sets should be equal it is invalid, similarly if we use 4 1's in the second set then we are left with only 3 distinct elements for set 1. hence if s == mx, Ans = mx-1

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

For the B question, just repeat the distinct characters one after another n times.

#include <bits/stdc++.h>
using namespace std;
int main() {
    int t;
    cin>>t;
    while(t--){
        long long int n,a,b;
        cin>>n>>a>>b;
        int x = 'a';
        int cnt =0;
 
        for(int i=0;i<n;i++)
        {
            cout<<char(x+cnt);
            cnt++;
            if(cnt > b-1)
                cnt=0;
 
        }
        cout<<endl;
 
    }
}
»
4 months ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

Anti Soduko solution is damn cool..

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

Thank you vovuh.Great contest.This contest motivated me a lot.

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

Why the time complexity of solution E is $$$O(Nk)$$$. It seems that it enumerates all possible lengths in $$$O(N)$$$ and iteraters all possible pair $$$(a, b)$$$ in $$$O(k^2)$$$.

UPDATE: Here is my code:76588322

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

    Actually, you just pass through all positions of each characters. So in total, you just pass through N elements, which means n segments. Therefore, time complexity is just O(Nk)

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

      Thanks, but I still don't quite understand.

      I have added my code to the post. Would you give an explanation based on the offical solution or my solution. Thanks in advance.

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

        Note that we are making an array of size K such that the ith element contains a vector of the positions of value i. So its quite clear to see that the total number of elements in the entire array is equal to N. In the solution, we are traversing through each vector, say v, and just keeping two pointers at the ith and (v.size()-1-i)th positions and then we are iterating through all values from 1-200 and finding the answer. So for each vector, we are finding a possible answer in O(v.size()*K). Since there are K vectors, the overrall complexity is O(v1.size()*k + v2.size()*k +.... v200.size()*k) = O(NK).

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

          I got it! The total number of all vector v is not nk but n. So the time complexity is O(nk) .

          Thanks bro!

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

          I had the same doubt. Thanks for the explanation!

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

          thank you

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

    Actually, possible pair (a, b) is not calculated in O(k^2), it's calculated in O(k). It seems like O(k^2) but it's not. Just take pen and paper and check the sample case. You would get it. I got the exactly same solution but became fool thinking of my solution would be O(n*k^2) and didn't submit that. I got to know mine is O(n*k) later.

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

How i can solve (problem E) by dynamic programming

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

why the C problem can do that,can you explain?

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

Can someone please tell me what's wrong in my 76608051 as it gave runtime error while running perfectly fine on my local system.

My basic approach was I made a vector of vector of size 201 as the range of input is between 1 to 200 and I stored the occurrences of each number in the corresponding position. Finally, I iterated each of the numbers from 1 to 200 and I calculated the maximum possible answer.

I calculated the answer as I iterated the current element taking indexes from starting and ending while calculating the maximum possible frequency of another distinct element that can be inserted in between. I calculated the maximum frequency in range by binary search.

Please help me with it.

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

Problem E2 is very nice. What is the Mo's algorithm approach?

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

    E2 was super nice and it fooled me.

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

    The solution described in editorial iterates over all 200 elements to find maximum frequency between indices l and r. This iteration can be avoided using Mo's algorithm. Finding maximum frequency in a range is a classical problem. See this

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

      Oh, I see it now. Thanks!

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

      There would be approx n^2 ranges....how can I do it with Mo's algo

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

        I have same doubt, Can someone please explain this in detail?

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

          I can never understand how this down voting thing works here and I know I will be getting many more downvotes on this , but I just asked a doubt, that sometimes feels like a curse. I thought the whole idea of codeforces is to make people better at algorithms.

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

        same doubt ..have u got the answer ?? if u got then plz explain

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

          I got that... for every x from 1 to 200 take first k occurences from the left(from 0th index) and same from right....and between them count the maximum frequnecy using mo's algo

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

        It is mentioned in the editorial that there are O(n) segments only.

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

Is there any reason why system testing has been really slow for the past few contests?

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

Why D Anti-Suduko in giving wrong if we replace any number in a row and only giving right if we replace one ?

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

    For every row, column and block, the nine numbers shouldn't be distinct.

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

      In beginning all the numbers are different so if I repeat any one of them then there won't be 9 distinct elements in rows/col.

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

        What about the blocks?

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

          how is changing all 1's to 2's handling the blocks ?

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

            In the original Suduko, every row, column and block contains 1-9, 9 different numbers. After you change 1's to 2's, every row, column and blocks will contains a couple of 2, which meets the Anti-Suduko constraints.

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

            After replacing all 1's with 2's, the entire sudoku table has no 1's, hence only 8 distinct elements. The number of distinct elements per row/column/block can not exceed the number of distinct elements in the entire table.

            Or, another way to think about it, choose an 1. In the initial table its row, column and block contain 9 distinct elements each (including 2s). If you replace the 1 with a 2, you get a duplicate in each of them. That way you take care of 1 row, 1 column 1 block by 1 replacement. The initial table contains a total of 9 1s, replacing each of them takes care of 1 row, 1 column, 1 block, all of them different from the ones handled by previous replacements, because in the initial array there were no 2 1s in the same row or column or block.

            Instead of 1 and 2 you can pick any 2 distinct numbers between 1 and 9 (both inclusive) and apply the similar process. The solution will still work.

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

In the second question, My solution was not accepted

Here is my code 76582843

I got WA on the second testcase However, i am having difficulty in coming up with testcase for which the code will produce a wrong answer.

Can someone please help me..

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

    There should be exactly b distinct letters in a subarray of size a. Not more than that and not less than that. You handled the condition of less than but didn't handle more than that condition. Just see the test 2 case 1.

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

Can someone share the Mo's algorithm approach for problem E2 ? Thanks in advance.

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

Can someone please explain what this does in Problem B? I am a total newbie to these cp. This was my first contest.

for (int i = 0; i < n; ++i) { cout << char('a' + i % b); }

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

    Each char has got a different ascii code. By adding i % b, you take the char with ascii code 97 + i % b. This value is always between 97 and 122, so it represents a valid lowercase letter.

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

      Thanks for the reply. But how does it ensure that b number of distinct letters are printed out in the sub string of length a? Also, how does it print the other random characters? Sorry for making so many questions.

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

        i % b is the remainder of i when divided by b.
        For example, the string with b = 5 is
        abcdeabcdeabcde...
        because 'a' + 0 % 5 = 'a' + 5 % 5 = 'a', 'a' + 1 % 5 = 'b', etc.
        Notice that, for each substring of length b, b different letters are printed out because the remainders are all different. So the strings of length a
        - contain at least b distinct characters because they contain a string of length b
        - contain at most b distinct characters because the whole string contains only b distinct characters
        Hence the condition is true for each substring of length b.

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

In the que:"E:Three Blocks palindrome" the sol gives wrong answer for the array: 1 2 2 1 3 1 2 1 It gives ans as 5 but correct answer is 6 i.e. by removing a[4]:-(3) and a[6]:-(2) Please see into it. and explain if i am wrong

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

    After removing 4th and 7th element as you say array look like : 1 2 2 1 1 1, but this is not a Three Blocks palindrome.

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

      yeah sorry i didn't read the question correctly. my bad due to it i got wa

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

What does AL denote in the time complexity of Problem E2?

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

    The alphabet size which is 26 for E1 and 200 for E2.

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

In problem F solution, what fans & sans array meant for?

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

In problem F, this is how I approached it. Since each vertex has out-degree = 1 and the matrix can be thought of as a directed graph, hence we can say that the graph contains multiple components and each component has exactly one cycle. Now multiple paths might converge into the same cycle. Hence the maximum number of robots that can be placed is equal to the sum of length of each cycle.

For the second part of the question: Think of the graph to be inverted.(We don't actually need to invert it) Number each cycle from 0...(length of cycle — 1). Mark all vertices of this cycle as visited Now apply dfs from each vertex of the cycle and assign a number to each vertex : number[child] = number[parent]+1 (still thinking of graph to be inverted) Now for each black cell we take the modulo of its number with the length of the cycle in its component.

Answer to second part = sum of distinct remainders for each component.

Is this logic correct? I am getting WA on test 2 (1248th number differs by 1).

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

    It seems to be correct and is exactly what I did. My implementation is a little over complicated but if you can check it out in my submissions and it was accepted.

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

    You should apply multi-sourced bfs instead of dfs to assign the numbers.

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

    Yes its correct, can you please share your code? then probable i can help you solving your problem.

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

      Please check this code i added some comments, i hope it will help you.

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

        I forgot to update. I had corrected my code. There was a small implementation mistake. Thanks for reaching out though.

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

          Can you please Explain your approach to part 2 more clearly !!!

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

            For every cycle choose a vertex in it as root of this cycle, then for every vertex in this component calculate how many turns it takes to reach the root for the first time module length of the cycle and store it in $$$fs_v$$$, then two robots one starting at $$$v$$$ and other at $$$u$$$ will collapse iff the condition below holds :

            1. $$$u$$$ and $$$v$$$ are in the same component.
            2. $$$fs_u$$$ is equal to $$$fs_v$$$.

            It can be proved easily, it's quite different with what he said but after thinking a bit you will find out that they are both the same.

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

In problem D is it necessary to only replace all 2 with 1 or can we replace any other particular number with something different. For eg: all 3 with 4?

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

    You can. It's just random.

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

    It can be random. The reason behind it is in sudoku, all the numbers in each row, column and $$$3 \times 3$$$ cell have to be different. The input we are given will represent valid sudoku board. That's why replacing any number with any other number will make it anti-sudoku, since every number occurs exactly $$$9$$$ times.

    I was wondering why the solution works until I googled how to play sudoku. :p

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

Hello everyone, This is the first time I participated in a contest. I couldn't find a good explanation or solution to construct the string problem in Python 3.

Can anyone help me to get through the problem solution?

Thanks

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

    It's easy when you observe some pattern in making such string,
    There is a requirement of generating n sized string of which all substring of size a have only b unique characters.
    Consider this example :
    n=17 a=5 b=3
    So take any unique characters for b, say b_pattern = "abc" or "wdf" or anything, make sure they are unique for length b
    Now make a string of a characters by repeating b, So a_pattern = "abcab"
    Now make a string of n characters by repeating a, So final_anwser = "abcabcabcabcabcab"
    Now you have made sure that a_pattern contains only b unique characters as it is made from b_pattern
    So when you consider all substring of final_answer you will see that there are only b unique characters
    For above testcase, substring like :
    from [0:5] = "abcab" {a_count=2, b_count=2, c_count=1}
    from [1:6] = "bcabc" {a_count=1, b_count=2, c_count=2}
    from [2:7] = "cabca" {a_count=2, b_count=1, c_count=2}
    from [3:8] = "abcab" which is equal to 1st substring, so there is repeating pattern in substring also, so we conclude thatfrom this approach our answer will be correct

    Now in case of its implementation we don't need any counters or etc, we just now care for n and b,
    create b_string, repeat it for n/b times in final answer and append n%b characters in final answer

    This is my submission for python 3 : 76678117

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

      Hi Yash,

      Thanks a lot for making it simple. :)

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

        I was afraid that I may have made it complex but works for you...Well wish you great codeforces journey! :)

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

          No :P

          I made this problem so complex in my head that I started thinking solutions using complex methods.

          Anyways, as it was my first contest and I saw you have quite good ratings. Hard work!

          I would like to ask that though the contest was for Div-3, it has problems A, B, C..in the order of increasing difficulty and meanwhile I practiced only A and B level problems on the problem page.

          What was your strategy, in the beginning, should I go ahead and try to solve D,C..E level problems of the contest or get back to problem page.

          Thanks

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

            Well I am a beginner just like you...
            For consistency, I daily do A, B problems from recent contests and follow editorials if not able to solve...
            Meanwhile, I learn new DS and algorithms and solve problems of that kind
            When I will feel that I am comfortably able to solve A, B then I will leave my comfort zone by daily practicing harder problems...this technique works for me but you should use whatever you feel right! :)
            Just make sure you strengthen your DS and algorithms.

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

              Okay, Yash. Thanks for sharing your part.

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

Editorial of problem F is awesome!!

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

How to solve E1 with Top down dp?

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

For problem E I tested my code on various editors for test one they gave correct answer,,, but codeforce gives this error in 1st test case itself ??Why can any one explain????

Solution link:https://codeforces.com/contest/1335/submission/76633420

Diagnostics detected issues [cpp.g++17-drmemory]: ~.M~~ Dr. Memory version 1.11.0

~.M~~ Running "program.exe"

This application has requested the Runtime to terminate it in an unusual way. Please contact the application's support team for more information.

C:/Programs/mingw-w64-7/lib/gcc/i686-w64-mingw32/7.3.0/include/c++/debug/vector:417:

Error: attempt to subscript container with out-of-bounds index -1, but

container only holds 3 elements.

Objects involved in the operation:

sequence "this" @ 0x11357920 {

  type = std::__debug::vector<std::pair<int, int>, std::allocator<std::pair<int, int> > >;

}

~.M~~

~.M~~ NO ERRORS FOUND:

~.M~~ 0 unique, 0 total unaddressable access(es)

~.M~~ 0 unique, 0 total uninitialized access(es)

~.M~~ 0 unique, 0 total invalid heap argument(s)

~.M~~ 0 unique, 0 total GDI usage error(s)

~.M~~ 0 unique, 0 total handle leak(s)

~.M~~ 0 unique, 0 total warning(s)

~.M~~ 0 unique, 0 total, 0 byte(s) of leak(s)

~.M~~ 0 unique, 0 total, 0 byte(s) of possible leak(s)

~.M~~ ERRORS IGNORED:

~.M~~ 2 potential error(s) (suspected false positives)

~.M~~ (details: K:\invoker-prod\work\codeforces6\60c583d1d5042c09b8b90fe60fe5fe0b\check-acfb434e06065bfe7c8a7fcb2d8ca975\run\DrMemory-program.exe.3432.000\potential_errors.txt)

~.M~~ 22 unique, 26 total, 39452 byte(s) of still-reachable allocation(s)

~.M~~ (re-run with "-show_reachable" for details)

~.M~~ Details: K:\invoker-prod\work\codeforces6\60c583d1d5042c09b8b90fe60fe5fe0b\check-acfb434e06065bfe7c8a7fcb2d8ca975\run\DrMemory-program.exe.3432.000\results.txt

~.M~~ WARNING: application exited with abnormal code 0x3

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

Can someone recommend problems similar to F?

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

Notice that for problem F, once you draw the graph, you'll find that it is a bunch of components which each look like a directed cycle with some ordered trees going into them. Then for each component, the maximum number of robots you can place is equal to the cycle length in that component (since sooner or later they all end up in the cycle). Find a node in the cycle corresponding to one component and do a reverse BFS from this node and compute all distances in the component to this node. Notice that if two robots are placed at the same distance from this node modulo cycle length, they will collide after some time. So greedily try placing robots on black nodes which have different distances modulo cycle length, else place on white node.

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

I liked the way the 2D matrix is stored in the fastest solution of F.

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

Hey, I think i did problem C on the coolest way using map! I used map to count the no of ocurrences then chose the max occurence as one team. then i took the length of map-1 as the no of players in second team. then if there remains difference in no of plaayers, i fixed!

//# include<bits/stdc++.h>

using namespace std;

typedef long long ll;

//# define FASTIO ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);

int main()

{

FASTIO;

int t=0; cin >> t;

while(t--)

{

    int n=0; cin >> n;

    int ar[n];

    unordered_map<int, int> m;

    int huge = 0;

    for(int i=0; i<n; i++){

        cin >> ar[i];

        m[ar[i]]++;

        if(m[ar[i]]>huge) huge = m[ar[i]];

    }

    if(n==1){

        cout << "0\n"; continue;

    }

    if(n==2){

        cout << "1\n"; continue;

    }

    int a = m.size()-1;

    int ans = 0;

    if(huge<=a) ans = huge;

    else{

        ans = a;

        if(huge-a>1)

            ans++;

    }

    cout << ans << '\n';

}

}

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

    nice, thanks. with this test case else part make much more sense 1 15 1 1 1 2 2 2 3 3 3 4 4 4 4 4 4

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

problem F and if nm has the deg-th bit on, just jump from the current vertex 2deg times (set v:=nxt[v][deg]). why should i only jump if deg-th bit is on in nm ?

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

That solution to D. OMG.

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

    could u plz explain ?? there will be approximately n2 ranges so how u solved for most frequent value in a range using mos algorithm ?? . i would be highly thankful to you if u help me.. plz help

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

      no there will be n/2 ranges.our problem was just to find most frequent element in ranges. and these ranges are made by indexes of element having same value. consider below example

      arr=[1,1,2,3,2,2,1,1] one of the range will be (consider 1-based indexing) l=2,r=7 (as first 1 and last 1 will form "a" in three block palindrome and then we just have to find max frequent element in range [index of first[1] + 1,index of last[1]-1] which will be "b")

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

        if i am not wrong u are saying that for each k from 1 to 200 we are just traversing over size[k]/2 in the first 2 loops (summation of these k will give atmost n) and in the third loop we are checking for each k hence overall o(nk).... so if we do use mo's algo then in vector there will be atmost n (basically n/2) ranges which we can solve easily .... please do tell me if i am correct or wrong

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

          yes u are right. we just make query structure in which we store l,r,cnt (cnt will store the 2*x, basically segment formed by "a") and then we will apply mo s algo to find max(answer to the range+cnt) for all ranges and hence overall time complexity will be (n/2+n)sqrt(n) which is basically O(n*sqrt(n))

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

            thanks a lot ... i misunderstood my complexity and thought it to be nk2 .. it is just n*k thanks a lot dear

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

            In this problem we need to find the palindrome 'aba'. How do you find 'a' in complexity less than O(nC) where C is the total of distinct numbers? I understand that you use Mo's algorithm to search for the most frequent number that will be in b.

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

        instead of using mo you could have used prefix sum to store the frequencies of each element at each point and then you could have taken the element with max frequency.

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

          yes u are right,for this question prefix sum approach is better because of additional constraint on count of distinct elements.

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

can anyone tell me whats going wrong with the code.https://codeforces.com/contest/1335/submission/76681472

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

Today I've got an interesting masage from codeforces: Attention!

Your solution 76548547 for the problem 1335E2 significantly coincides with solutions oleh1421/76548547, oleh1421/76549567. Such a coincidence is a clear rules violation.

Well,as you can see, both of those solutions are my, so... does this realy violates the rules?

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

The solution for E1 that is explained here but written in python got TLE on test 12. Is this because python is slow? What can i do to solve this in py?

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

Can anyone explain why this O(n) solution of Problem C was giving me TLE? https://codeforces.com/contest/1335/submission/76571599

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

    This is because of initialization of memory to an array named r inside the while loop which has a size of 1e6 and 2nd test case has t as 1000 so you are initializing memory for 1e9 ints which I think can take time. Well you don't need 1e6 elements in array r as constraints of this problem says 1<=a[i]<=n...
    Here is the solution which I modified from your source and passed tests : 76697932

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

      Thanks for your help! But the given time limit said 1 sec per test. So in a single test I'm only initializing 1e6 int right?

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

        In a single test there are 1<=t<=1e4 test cases.
        And you are initializing memory of 1e6 per test case, which makes 1e6*1e4 = 1e10 memory initialization per test. Your code has to process a maximum of 1e4 test cases in 1 second which can lead to a heavy memory operation for 1e10 memory inits, so it would be better if you initialize your array only once in outside the loop as I did in the previous submission of yours and then just loop it through per test case for resetting its values.

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

can anyone explain problem E?.it's really seem hard to me.

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

Why on Earth is K = 24 in the last code listing?

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

Can Anyone please tell me why the complexity of E2 described above is n.AL ? I think it should be N*(AL^2).

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

In the problem E1, can't we just do it with simple recursion using two-pointers and DP. Can anyone tell me the test case where my recursion code fails? https://codeforces.com/contest/1335/submission/76697089

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

    You are not checking that in a 3 block palindrome, only 2 symbols are possible in your recursion. Your recurstion gives the answer for total no. of palindromic subsequences rather than 3 block palindromic subsequences.

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

      I have checked that using set. I have made a base condition where I check if the size of set becomes greater than 2 then I return 0.

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

plz tell how to solve problem e1 with explanation

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

Can someone help me debug my solution for E1 https://codeforces.com/contest/1335/submission/76608293

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

when the ratings of this contest will be updated??

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

If anyone know the O(nlogn) soln for E2, please post.

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

regarding candy problem is there any specific method for these types of problems or it's just practice. like during contest how we'll know that we have to output (n-1)/2 only. i have done it nested loop btw.

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

I am getting TLE on Problem C on test #2. Not able figure out the case.

#include <bits/stdc++.h>
using namespace std;
int main() {
	ios_base::sync_with_stdio(false); 
    cin.tie(NULL);  
	int t,n,val;
	cin>>t;
	while(t--){
		cin>>n;
		int distinct=0,max_same = -1;
		vector<int> count(200010,0);
		for(int i=0;i<n;i++){
			cin>>val;
			if(count[val] == 0) distinct++;
			count[val]++;
			max_same = max(count[val] , max_same);
		}
	(max_same == distinct) ? cout<<max_same-1<<endl : cout<<min(max_same,distinct)<<endl;
		
	}
}
»
4 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Why am I getting Memory Limit Exceeded on E2 even though my code is logically the same as given in the tutorial (even the data structures used are the same)?

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

    you defined int as ll isn't necessary in this case.

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

      Using ll instead of int gave me problems for the first time. Thanks for the help!

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

Why the time complexity of problem E2 is $$$O(n.AL)$$$? I came up with this approach but I calculated the time complexity is $$$O(n*AL^2)$$$? Anyone can help me, thanks.

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

For Robots on a Grid (problem F) there is an easier, O(nm) way of finding the loops and equivalence classes:

  • Start by marking all cells as unvisited.
  • While there are unvisited cells:
    • Follow the path from the first unvisited cell, marking each cell with a path number and step number. When you hit a visited cell it is either on the current path or a previous path:
      • If it is on the current path then you have found a new loop, and you know its size from the step number of the visited cell. You now have ls new equivalence classes of cells, where ls is the size of the loop. Mark each cell on the path with its equivalence class. Also, for each new equivalence class created remember whether you have found a black cell in that equivalence class.
      • If the visited cell is on an old path, then you know the equivalence class of the visited cell, so you can work back along the path working out the equivalence classes of the cells on the new path. Mark these, and check for black cells in each equivalence class.
  • Print the total number of equivalence classes, and the number of them that contain black cells.

See https://codeforces.com/contest/1335/submission/76714155

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

    EVen i am using the same concept ,but I got a wrong answer on test 50 offile 2. https://codeforces.com/contest/1335/submission/76685166

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

    Don't you need to consider black cells in the same equivalence class eventually collides with each other? For all black cells that are in the same equivalence class, only the ones that won't collide can be considered as robot placing candidates.

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

      Yes, everything in a particular equivalence class will eventually collide. That is why you count the equivalence classes containing black cells, not the black cells. Each equivalence class is counted at most once.

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

        I do not understand.

        The question is for the max number of possibly used black cells. This should be the minimum of "black cells in the equivalence class" and the "size of the loop". Not?

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

          What you may be missing is that I am creating multiple equivalence classes for each loop (as is the solution in the tutorial), one for each position in the loop. Even if there are multiple black cells in a single equivalence class one cannot use them, since robots in the same equivalence class will collide.

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

Can someone please help me to figure out what's wrong with my solution? (Problem D) My code passed test 1 but failed test 2. The test case is so complicated. I cannot even figure out what's wrong.

My solution is pretty straight forward. For row i, i in [0,7], add 1 to col (3*i % 8). For row 8, add 1 to col 8.

Here's my code:

#include <iostream>
using namespace std;

int main(){
  int loop,tem,col=0;
  string str;
  cin>>loop;
  for (int i =0;i<loop;i++){
    for (int row=0;row<9;row++){
      cin>>str;
      if (col != 8) col = col%8;
      tem = str[col]-'0';
      tem = tem % 9 + 1;
      str[col] = tem+48;
      cout<<str<<endl;
      col += 3;
    }
  }
}
»
4 months ago, # |
  Vote: I like it 0 Vote: I do not like it

is there a simpler explanation for E ? :\

>> i cant understand what c and Pref if about ![problem:E1]

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

    First store all position of each elements. It's each to store since elements are less than 201. Traverse through each position and check for most frequent element between two positions. Suppose 1 appears in position 1,3,8,10 Then we need to pick 1 and 10 and add frequency of most frequent element. Answer will be it's frequency+2, and then we need to pick 3 and 8 similarly, answer will frequency+4. Do this with all positions of all elements. Brute force works here. Solution is O(N.200)

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

      Thanks . . I think i started to understand it better

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

I had 1147 rating and this contest I write 3 questions and I earn just 22 ratings. Are you kidding me? If I don't know any rule please teach me!

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

can anyone help me with the code for the last question. I have used dp on trees,i guess. Like the crux is i am finding the cycles and the sum of the length of the cycles is the no.of robots that can be added. Also i am trying to create equivalence classes too for the cycles so that i can find the vertex to be used to fit the robot in.

Here is the link — https://codeforces.com/contest/1335/submission/76685166

I am having a wrong answer on test case 50 of the 2nd test file.

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

still I cant get the logic behind three block Palindrome please help me out.. thank you in advance

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

    As the problem says we can use at most two distinct elements. say these tow distinct elements are a and b. Then the possible combinations are aba, bab . now say we select aba as combination.

    Then we will select how many a we will consider as prefix for our palindrome let this count be 2 and so total count of a should at least be 4 (we have to check this if we can or not). Let l denotes the position where we found 2nd a form the begin ant r denotes the position of 2nd a from the end. then we will count the number of b in range l+1 to r-1. The result for this aba combination will be 2 + (count of b in the l+1 to r-1 range) + 2.

    In this way we can check for all combination and result be the maximum of all these results. Hope it helps.

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

What will be the recursive solution for E-1. I have written some code but I can't figure out the else part. Please help me find it.

 static int fun(int[] a, int x, int y, int c, int prev) {
        //c is number of distinct element is subarray
        if (x >= y)
            return 0;
        if (a[x] == a[y]) {
            if (prev != a[x])
                if (c - 1 > 0)
                    return 2 + fun(a, x + 1, y - 1, c - 1, a[x]);
                else
                    return 2 + fun(a, x + 1, y - 1, c, a[x]);
        } else {
            
        }

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

Can someone please explain this 76572022 solution for problem F. What does st[x],val[x],len[x] mean or explaining the idea in some words would help more (I have given a quite good time still don't get it properly )

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

Please can someone explain E1

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

Can anyone help me with Problem E1 I used an idea similar to Longest palindromic sub-string using Dp. The solution link is https://codeforces.com/contest/1335/submission/76724438

Thanks!!

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

I don't quite understand the explanation provided for B? Could someone please explain the reasoning provided in a bit more detail?

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

Easy to understand java solution for E (both easy and hard version) :

******-----*******

import java.util.*;

import java.lang.*;

import java.io.*;

class Solution {

public static void main (String[] args) throws java.lang.Exception

{

    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

    int t = Integer.parseInt(br.readLine());

    StringBuilder str = new StringBuilder();

    while(t--!=0){

        int n = Integer.parseInt(br.readLine());

        int[] arr = new int[n];

        String[] in = br.readLine().split(" ");

        HashMap<Integer,ArrayList<Integer>> map = new HashMap<>();
        for(int i=0;i<n;i++){
            arr[i] = Integer.parseInt(in[i]);
            if(map.containsKey(arr[i])){
                map.get(arr[i]).add(i);
            }
            else{
                ArrayList<Integer> a = new ArrayList<>();
                a.add(i);
                map.put(arr[i],a);
            }
        }
        int ans = 0;
        for(int i=1;i<201;i++){

            if(map.containsKey(i)){
                int x = map.get(i).size();
                ans = Math.max(ans,x);
                int size =  x/2;
                for(int j=1;j<=size;j++){
                    int leftpos = map.get(i).get(j-1)+1;
                    int rightpos = map.get(i).get(x-j)-1;
                    int[] freq = new int[201];
                    int curr = 0;

                    for(int k=leftpos;k<=rightpos;k++){
                        freq[arr[k]]++;
                        curr = Math.max(freq[arr[k]],curr);
                    }
                    ans = Math.max(curr+(j*2),ans);
                }
            }
        }
      System.out.println(ans);

    }
}

}

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

include

using namespace std;

long long l, r;

long long gcd (long long a, long long b) { return b ? gcd (b , a % b) : a; }

int main() { cin>>l>>r; for (long long a=l;a<r-1;a++) for (long long b=a+1;b<r;b++) for (long long c=b+1;c<=r;c++) if (gcd(a, b) == 1 && gcd (b, c) == 1 && gcd (a, c) != 1) { cout << a << " " << b << " " << c; return 0; } cout<<"-1"; return 0; }

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

Can Anyone Please help me why I am getting runtime error on Problem E2. My code here 76738146 Edit: I changed long long to int and it worked, i still dont know why? anyone explain?

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

    Don't define big arrays in $$$main$$$, or any other function, because a function can have much less memory than application's limits, for example if the memory limit is $$$256MB$$$, then your functions cant have more than $$$32MB$$$, and it will cause runtime error, just define your $$$dp$$$ array before main then you will get ML instead of RE :).

    When using big global arrays and multiple test cases, its preferred to iterate over the part of array that you need instead of using memset, as memset(arr, 0, sizeof arr) will fill the array with zero and it will take about $$$O(sizeof arr)$$$ time and its too much to clear the whole array for every small test case.

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

      First of all, Thanks for the tip. This will stay for life time.DeadlyCritic . You mean, by declaring long long, the memory limit of function exceeded and that is the reason of run time error? right? BTW: you are so nice for giving me the advices.

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

        You welcome, yes the reason of run time is that, also you should use int instead of long long in this problem as the memory limits are though and you don't actually need long long. The numbers i said in my last comment are not completely right.

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

      DeadlyCritic I am also getting MLE on test case 9, even after defining int as ll. 88900051

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

please tell me how the answer for prob C testcase 2 1 5 4 3 is 1

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

    First two important lines of the problem:

    The first team should consist of students with distinct skills (i.e. all skills in the first team are unique).

    The second team should consist of students with the same skills (i.e. all skills in the second team are equal).

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

      so what will the teams look like in this case ? (1,2), (3,4) excluding 5?

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

        You mean 3 is equal to 4?, the second team should have $$$equal$$$ numbers.

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

          no i meant 4 teams in total 1,2 and 3,4 , excluding 5th but again, we are allowed exactly 2 teams . i don't understand how we can divide a team of odd number of members in 2 equal parts . even if the ans is 1 , as in this case , repeating members are not allowed so one will be excluded in the end

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

          if x=1 for 2 1 5 4 3 , then how are the teams formed please tell me that

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

            Teams can be consisted of only one student no matter what is the skill of the student, any choosing two students out of this 5 students then putting one in the first team and the other in the second team will give us a valid solution(i.e $$$team1 : 2$$$ and $$$team2 : 5$$$ is valid).

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

              thanks mate . i did not realise excluding members is allowed.

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

@vovuh Hey, problem D was cool. Your constraint was to use at most 9 changes. I've been thinking if it is possible to do it in lesser moves (like what if someone uses the problem to give a smaller constraint?). Haven't been able to come up with anything for this version though. Do you have a proof as to why you need to make at least 9 changes? If it's possible to do it in lesser, do you have any suggestions on how to go about it? Also, if there's any obvious knowledge that I might be missing, please consider sharing.

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

    Your constraint was to use at most 9 changes. I've been thinking if it is possible to do it in lesser moves (like what if someone uses the problem to give a smaller constraint?)

    Say you make 8 or less moves. Then there is at least one 3x3 square (or at least one row, or at least one column ...) which was unchanged, so it still has the sudoku property.

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

Isn't $$$O(n*200)$$$ memory too much for problem E2 since $$$n <= 2e5$$$?

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

    Sum of n over all test cases does not exceed 2e5. So total iterations will be 200*2e5, wiz O(1e7), wiz O(n)

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

    In fact it will take about $$$160$$$ MB memory, I've got lots of ML verdicts for the problem, as i used 2 arrays of size $$$n*200$$$ :).

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

Could someone explain me why are we doing this?

#ifdef _DEBUG
	freopen("input.txt", "r", stdin);
//	freopen("output.txt", "w", stdout);
#endif

And how do we come up with this equation: 'a' +i%b ??

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

    It is used to take input from a text file and dumping the corresponding output of the code in output.txt on the local machine

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

      Ok. But where has he defined the identifier _DEBUG in the source code? Then how the redirection will take place??

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

        https://www.geeksforgeeks.org/cpp-preprocessor-directives-set-2/

        since it is not defined that's why it won't execute.If it would have been defined then if condition would have been executed

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

          If it's not getting executed then why even bother to put it?

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

            Because while the author is testing his/her code at his/her local system it reads input from the file("input.txt", present at his/her system) instead of user entering values himself. But to submit it doesn't have to read from any such file and have to use standard input stream(stdin) so when the author submits the code he removes the #define DEBUG line from his/her code.

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

              Ok. So where would have the author placed the identifier DEBUG??

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

                Have a look at this code and check the 3rd line. If you delete the third line and run it will accept integers from your terminal, otherwise it will read integers from the file https://pastebin.com/sgrCGMxw

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

                  Got it completely. Thank you so much.

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

This is my solution to the fifth question : https://codeforces.com/contest/1335/submission/76728501

Where is my mistake? I'm using dp

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

how for E O(n^2⋅AL) algorithm pass? n^2 means 10^10 operations. about 10^8 operations takes 1 sec I guess

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

    $$$O(n^2.AL)$$$ solution is for E1, for E2 you should solve it in $$$O(n.AL)$$$ and it's included in editorial.

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

      O(n2.AL) solution is for E1.I know how this can pass time constraints of E1. n^2 means 10^10 operations. about 10^8 operations takes 1 sec I guess

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

        Yes you are right, it passes E1 but not E2, the editorial's solution for E1 only works for E1, not for E2.

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

          why O(n2.AL) solution pass E1? that's what I am asking

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

            Oh, E1 constraints are $$$n <= 2000$$$ and $$$a_i <= 26$$$, so that $$$O(n^2.AL)$$$ will pass it, in fact the solution works much faster than $$$n^2.AL$$$ time, it will work about twice faster, then it will do less than $$$4e7$$$ operations which is fine, it actually worked in $$$70MS$$$ for me.

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

              ohk got that didn't saw it was 2000 not 20000. thanks

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

              t is not included in finding order of algorithm? if t got included it will be like n^3 A as t=2000

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

                No its not like this, as the sum of $$$n$$$ over all test cases is less than or equal to $$$2000$$$, but yes the true order is $$$O(n^2.AL + t.n)$$$.

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

If anyone could help how can I optimise my code so that it could be accepted.It is working fine but is giving TLE for #12 testcase (1 2000).

https://codeforces.com/contest/1335/submission/76779927 Thanks in advance.

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

    This is with regard to the palindrome blocks question.

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

    Avoid using arrays, vectors, sets and other data structures in function arguments, for example you have used $$$arr$$$ as an argument for $$$getSubsequence$$$. Try using global arrays.

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

Nice problem set, problems E2 and F were fine even for Div.1 participants, Div.3 contests are more like global ones, having interesting problems for every participant. Job well done MikeMirzayanov and vovuh.

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

Hey I solved E1 using brute force and E2 I improved my code using binary search so my complexity is O( $$$nlognA_i$$$ ) where $$$A_i$$$ is the maximum value. I cant find a way to make it O( $$$nlogn$$$ ) or thats it ? the actual solution with O( $$$nlogn$$$ ) complexity? here is the part I cant get rid of which causes the $$$A_i$$$ complexity:

 for(int j = 1; j < 201; j++)
	if(j != ss[i])
		middle = max(middle, nm[j][index] - nm[j][i]);

my full code 76745546

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

    Your solution is actually $$$O(nlog_2n + nA_i)$$$, i didn't understand what did you binary search on, but it doesn't mean that i'm not sure about the complexity of your code, also $$$O(nlog_2nA_i)$$$ wont accept without optimizations.

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

      Yeah I didn't write my complexity well thanks for correcting me. I was doing binary search to see if there is a third block that is the same as my first block by looking if there is such sequence that has the same length from the end of array $$$a$$$ (I mean if there is such suffix that has a sequence with the same length) and the same value (get the value from my $$$N * A_i$$$ vector and search in that) and if there is I check of other $$$A_i$$$ numbers sequences between the value from the binary search and where am at to find the maximum one of them.

      I hope you got where I was going with that, and if I may ask can you tell me which approach is better dp or this ?

      thanks again :).

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

in problem D its mentioned that

each 3×3 block (you can read what is the block in the link above) contains at least two equal elements.

The solution mentioned does not fulfill the condition for the input : 1 123456789 912345678 891234567 789123456 678912345 567891234 456789123 345678912 234567891

It gives the output:

113456789 911345678 891134567 789113456 678911345 567891134 456789113 345678911 134567891

Correct me if I am wrong.

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

problem D, there is a simple idea: choose 1 grid from each 3 * 3 block, after choose 9 grid, must cover all row and col, make those choosed grid to be different with its origin value. that will exactly conflict with all sudoku recipe.

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

Cfn somebody explian why my E2 submission passed all the tests? It is really strange.

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

Can somebody please explain the solution of problem E

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

Please explain E1/E2 i could not understand editorial.

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

    For every alphabet 'x' do the following:

    • go through all possible pairs of occurences of x

    • consider those 2 indexes (say {i, j} ) of each pair as boundary for middle block

    • for each such pair, take the most frequent element within this boundary to construct the middle block of required palindrome

    • using prefix sum of all alphabets you can calculate size of constructed palindrome ( min(left,right) + middle + min(left,right) )

    Optimisation for hard version:

    • you need to realise that you don't actually need to go through all pairs of alphabet, as only the minimum frequency from left OR right will contribute to answer

    • so just go through those pairs which satisy freq[1..i][x] == freq[j..n][x]

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

      In problem E2 is not tutorial solution complexity is O(n*al^2)?

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

        Amortised complexity of outer 2 loops will be O(n). So total complexity will be O(n*200)

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

If someone wants to see a small and simple implementation of F : https://codeforces.com/contest/1335/submission/77002174

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

For problem E2. Hey, can someone please tell why am i getting a TLE error for writing a very similar code given in editorial? Here is a link to my code: https://codeforces.com/contest/1335/submission/77012506

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

Anti-Sudoku problem broadens our perspective towards tricky problems and was really interesting and amazing!!!....Thank You @vovuh

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

F:I cant understand "if ((nm >> deg) & 1) " please tell me why thx

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

I didn't understand how could that give the final answer in three block palindrome easy version. Where are we checking if it satisfing the condition for three block palindrome..Can someone explain how this approach meeting the requirements.

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

In E1's Solution, inorder to get max count out of all the occurrences why are we getting cnt[i][n — 1] element, whereas we should be taking cnt[i][n], as the last element has the sum of all number occurrences.

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

How to avoid MLE on F, I keep getting MLE on test 5: https://codeforces.com/contest/1335/submission/77190353

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

Can someone please tell me why is the time limit being exceeded using this code of Python3 for Problem C:

t = int(input())
for case in range(t):
	n = int(input())
	skills = [int(a) for a in input().split()]
	unique = len(set(skills))
	m = 0
	for skill in set(skills):
		m = max(m, skills.count(skill))
	pos1 = min(unique - 1, m)
	pos2 = min(unique, m - 1)
	ans = max(pos1, pos2)
	print(ans)
»
4 months ago, # |
  Vote: I like it 0 Vote: I do not like it

in 1335C someone please explain me the count function, what is that 0 doing as parameter?

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

I am new to dynamic Programming, can someone please explain the problem E1. Thanks in advance :)

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

Can someone please help me with my solution to E2. I've implemented it after going through the editorial since I didn't know how to approach it, but I don't understand why I'm getting MLE on case #9. Thx in advance.

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

PROBLEM F

int v = i * m + j, to = v;
for (int deg = lognm-1; 1; deg >= 0; --deg) 
    if ((nm >> deg) & 1) 
       to = nxt[to][deg];

If we perfom at least nm moves from each possible cell, we will obtain some "equivalence classes". So, why we need the above operation instead of to = nxt[v][lognm-1]?

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

https://codeforces.com/contest/1335/submission/77449681 a general solution to the D problem using a simple math observation .

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

Please explain me why this submission is going TLE for Problem C. According to my understanding the solution is O(t*n). Link: https://codeforces.com/contest/1335/submission/77608775

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

int anti-sudoku problem, I am changing diagonal elements to 9(if initially not 9) else changing to 1(initially 9). Getting WA.

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

    Its because you need to make changes such that every 3x3 square also has one element repeated. Changing the diagonal elements doesn't do the job.

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

      it will, because diagonal elements will get repeated number, either 9 or 1 9 8 9 1 9 3 4 6 9

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

        blinks

        How about the lower left 3x3 square? Or the upper right? It will stay untouched... (If you're changing elements along the main diagonal)

        Otherwise, the lower right 3x3 square or the upper left... well you get the idea.

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

Why is the problem C tagged with Binary Search? How can it be solved using Binary Search?

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

In problem E2 is not tutorial solution complexity is O(n*al^2)?

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

If anyone is interested in E2 Here is explanation with example and code

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

I'm getting memory limit exceeded in test case 5 for F. Submission: 77895714

The logic I've tried to implement is to break the graph into components. Each component would have some equivalent nodes which would collapse if two or more blocks from one equivalence classes are chosen simultaneously. Answer for each component should then be cycle size and no of equivalence classes which have at least one black node.

I would appreciate any input on my mistake.

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

    Problem solved. DFS used led to stack over flow. However, BFS did not cause this problem.

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

      Can you elaborate on your approach? It seems interesting

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

        It has been long since this comment was made. I have looked at it now only. Have you figured it out by now?

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

In solution of E1 forn(i, 26) ans = max(ans, cnt[i][n - 1]);

shouldn't it be forn(i, 26) ans = max(ans, cnt[i][n]);

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

include<bits/stdc++.h>

define ll long long

using namespace std;

int main() {

std::ios::sync_with_stdio(false); cin.tie(NULL);

ll int t; cin>>t; while(t--) { ll int n; cin>>n; vectora; for( ll int i=0;i<n;i++) { ll int k; cin>>k; a.push_back(k);

}

map<ll int,ll int> s;

ll int maxm_count=-1; ll int dist_count=0;

for(ll int i=0;i<n;i++) { ll int x=count(a.begin(),a.end(),a[i]); s[a[i]]=x; maxm_count=max(maxm_count,x);

//dist_count++;
  //i=i+x-1;

} dist_count=s.size(); if(dist_count<maxm_count) cout<<dist_count<<endl;

else if(dist_count==maxm_count) { cout<<maxm_count-1<<endl; } else { cout<<maxm_count<<endl;

}

} }

why time limit exceeded

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

    Well, your code exceeded the time limit, so you get time limit exceeded. As for why, the issue seems to be here:

    for (int i=0;i<n;i++) {
        int x=count(a.begin(),a.end(),a[i]);
        s[a[i]]=x;
        maxm_count=max(maxm_count,x);
    }
    

    count has O(n) complexity, and since you call it n times, your code has O(n2) complexity. Since the maximum bound for n is 2 * 105, your code runs around 1010 operations, which is around 100 times too many.

    This can be fixed by iterating through a and incrementing s[a[i]]. Then maxm_count can be calculated with maxm_count = max(maxm_count, s[a[i]]);.

    Also, in the future, it helps to link your code submission instead of pasting the code. So for this post you could write 78250328 to keep it short and avoid the weird formatting that occurs when directly pasting code into a comment.

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

      thank you, what you suggest i did and it worked.

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

Can someone explain me that how can we do E1/E2 using Mo's algorithm??

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

How to solve Problem C using binary search?

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

PROBLEM — E1

test case : — (1,1,3,1,5) shouldn't answer be (1,1,3,1) so length = 4 but judge gives answer as 3

please help

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

    it should be palindrome too hence 3 is the correct answer because 1 1 3 1 is not a palindrome but 1 1 1 is

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

Could someone explain why the solution for F is supposed to be O(n*AL)? It looks like a clear O(n*AL^2) to me (O(AL)-loop inside O(n)-loop inside O(AL)-loop). I mean this approach is fast enough to get accepted anyway (I just tried), but still...

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

Regarding the tutorial for F, we don't need to jump exactly nm times to find the equivalence classes. Anything >= nm will do. We can just take the maximum deg(lognm) calculated in the previous steps and derive equivalence classes from them. Of course, lognm has to be a ceil(log(nm) / log(2)).

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

why I'm getting a runtime error in problem B? What is the problem with my code? Here's my code in python::::


li = [] x = 'abcdefghijklmnopqrstuvwxyz' sl, n, d = [int(x) for x in input().split()] for i in x: li.append(i) if len(li) < d: continue else: break for i in range(sl): print(li[i % d], end='')
  • »
    »
    2 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Your code will work for just 1 test case. But there can be multiple test cases.;)

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

I did Anti sudoku in different way. For test case given in question , my answer is giving correct output satisfying all constraints. But still giving wrong Answer.Please help. Code:

Your code here...
char a1[9][9];
	    int q=0;
	    for(int i=0;i<9;i++)
        {
            for(int j=0;j<9;j++)
            {
            cin>>a1[i][j];
            }
        }
        int a[9][9];
        for(int i=0;i<9;i++)
        {
            for(int j=0;j<9;j++)
            {
            a[i][j]=a1[i][j]-48;
            }
        }
        for(int i=0;i<9;i++)
        {
            for(int j=0;j<9;j++)
            {
                if(i==8-j)
                {
                    if((i+1)%3==0)
                        a[i][j]=a[i][j+1];
                    else a[i][j]=a[i][j-1];
                }
            }
        }
        for(int i=0;i<9;i++)
        {
            for(int j=0;j<9;j++)
            {
            cout<<(char)(a[i][j]+48);
            }cout<<endl;
        }
»
6 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

is there any video solution for problem E?

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

My solution for Anti — Sudoku goes wrong .Can someone explain it by giving some random test case where it goes wrong!! Link: https://codeforces.com/contest/1335/submission/86219320

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

easiest D....:)