### vovuh's blog

By vovuh, history, 12 months ago,

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

• +115

 » 12 months ago, # |   +32 That anti-sudoku approach is the coolest approach ever possible!!
•  » » 12 months ago, # ^ |   0 Its just awesome!!
•  » » 12 months ago, # ^ |   0 I have done that in contest! :D
•  » » » 12 months ago, # ^ |   0 can you remember where would you have done that earlier
•  » » 12 months ago, # ^ |   +11 After reading the solution, I feel very stupid now. Wasted more than 1 hour for this problem. :(
•  » » 12 months ago, # ^ |   -11 O(n*200) = O(n) approach for E-1/E-2 this code
•  » » 6 weeks ago, # ^ |   0 Another approach for D 109670932
 » 12 months ago, # |   -23 I like Problem D, it's really interesting.
•  » » 12 months ago, # ^ |   -13 Idea is good, but problem is obvious.
•  » » » 12 months ago, # ^ |   -16 Maybe.
•  » » » » 12 months ago, # ^ |   -9 How to solve problem A ?
•  » » » » » 12 months ago, # ^ |   -11 that's simple, you've to output (n-1)/2. you can see it on your own its obvious.
•  » » » » » 12 months ago, # ^ |   0 learn stars and bars algorithm it will help you even if there are more than 2 variable
•  » » 12 months ago, # ^ |   0 how to solve candies problem ?
•  » » » 12 months ago, # ^ |   0 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
 » 12 months ago, # |   0 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]; } } 
•  » » 12 months ago, # ^ |   0 check this: 78 39 26
•  » » 12 months ago, # ^ | ← Rev. 2 →   +5 In alphabet string, you have repeated 'g' twice, hence for test case 10 10 10 It fails.
•  » » » 12 months ago, # ^ |   +5 Accepted Thank you very much!
•  » » 12 months ago, # ^ | ← Rev. 4 →   0 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].
•  » » » 12 months ago, # ^ |   0 thanks, I get it.
•  » » 12 months ago, # ^ |   0 except the mistake of alphabet, this solution is wrong itself...
•  » » » 12 months ago, # ^ |   +1 I found this mistake, thanks, I'm really stupid:)
•  » » » 12 months ago, # ^ |   0 My fault, when a gets bigger, so does the step.
•  » » 12 months ago, # ^ |   0 take input char str[1000000]='abcdefghijklmnjklmnopqrstuvwxyz' and yes u repeat g twice
•  » » » 12 months ago, # ^ |   0 thank you！
 » 12 months ago, # |   0 Can someone please help me with my submission for problem C? Here is the link: 76600537
•  » » 12 months ago, # ^ |   -6 Cannot seem to find any test which fails and please learn macros.
•  » » » 12 months ago, # ^ |   0 Sure!
•  » » 12 months ago, # ^ |   0 Check this:121 1
•  » » » 12 months ago, # ^ |   0 Thank you!
•  » » 12 months ago, # ^ |   0 61 1 1 2 2 2actual answer = 2your answer = 1
•  » » » 12 months ago, # ^ |   0 Thank you!
 » 12 months ago, # |   -7 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.
 » 12 months ago, # | ← Rev. 2 →   0 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 using namespace std ; map m ; map::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 — 1 ; else ans = min(mx, s) ; cout << ans << "\n" ; t-- ; } return 0 ; } 
•  » » 12 months ago, # ^ | ← Rev. 3 →   0 You need clear your map at the starting of each test case using m.clear() I submitted your code 76658706
•  » » » 12 months ago, # ^ | ← Rev. 2 →   0 It still shows the same problem, moreover I think will be better to put map m ; map::iterator itr; inside the while loop to avoid using clear()
•  » » » 12 months ago, # ^ |   0 What is the logic behind this approach?? And why s==mx gives ans as mx-1?? Plz help me out
•  » » » » 12 months ago, # ^ | ← Rev. 2 →   0 consider the case171 1 1 1 2 3 4here s = mx = 4if 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
•  » » » » » 12 months ago, # ^ |   0 Thank you very much!!
 » 12 months ago, # |   0 For the B question, just repeat the distinct characters one after another n times. #include 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 b-1) cnt=0; } cout<
 » 12 months ago, # | ← Rev. 2 →   0 Anti Soduko solution is damn cool..
 » 12 months ago, # |   0 Thank you vovuh.Great contest.This contest motivated me a lot.
