vovuh's blog

By vovuh, history, 4 years 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

| Write comment?
»
4 years ago, # |
  Vote: I like it +32 Vote: I do not like it

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

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

    I have done that in contest! :D

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

    After reading the solution, I feel very stupid now. Wasted more than 1 hour for this problem. :(

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

    O(n*200) = O(n) approach for E-1/E-2 this code

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

    Another approach for D 109670932

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

      Yr way of writting sid_rasa is in yr snippet is reallly amazing. Can I get to know how would you do it>

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

        Just search Ascii text generator and you can easily do it.

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

I like Problem D, it's really interesting.

»
4 years 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 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    check this: 78 39 26

  • »
    »
    4 years 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 years 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 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

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

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

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

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

  • »
    »
    4 years 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 years 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 years 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 years 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 years 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 years 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 years 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 years 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 years 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 years 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 years 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 years 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 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
4 years 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 years 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 years ago, # ^ |
      Vote: I like it +4 Vote: I do not like it

    E2 was super nice and it fooled me.

  • »
    »
    4 years 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 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Oh, I see it now. Thanks!

    • »
      »
      »
      4 years 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 years ago, # ^ |
          Vote: I like it -9 Vote: I do not like it

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

        • »
          »
          »
          »
          »
          4 years 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 years 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 years 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 years 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 years 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 years 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 years 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 years 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 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        What about the blocks?

        • »
          »
          »
          »
          »
          4 years 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 years 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 years 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 years 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 years 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 years 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 years 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 years 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 years 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 years 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 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    4 years 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 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
4 years 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 years 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 years 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 years 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 years 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 years 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 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

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

          • »
            »
            »
            »
            »
            »
            4 years 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 years 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 years 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 years 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 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Hi Yash,

      Thanks a lot for making it simple. :)

      • »
        »
        »
        »
        4 years 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 years 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 years 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 years ago, # |
Rev. 3   Vote: I like it +6 Vote: I do not like it

Editorial of problem F is awesome!!

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

How to solve E1 with Top down dp?

»
4 years 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]: Dr,2020-04-14.M Dr. Memory version 1.11.0

Dr,2020-04-14.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> > >;

}

Dr,2020-04-14.M

Dr,2020-04-14.M NO ERRORS FOUND:

Dr,2020-04-14.M 0 unique, 0 total unaddressable access(es)

Dr,2020-04-14.M 0 unique, 0 total uninitialized access(es)

Dr,2020-04-14.M 0 unique, 0 total invalid heap argument(s)

Dr,2020-04-14.M 0 unique, 0 total GDI usage error(s)

Dr,2020-04-14.M 0 unique, 0 total handle leak(s)

Dr,2020-04-14.M 0 unique, 0 total warning(s)

Dr,2020-04-14.M 0 unique, 0 total, 0 byte(s) of leak(s)

Dr,2020-04-14.M 0 unique, 0 total, 0 byte(s) of possible leak(s)

Dr,2020-04-14.M ERRORS IGNORED:

Dr,2020-04-14.M 2 potential error(s) (suspected false positives)

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

Dr,2020-04-14.M 22 unique, 26 total, 39452 byte(s) of still-reachable allocation(s)

Dr,2020-04-14.M (re-run with "-show_reachable" for details)

Dr,2020-04-14.M Details: K:\invoker-prod\work\codeforces6\60c583d1d5042c09b8b90fe60fe5fe0b\check-acfb434e06065bfe7c8a7fcb2d8ca975\run\DrMemory-program.exe.3432.000\results.txt

Dr,2020-04-14.M WARNING: application exited with abnormal code 0x3

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

Can someone recommend problems similar to F?

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

    This idea of the graph looking like cycles and ordered trees going into cycles is also found in this problem — Scheme

»
4 years 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 years 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 years 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 years ago, # |
  Vote: I like it +1 Vote: I do not like it

That solution to D. OMG.

»
4 years ago, # |
  Vote: I like it +5 Vote: I do not like it
  • »
    »
    4 years 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 years 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 years 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 years 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 years 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 years 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 years 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 years 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 years 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 years 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 years 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 years 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 years 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 years 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 years 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 years 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 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

    • »
      »
      »
      4 years 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 years 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 years 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 years 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 years 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 years 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 years 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 years 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 years 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 years 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 years 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 years 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 years 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 years 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 years 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 years 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.

    • »
      »
      »
      4 years 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 years 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 years 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 years 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 years 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 years 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 years 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 years 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 years 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 years 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 years 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 years 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 years 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 years 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 years 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 years 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 years 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 years 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 years 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 years ago, # ^ |
                Vote: I like it 0 Vote: I do not like it

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

              • »
                »
                »
                »
                »
                »
                »
                »
                4 years 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 years ago, # ^ |
                    Vote: I like it +1 Vote: I do not like it

                  Got it completely. Thank you so much.

»
4 years 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 years 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 years 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 years 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 years 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 years 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 years 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 years 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 years 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 years 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 years 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 years 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 years 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 years 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 years 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 years ago, # |
  Vote: I like it +2 Vote: I do not like it

Can somebody please explain the solution of problem E

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

Please explain E1/E2 i could not understand editorial.

  • »
    »
    4 years 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 years 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 years 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 years 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 years 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 years 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 years 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 years 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 years 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 years 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

      • »
        »
        »
        »
        4 years 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 years 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 years 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 years 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 years 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.

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

      Can you elaborate on your approach? It seems interesting

      • »
        »
        »
        »
        4 years 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 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          No not yet

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

            There are finite no of cells available. Thus, for any cell, robot starting at that cell will end up in a closed loop after some time.

            The matrix can be broken down into components, with each component having cells which end up in the same closed loop.

            For a component, there is one closed loop and some chains of cells leading into it. The maximum no of blocks that can be occupied for a component is equal to no of cells that part of the loop.

            In order to maximize robots occupying black cells, we classify cells such that any two cells which cannot have robots placed on them simultaneously (because they will overlap in future) are assigned equal ids. Again, no of ids assigned = no of blocks part of the loop.

            For every class, we take one cell (preferably black). Thus we get max no of black cells that can be occupied at the beginning.

»
4 years 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 years 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.

»
4 years 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

»
4 years 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...

»
4 years 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)).

»
4 years 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='')
  • »
    »
    4 years 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.;)

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

is there any video solution for problem E?

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

here is my approach for solving E2 in 200*n*log(n). 95645153; not so hard to understand.

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

In problem F, we don't even need to do binary lifting . We just need to check where will a robot be after pow(2,ceil(log2(n*m))) because it is guaranteed that after this many number of moves any robot is bound to enter into a cycle.

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

On the problem E2, consider the following example :

12 1 1 2 2 2 1 1 2 1 1 1 1 I run author's code that shows the answer is 9 here. But can't we take this subsequence : 1 1 2 2 2 1 1 1 1 1 1, so that the resulting answer is 11?

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

O(200N) complexity gives tle for E2 ??

229116617

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

    Please don't necropost. I can see the downvotes coming to both your and my comment.

    according to

    Editorial

    The problem with your code is either the implementation or Java is slow.

    btw is it rated?

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

n%2==0 c=n/2-1; n%2==1 c=n/2; printf("%d\n",c);