•  » » 12 months ago, # ^ |   0 lol. then give div 2.
 » 12 months ago, # | ← Rev. 2 →   0 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
•  » » 12 months ago, # ^ |   +4 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)
•  » » » 12 months ago, # ^ |   -7 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.
•  » » » » 12 months ago, # ^ |   +12 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).
•  » » » » » 12 months ago, # ^ |   -8 I got it! The total number of all vector v is not nk but n. So the time complexity is O(nk) .Thanks bro!
•  » » » » » 12 months ago, # ^ |   0 I had the same doubt. Thanks for the explanation!
•  » » » » » 12 months ago, # ^ |   0 thank you
•  » » 12 months ago, # ^ |   +4 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.
•  » » » 12 months ago, # ^ | ← Rev. 2 →   -8 I think I have figured out how it works. Thanks bro.
 » 12 months ago, # |   0 How i can solve (problem E) by dynamic programming
 » 12 months ago, # |   0 why the C problem can do that,can you explain?
•  » » 12 months ago, # ^ | ← Rev. 2 →   0 Analyse these 3 cases.41 1 2 351 1 1 2 341 1 1 3You will be able to get yourself now.
•  » » » 12 months ago, # ^ |   0 ok，thanks very much.
 » 12 months ago, # |   0 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.
 » 12 months ago, # |   +7 Problem E2 is very nice. What is the Mo's algorithm approach?
•  » » 12 months ago, # ^ |   +4 E2 was super nice and it fooled me.
•  » » 12 months ago, # ^ |   +6 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
•  » » » 12 months ago, # ^ |   0 Oh, I see it now. Thanks!
•  » » » 12 months ago, # ^ |   -6 There would be approx n^2 ranges....how can I do it with Mo's algo
•  » » » » 12 months ago, # ^ |   -9 I have same doubt, Can someone please explain this in detail?
•  » » » » » 12 months ago, # ^ |   +5 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.
•  » » » » 12 months ago, # ^ |   0 same doubt ..have u got the answer ?? if u got then plz explain
•  » » » » » 12 months ago, # ^ |   0 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
•  » » » » 12 months ago, # ^ |   +4 It is mentioned in the editorial that there are O(n) segments only.
 » 12 months ago, # |   0 Is there any reason why system testing has been really slow for the past few contests?
•  » » 12 months ago, # ^ |   0 Probably reason is increasing number of people take part in the contests.
 » 12 months ago, # |   0 Why D Anti-Suduko in giving wrong if we replace any number in a row and only giving right if we replace one ?
•  » » 12 months ago, # ^ | ← Rev. 2 →   0 For every row, column and block, the nine numbers shouldn't be distinct.
•  » » » 12 months ago, # ^ |   0 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.
•  » » » » 12 months ago, # ^ |   0 What about the blocks?
•  » » » » » 12 months ago, # ^ |   0 how is changing all 1's to 2's handling the blocks ?
•  » » » » » » 12 months ago, # ^ |   0 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.
•  » » » » » » » 12 months ago, # ^ |   0 I got it. Thank a lot!
•  » » » » » » 12 months ago, # ^ |   0 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.
•  » » » » » » » 12 months ago, # ^ |   0 Thank you for the detailed explanation.
 » 12 months ago, # |   0 In the second question, My solution was not acceptedHere is my code 76582843I 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..
•  » » 12 months ago, # ^ |   0 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.
•  » » » 12 months ago, # ^ |   0 Thanks a lot !!
 » 12 months ago, # |   0 Can someone share the Mo's algorithm approach for problem E2 ? Thanks in advance.
 » 12 months ago, # |   0 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); }
•  » » 12 months ago, # ^ |   0 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.
•  » » » 12 months ago, # ^ |   0 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.
•  » » » » 12 months ago, # ^ |   +3 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.
 » 12 months ago, # | ← Rev. 2 →   -8 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
•  » » 12 months ago, # ^ |   0 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.
•  » » » 12 months ago, # ^ |   0 yeah sorry i didn't read the question correctly. my bad due to it i got wa
 » 12 months ago, # |   0 What does AL denote in the time complexity of Problem E2?
•  » » 12 months ago, # ^ |   0 The alphabet size which is 26 for E1 and 200 for E2.
 » 12 months ago, # |   0 In problem F solution, what fans & sans array meant for?
 » 12 months ago, # |   +16 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).
•  » » 12 months ago, # ^ |   +3 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.
•  » » 12 months ago, # ^ |   0 You should apply multi-sourced bfs instead of dfs to assign the numbers.
•  » » 12 months ago, # ^ |   0 Yes its correct, can you please share your code? then probable i can help you solving your problem.
•  » » » » 12 months ago, # ^ |   0 I forgot to update. I had corrected my code. There was a small implementation mistake. Thanks for reaching out though.
•  » » » » » 12 months ago, # ^ |   0 Can you please Explain your approach to part 2 more clearly !!!
•  » » » » » » 12 months ago, # ^ | ← Rev. 2 →   +3 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 : $u$ and $v$ are in the same component. $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.
 » 12 months ago, # | ← Rev. 2 →   +3 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?
•  » » 12 months ago, # ^ |   +4 You can. It's just random.
•  » » 12 months ago, # ^ |   0 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
 » 12 months ago, # |   +3 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
•  » » 12 months ago, # ^ |   0 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 correctNow 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 answerThis is my submission for python 3 : 76678117
•  » » » 12 months ago, # ^ |   0 Hi Yash,Thanks a lot for making it simple. :)
•  » » » » 12 months ago, # ^ |   0 I was afraid that I may have made it complex but works for you...Well wish you great codeforces journey! :)
•  » » » » » 12 months ago, # ^ |   0 No :PI 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
•  » » » » » » 12 months ago, # ^ |   0 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.
•  » » » » » » » 12 months ago, # ^ |   0 Okay, Yash. Thanks for sharing your part.
 » 12 months ago, # | ← Rev. 3 →   +6 Editorial of problem F is awesome!!
•  » » 12 months ago, # ^ | ← Rev. 2 →   0 I didn't get it. could you explain with more details?
 » 12 months ago, # |   +3 How to solve E1 with Top down dp?
 » 12 months ago, # | ← Rev. 3 →   0 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/76633420Diagnostics 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::allocator > >; }~.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
 » 12 months ago, # |   0 Can someone recommend problems similar to F?
•  » » 5 months ago, # ^ |   0 This idea of the graph looking like cycles and ordered trees going into cycles is also found in this problem — Scheme
 » 12 months ago, # |   +17 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.
 » 12 months ago, # |   +2 I liked the way the 2D matrix is stored in the fastest solution of F.
 » 12 months ago, # | ← Rev. 3 →   -19 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!//# includeusing 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 m; int huge = 0; for(int i=0; i> 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'; }}
•  » » 12 months ago, # ^ |   0 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
•  » » » 12 months ago, # ^ |   0 yes! :D but still people downvoted! -_- :D
 » 12 months ago, # | ← Rev. 2 →   0 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 ?
 » 12 months ago, # |   +1 That solution to D. OMG.
 » 12 months ago, # |   +5 E2 using Mo s algorithm https://codeforces.com/contest/1335/submission/76679523
•  » » 12 months ago, # ^ | ← Rev. 2 →   0 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
•  » » » 12 months ago, # ^ |   +1 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 examplearr=[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")
•  » » » » 12 months ago, # ^ |   0 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
•  » » » » » 12 months ago, # ^ |   0 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))
•  » » » » » » 12 months ago, # ^ |   0 thanks a lot ... i misunderstood my complexity and thought it to be nk2 .. it is just n*k thanks a lot dear
•  » » » » » » 12 months ago, # ^ |   0 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.
•  » » » » 12 months ago, # ^ |   0 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.
•  » » » » » 12 months ago, # ^ |   0 yes u are right,for this question prefix sum approach is better because of additional constraint on count of distinct elements.
 » 12 months ago, # |   +6 can anyone tell me whats going wrong with the code.https://codeforces.com/contest/1335/submission/76681472
 » 12 months ago, # | ← Rev. 3 →   +4 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?
 » 12 months ago, # |   0 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?
 » 12 months ago, # |   0 Can anyone explain why this O(n) solution of Problem C was giving me TLE? https://codeforces.com/contest/1335/submission/76571599
•  » » 12 months ago, # ^ |   0 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
•  » » » 12 months ago, # ^ |   0 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?
•  » » » » 12 months ago, # ^ |   0 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.
•  » » » » » 12 months ago, # ^ |   0 Oww. Thank you. I understand now.
 » 12 months ago, # |   0 can anyone explain problem E?.it's really seem hard to me.
 » 12 months ago, # |   0 Why on Earth is K = 24 in the last code listing?
 » 12 months ago, # |   +3 Can Anyone please tell me why the complexity of E2 described above is n.AL ? I think it should be N*(AL^2).
 » 12 months ago, # |   0 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
•  » » 12 months ago, # ^ |   0 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.
•  » » » 12 months ago, # ^ |   0 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.
 » 12 months ago, # |   0 plz tell how to solve problem e1 with explanation
 » 12 months ago, # |   0 Can someone help me debug my solution for E1 https://codeforces.com/contest/1335/submission/76608293
 » 12 months ago, # |   0 when the ratings of this contest will be updated??
 » 12 months ago, # |   0 If anyone know the O(nlogn) soln for E2, please post.
 » 12 months ago, # |   0 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.
•  » » 12 months ago, # ^ |   0 You need to work on your basic class 10th math then
•  » » 12 months ago, # ^ |   0
 » 12 months ago, # | ← Rev. 2 →   -8 I am getting TLE on Problem C on test #2. Not able figure out the case. #include 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 count(200010,0); for(int i=0;i>val; if(count[val] == 0) distinct++; count[val]++; max_same = max(count[val] , max_same); } (max_same == distinct) ? cout<
 » 12 months ago, # |   0 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)?
•  » » 12 months ago, # ^ |   0 you defined int as ll isn't necessary in this case.
•  » » » 12 months ago, # ^ |   0 Using ll instead of int gave me problems for the first time. Thanks for the help!
 » 12 months ago, # |   -8 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.
•  » » 12 months ago, # ^ |   -8 I understand now thanks to this comment section
 » 12 months ago, # |   0 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.
•  » » 12 months ago, # ^ |   0 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
•  » » 12 months ago, # ^ |   0 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.
•  » » » 12 months ago, # ^ |   0 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.
•  » » » » 12 months ago, # ^ |   0 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?
•  » » » » » 12 months ago, # ^ |   0 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.
 » 12 months ago, # |   0 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 using namespace std; int main(){ int loop,tem,col=0; string str; cin>>loop; for (int i =0;i>str; if (col != 8) col = col%8; tem = str[col]-'0'; tem = tem % 9 + 1; str[col] = tem+48; cout<
 » 12 months ago, # |   0 is there a simpler explanation for E ? :\>> i cant understand what c and Pref if about ![problem:E1]
•  » » 12 months ago, # ^ |   0 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)
•  » » » 12 months ago, # ^ |   0 Thanks . . I think i started to understand it better
 » 12 months ago, # |   0 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!
 » 12 months ago, # |   0 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/76685166I am having a wrong answer on test case 50 of the 2nd test file.
 » 12 months ago, # |   0 still I cant get the logic behind three block Palindrome please help me out.. thank you in advance
•  » » 12 months ago, # ^ | ← Rev. 2 →   0 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.
•  » » » 12 months ago, # ^ |   0 Thanks Bro
•  » » » 12 months ago, # ^ |   0 Hey man can you please explain how we select prefix or suffix of out sequence?
 » 12 months ago, # | ← Rev. 2 →   0 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 { } } 
 » 12 months ago, # |   0 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 )
 » 12 months ago, # |   0 Please can someone explain E1
 » 12 months ago, # |   0 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/76724438Thanks!!
 » 12 months ago, # |   0 I don't quite understand the explanation provided for B? Could someone please explain the reasoning provided in a bit more detail?
 » 12 months ago, # | ← Rev. 5 →   -7 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> map = new HashMap<>(); for(int i=0;i 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); } } }
»
12 months ago, # |
0

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

 » 12 months ago, # | ← Rev. 2 →   0 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?
•  » » 12 months ago, # ^ |   +1 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.
•  » » » 12 months ago, # ^ |   0 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.
•  » » » » 12 months ago, # ^ |   0 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.
•  » » » 9 months ago, # ^ |   0 DeadlyCritic I am also getting MLE on test case 9, even after defining int as ll. 88900051
 » 12 months ago, # |   0 please tell me how the answer for prob C testcase 2 1 5 4 3 is 1
•  » » 12 months ago, # ^ | ← Rev. 2 →   0 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).
•  » » » 12 months ago, # ^ |   0 so what will the teams look like in this case ? (1,2), (3,4) excluding 5?
•  » » » » 12 months ago, # ^ |   0 You mean 3 is equal to 4?, the second team should have $equal$ numbers.
•  » » » » » 12 months ago, # ^ | ← Rev. 2 →   0 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
•  » » » » » » 12 months ago, # ^ |   0 You must have 2 team not 4.
•  » » » » » » » 12 months ago, # ^ |   0 yes i corrected that
•  » » » » » 12 months ago, # ^ |   0 if x=1 for 2 1 5 4 3 , then how are the teams formed please tell me that
•  » » » » » » 12 months ago, # ^ |   0 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).
•  » » » » » » » 12 months ago, # ^ |   0 thanks mate . i did not realise excluding members is allowed.
 » 12 months ago, # |   +6 @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.
•  » » 12 months ago, # ^ |   +21 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.
 » 12 months ago, # |   +1 Isn't $O(n*200)$ memory too much for problem E2 since $n <= 2e5$?
•  » » 12 months ago, # ^ |   +3 Sum of n over all test cases does not exceed 2e5. So total iterations will be 200*2e5, wiz O(1e7), wiz O(n)
•  » » 12 months ago, # ^ |   +3 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$ :).
 » 12 months ago, # | ← Rev. 3 →   0 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 ??
•  » » 12 months ago, # ^ |   +1 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
•  » » » 12 months ago, # ^ |   0 Ok. But where has he defined the identifier _DEBUG in the source code? Then how the redirection will take place??
•  » » » » 12 months ago, # ^ |   0 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
•  » » » » » 12 months ago, # ^ |   0 If it's not getting executed then why even bother to put it?
•  » » » » » » 12 months ago, # ^ |   0 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.
•  » » » » » » » 12 months ago, # ^ |   0 Ok. So where would have the author placed the identifier DEBUG??
•  » » » » » » » » 12 months ago, # ^ |   0 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
•  » » » » » » » » » 12 months ago, # ^ |   +1 Got it completely. Thank you so much.
 » 12 months ago, # |   0 This is my solution to the fifth question : https://codeforces.com/contest/1335/submission/76728501Where is my mistake? I'm using dp
 » 12 months ago, # |   0 how for E O(n^2⋅AL) algorithm pass? n^2 means 10^10 operations. about 10^8 operations takes 1 sec I guess
•  » » 12 months ago, # ^ |   0 $O(n^2.AL)$ solution is for E1, for E2 you should solve it in $O(n.AL)$ and it's included in editorial.
•  » » » 12 months ago, # ^ |   0 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
•  » » » » 12 months ago, # ^ |   0 Yes you are right, it passes E1 but not E2, the editorial's solution for E1 only works for E1, not for E2.
•  » » » » » 12 months ago, # ^ |   0 why O(n2.AL) solution pass E1? that's what I am asking
•  » » » » » » 12 months ago, # ^ | ← Rev. 2 →   0 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.
•  » » » » » » » 12 months ago, # ^ |   0 ohk got that didn't saw it was 2000 not 20000. thanks
•  » » » » » » » 12 months ago, # ^ |   0 t is not included in finding order of algorithm? if t got included it will be like n^3 A as t=2000
•  » » » » » » » » 12 months ago, # ^ | ← Rev. 2 →   0 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)$.
•  » » » » » » » » » 12 months ago, # ^ |   0 ok thanks.
 » 12 months ago, # |   0 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.
•  » » 12 months ago, # ^ |   0 This is with regard to the palindrome blocks question.
•  » » 12 months ago, # ^ |   0 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.
 » 12 months ago, # |   +23 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.
 » 12 months ago, # | ← Rev. 2 →   -8 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
•  » » 12 months ago, # ^ |   0 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.
•  » » » 12 months ago, # ^ |   0 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 :).
 » 12 months ago, # |   0 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 234567891It gives the output:113456789 911345678 891134567 789113456 678911345 567891134 456789113 345678911 134567891Correct me if I am wrong.
 » 12 months ago, # |   0 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.
 » 12 months ago, # |   0 Cfn somebody explian why my E2 submission passed all the tests? It is really strange.
 » 12 months ago, # |   +2 Can somebody please explain the solution of problem E
 » 12 months ago, # |   -8 Please explain E1/E2 i could not understand editorial.
•  » » 12 months ago, # ^ | ← Rev. 2 →   0 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]
•  » » » 12 months ago, # ^ |   0 In problem E2 is not tutorial solution complexity is O(n*al^2)?
•  » » » » 12 months ago, # ^ |   +1 Amortised complexity of outer 2 loops will be O(n). So total complexity will be O(n*200)
•  » » » » » 12 months ago, # ^ |   0 Thanks.Got it.
 » 12 months ago, # |   -8 If someone wants to see a small and simple implementation of F : https://codeforces.com/contest/1335/submission/77002174
•  » » 12 months ago, # ^ |   0 Please explain what you are doing in your solution.Thanks in advance
 » 12 months ago, # | ← Rev. 3 →   0 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
 » 12 months ago, # |   0 Anti-Sudoku problem broadens our perspective towards tricky problems and was really interesting and amazing!!!....Thank You @vovuh
 » 12 months ago, # |   -8 F:I cant understand "if ((nm >> deg) & 1) " please tell me why thx
 » 12 months ago, # |   0 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.
 » 12 months ago, # |   0 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.
 » 12 months ago, # |   0 How to avoid MLE on F, I keep getting MLE on test 5: https://codeforces.com/contest/1335/submission/77190353
 » 12 months ago, # |   0 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) 
 » 12 months ago, # |   0 in 1335C someone please explain me the count function, what is that 0 doing as parameter?
 » 12 months ago, # |   0 I am new to dynamic Programming, can someone please explain the problem E1. Thanks in advance :)
 » 12 months ago, # |   0 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.
 » 12 months ago, # | ← Rev. 3 →   0 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]?
•  » » 12 months ago, # ^ |   0 I already understood.
 » 12 months ago, # | ← Rev. 2 →   0 https://codeforces.com/contest/1335/submission/77449681 a general solution to the D problem using a simple math observation .
 » 12 months ago, # |   0 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
 » 12 months ago, # |   0 int anti-sudoku problem, I am changing diagonal elements to 9(if initially not 9) else changing to 1(initially 9). Getting WA.
•  » » 12 months ago, # ^ |   0 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.
•  » » » 12 months ago, # ^ |   0 it will, because diagonal elements will get repeated number, either 9 or 1 9 8 9 1 9 3 4 6 9
•  » » » » 12 months ago, # ^ |   0 blinksHow 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.
 » 12 months ago, # |   0 Why is the problem C tagged with Binary Search? How can it be solved using Binary Search?
 » 12 months ago, # |   0 In problem E2 is not tutorial solution complexity is O(n*al^2)?
 » 12 months ago, # |   0 If anyone is interested in E2 Here is explanation with example and code
 » 12 months ago, # |   0 I'm getting memory limit exceeded in test case 5 for F. Submission: 77895714The 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.
•  » » 12 months ago, # ^ | ← Rev. 2 →   0 Problem solved. DFS used led to stack over flow. However, BFS did not cause this problem.
•  » » » 10 months ago, # ^ |   0 Can you elaborate on your approach? It seems interesting
•  » » » » 10 months ago, # ^ |   0 It has been long since this comment was made. I have looked at it now only. Have you figured it out by now?
•  » » » » » 8 months ago, # ^ |   0 No not yet
•  » » » » » » 8 months ago, # ^ |   0 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.
 » 12 months ago, # | ← Rev. 4 →   0 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]);
»
12 months ago, # |
0

# 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

•  » » 12 months ago, # ^ |   0 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
•  » » » 12 months ago, # ^ |   0 thank you, what you suggest i did and it worked.
 » 12 months ago, # |   0 Can someone explain me that how can we do E1/E2 using Mo's algorithm??
 » 12 months ago, # |   0 How to solve Problem C using binary search?
 » 11 months ago, # |   0 PROBLEM — E1test case : — (1,1,3,1,5) shouldn't answer be (1,1,3,1) so length = 4 but judge gives answer as 3please help
•  » » 10 months ago, # ^ |   0 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
 » 11 months ago, # |   0 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...
 » 11 months ago, # |   0 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)).
 » 10 months ago, # |   0 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='') 
•  » » 10 months ago, # ^ |   0 Your code will work for just 1 test case. But there can be multiple test cases.;)
•  » » » 10 months ago, # ^ |   0 yea got it & fixed it , tnx btw
 » 10 months ago, # |   0 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<
 » 10 months ago, # |   0 is there any video solution for problem E?
 » 10 months ago, # |   0 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
 » 9 months ago, # |   0 easiest D....:)
 » 8 months ago, # |   0 Its pretty nice set of questions for a beginner!
 » 6 months ago, # |   0 here is my approach for solving E2 in 200*n*log(n). 95645153; not so hard to understand.
 » 6 months ago, # |   0 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.
•  » » 5 months ago, # ^ |   0 Can you share the proof ?
 » 6 months ago, # |   0 Why do we use * before function in c++? ex:- ll mx = *max_element(cnt.begin(), cnt.end());
•  » » 2 months ago, # ^ |   0 The max_element() function returns the pointer to the maximum element. In order to get the actual element, we have to dereference it using *(dereferencing operator).
•  » » » 2 months ago, # ^ |   0 thanks, I got that already.
 » 4 months ago, # |   0 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?
•  » » 3 months ago, # ^ |   0 Read the problem carefully!
 » 2 months ago, # |   0 For problem E2 (Three Block Palindrome — Hard Version) why is the time complexity of the solution O(n * A) and not O(n * A2) ?