### vovuh's blog

By vovuh, history, 4 years ago, translation,

977A - Wrong Subtraction

Tutorial
Solution (Vovuh)

977B - Two-gram

Tutorial
Solution (Vovuh)

977C - Less or Equal

Tutorial
Solution (Vovuh)

977D - Divide by three, multiply by two

Tutorial
Solution (eddy1021)

977E - Cyclic Components

Tutorial
Solution (Vovuh)

977F - Consecutive Subsequence

Tutorial
Solution (Vovuh)

• +54

 » 4 years ago, # |   0 Can someone tell me why my submission for C got TLE? I only used a sort and some if statements.http://codeforces.com/contest/977/submission/37947136
•  » » 4 years ago, # ^ |   +19 6-th test is anti-qsort test especially for Java solutions. Replace int with Integer and it will be ok.
•  » » » 4 years ago, # ^ |   0 Why didn't you prepare such tests for manually-written quicksort? I had to do it.
•  » » » 4 years ago, # ^ | ← Rev. 2 →   0 .
•  » » » » 4 years ago, # ^ | ← Rev. 3 →   +16 Many solutions to F got hacked because unordered_map's insert is O(n) in the worst case, turning the whole solution to O(n^2) for some inputs. I lost my #1 spot because of this.I certainly wish the pretests had included a test case for this like they did for the Java issue. But then there would be little point in having a 12 hour hacking session with div 1 people participating, would there?When standard libraries contain such terrible implementations, the best thing is to do is educating people about them and teaching safe alternatives. Allowing an O(n^2) solution to pass because "the bug wasn't in my code, it was in the library" would be silly.
•  » » » » » 2 years ago, # ^ |   0 Thank you for enlightening! :) I'm practicing the same question, got a TLE on #36 due to usage of unordered_map
•  » » » » » 2 years ago, # ^ |   0 It helped!! I attempted this one and got tle on test 36
•  » » » 4 years ago, # ^ |   0 Man I've been in this for years and didn't know Java's sort was bad. I feel like a noob. My solution wasn't passing and this was why.
•  » » 4 years ago, # ^ |   0 I think it's because Arrays.sort() on primitives uses quicksort which is n^2 in worst case. I changed mine from Arrays.sort() to Collections.sort() which uses nlogn mergesort and it passed.
•  » » 4 years ago, # ^ |   0 May be because of Scanner. Scanner isn't the best solution in sport programming. It isn't as fast as DataInputStream (if i haven't made a mistake).
•  » » 4 years ago, # ^ |   0 use shuffle method before sorting. Arrays.sort uses quick sort it's complexity is O(nlog(n)) and at worst case O(n^2).quick sort runs in O(n^2) when array is partially sorted.so shuffle before sorting avoid O(n^2).
•  » » 4 years ago, # ^ |   0 Crazy, did exactly the same in JAVA 8, got a wrong answer on test case 16 http://codeforces.com/contest/977/submission/38608606
•  » » » 4 years ago, # ^ |   0 Not crazy if you know the difference between equals and ==
•  » » » » 4 years ago, # ^ |   0 Damned... Thanks
 » 4 years ago, # |   +36 Thanks for the contest!!!, it was a great contest to learn!!!
 » 4 years ago, # | ← Rev. 2 →   +7 Nice problem 977D - Divide by three, multiply by two, my solution 37939642 runs in O(n2). I make the graph and then run topological order.
•  » » 4 years ago, # ^ |   0 I did the same!
•  » » 4 years ago, # ^ |   0
•  » » 4 years ago, # ^ |   0 Can You Explain Your Approach
•  » » » 4 years ago, # ^ | ← Rev. 7 →   +3 I made the graph in this way:-> all positions of the array are the nodes in G.-> given two nodes v and w in G, if 2·array[v] = array[w] or array[v] = 3·array[w] then the edge exists. Check the same in the other way (). You may note that if then doesn't exist and viceversa.Note that at this point you have a DAG, just run a topological order and suppose it is in the array order[], just print the items in this way: from i = 0 to n - 1: print array[ order[ i ] ] 
•  » » » » 4 years ago, # ^ |   +1 I think graph will just be a linear chain, We just have to find the starting point and print while traversing.
•  » » » » » 4 years ago, # ^ |   0 That does the topological order. It runs in O(n).
•  » » » » » » 4 years ago, # ^ |   +1 Yes , so we don't even need top sort. We can find a node with 0 in degree.
•  » » » » » » » 4 years ago, # ^ |   +5 you are right, the problem guaranteed a solution exists, so the graph has to be a chain. And if the problem didn't guarantee the solution then we would just need to check if the graph is a chain or not :)
•  » » » » » » 4 years ago, # ^ |   0 I did the problem using backtracking. (check if 2*curr or curr/3 exists in set or not, and then proceed, otherwise, return). Below is my solution. 977DI was wondering whether this approach would give TLE if the constraints had been large, like n~10^5. Please let me know your thoughts
•  » » » » » » » 4 years ago, # ^ | ← Rev. 2 →   0 For the explanation of the backtracking solution see my teammate's comment Devil and for the explaining of my solution see my previous comment. Note that there exists a solution better than mine, it runs in , it's just that my solution was the solution I think faster and it runs in time. For any specific doubt just ask it.
•  » » » » » » » 4 years ago, # ^ |   0 Your code won't work when elements repeat. For example, 4 6 6 2 2.
•  » » » » » » » » 4 years ago, # ^ |   0 There are no testcases in which elements repeat.
•  » » » » » » » » » 3 years ago, # ^ |   0 If the elements are repeated then the solution would not be possible as you cannot get the same number anyhow by multiplying by 2 or dividing 3 .Its stated in the question that a solution exists .
•  » » 4 years ago, # ^ |   0 I did almost same My algo was n*(n+m)
•  » » 4 years ago, # ^ | ← Rev. 2 →   +1 .
•  » » » 4 years ago, # ^ |   +1 Yup, For Explanation: http://codeforces.com/blog/aMitkvikram
•  » » 4 years ago, # ^ |   0 Because there are at most 2 edges of 1 vertex. So you can run the topological order in O(n). Just like this: link
 » 4 years ago, # |   0 I tried this for problem D.Take a boolean array check[n] and mark all as false. Then I tried making chains. Take the first element from array given that is false and mark it as true and this will start a new chain. Then for each other false element in array check if it can be added to the chain started by this element, either by appending it to the beginning or to the end. If yes mark this as true too. For beginning, check if the new element divided by 3 is equal to first element in chain or if new element multiplied by 2 is equal to first element in the chain. Similarly we do for the end.However, I couldn't figure out how to decide a way to print all these chains in a valid manner. Is there any way to do figure this part out.
•  » » 4 years ago, # ^ |   +1 You may try using double ended queue (deque in C++) to store the chain itself:When you decide to make a new chain starting at some element x create new deque and put your x into it.Methods push_front, pop_front, push_back, pop_back allow you to append and remove elements to your current chain from the beginning and from the end in O(1).When the chain is completely formed you may iterate through deque (or simply use pop_front until it will become empty) to get elements of your chain in the order you put them into.
 » 4 years ago, # |   +20 I had a lot of fun while I participate in this contest. Thanks!
 » 4 years ago, # | ← Rev. 2 →   +1 recently learn recursive backtracking and apply it to problem D, got AC :D
•  » » 4 years ago, # ^ |   +3 That's what I did too, seems like many people did it another way though lol. It was a nice problem.
•  » » 4 years ago, # ^ |   0 backtracking is the first approach I think in problem D and It is accepted :v I also recently learn recursive backtracking =)))
•  » » 4 years ago, # ^ |   0 Can you please make the submission public or give me your solution through external link? I would like to see your backtracking approach. :)
•  » » » 4 years ago, # ^ |   0
•  » » » » 4 years ago, # ^ |   0 Here's mine, it is in Java though :)
 » 4 years ago, # |   +9 977C - Less or Equal: Another approach towards solving it can be by using Binary Search on the number x.
 » 4 years ago, # |   0 For C, if k == 0 and v[0] = 1, according to the tutorial/solution you would print 0. Shouldn't you print -1? As we have x in [1;109] or -1.
•  » » 4 years ago, # ^ | ← Rev. 2 →   0 .
•  » » » 4 years ago, # ^ | ← Rev. 2 →   0 if k == 0 and v[0] == 1 (after sorting), there is no x in [1,10^9], in which case the problem says that "-1" should be printed. But like DeadlyTreap replied below me, this case is also accounted for, I just misread the tutorial.
•  » » 4 years ago, # ^ |   +1 in that case IF condition (!(1 <= ans && ans <= 1000 * 1000 * 1000)) will be TRUE and hence output will be "-1".
•  » » » 4 years ago, # ^ |   0 You're right! I misread the tutorial.
 » 4 years ago, # |   +11 Another solution for D:There can't be (x, 2*x, x/3) in the same array (x is multiple of 3) ... so for each number x, if it's not multiple of 3 you just go to 2*x, otherwise there's either 2*x or x/3 you can go to.iterate over all numbers to start the chain with and check whether the chain exist.
•  » » 4 years ago, # ^ |   +23 You can find the first element x of the chain by checking that neither 3*x nor x/2 exists in the array. Using a hash table this leads to an O(n) solution.
•  » » » 4 years ago, # ^ |   +1 Yes, you're right I didn't thought about. Thanks!
•  » » » 4 years ago, # ^ |   0 Don't hash tables take O(log n) time to access ?
•  » » » » 4 years ago, # ^ |   0 No their O(n) but average O(1)
•  » » 2 years ago, # ^ |   -8 **There can't be (x, 2*x, x/3) in the same array (x is multiple of 3) ** Can you please explain why is this true?
•  » » » 2 years ago, # ^ |   0 U can't possibly change the no. from x to 2*x and then to x/3 or x->x/3->2*x or x/3->2*x->x or whatever!:-)
•  » » » » 2 years ago, # ^ |   0 Yeah, you are right. Thank you!
 » 4 years ago, # |   +3 Can someone hack this, or is it correct?
•  » » 4 years ago, # ^ |   +4 This is correct, maybe you expected TLE, but (x, 2*x, x/3) can't be in the array at the same time then, suppose you know the first element of the solution only one of 2*x and x/3 are in the array so it is O(n) after found the first element and the number of starts is N all the elements of array so this solution run in O(N^2)
 » 4 years ago, # |   0 For problem D you can view the problem as a directed graph where x maps to x*2 and x/3 if x|3.Start point has indegree of 0.Ignoring "extra" numbers in your dfs (i.e number not in your array) a dfs from the startpoint will always find a chain (guaranteed to exist) that is your answer.void dfs(ll cur) { if (s[cur*2]) dfs(cur*2); if (cur%3==0 && s[cur/3]) dfs(cur/3); ans.push_back(cur); }(you have to reverse ans)
 » 4 years ago, # |   0 Here's my solution to D, a little different aproach: Sort the array, and then group up all numbers that goes with sequence like x,2*x,4*x,8*x until there is numbers that can go in that sequence (for example 4 8 6 3 12 9 has 4,8;3,6,12;9 — 3 sequences) I used map to store that. Then, simply try to merge them one by one, and see what sequence can merge with another sequence. Here's my submission for this problem
•  » » 4 years ago, # ^ |   0 This approach is quite complicated. I'm struggling with the variable names. Can you explain how you merge ?
•  » » » 4 years ago, # ^ | ← Rev. 2 →   +1 Well, first sort them. Sorting is important because i will go from smallest to biggest element and do this approach:If I checked that number, then you don't do anything, but if I didn't went for that number (let's say d[i]), then I will put in map.push_back(d[i],2*d[i],4*d[i]) — as long as there are numbers 2*d[i] or 4*d[i]. example: 3 4 6 8 9 12 in map<3,vector> push back 3,6,12. then I go to 4 and map<4,vector> push back 4,8. Then I go to 6, but it belongs to map<3,vector> so I don't do nothing. Again, I don't do anything with 8 and 12, but I didn't checked 9, so map<9,vector> push_back 9After that I have 3 maps:map<3,vector> (3,6,12)map<4,vector> (4,8)map<9,vector> (9)Then I iterate trough map, find for every one of them last number in vector (let's say that number is x) and see if there is map. If there is, then merge it until there is no such map. Merging is done in if (x%3==0 and m[x/3].size()>0) statement.after you done with merging that map, repeat the process until you iterate all elements in map. Because answer always exists, there will be for sure one map that has size n. Just print it. I hope I made it a bit clearer, I know it's complicated I struggled with it a lot :D
•  » » » » 4 years ago, # ^ |   0 Oh Good job ! I understood it now. Please don't name your variables haha. It's difficult for others to understand. Actuallly, it can be much simpler. Every number x can have only one successor. Either 2x or x/3. An array can't have both 2x and x/3 because if you reach 2x you can never reach x/3So the sequence starting from each A[i] is unique. Now, all that's left to do is find the first element and find the sequence starting from there. This first element is an x, such that x/2 and 3x are not present in the array. I wrote about my solution here. :)
•  » » » » » 4 years ago, # ^ |   +3 Yes, it's much simpler, but I didn't thought about it when there waa competition. :)
 » 4 years ago, # |   0 hi guys , can someone explain probleme c tutorial pls? i did solved but i didn't understand the solution
•  » » 4 years ago, # ^ | ← Rev. 6 →   0 Do you try to approach this problem with binary search ? If not so you should do it by binary search since its kinda help you to understand the solution. Here is my approach to problem C with bns. First binary search a value x from 1->1e9 (boundery) We can check how many number are <= x with a simple for loop suppose this number cnt If cnt < k then l = mid + 1. if cnt == k then this is our desire answer. If cnt > k r = mid-1; (l,r here is the left and right boundery, initially l = 1, r = 1e9) So if understand this approach you will notice that the value that satisfy the problem is between some elements in the sorted array (i did some debugging order to realize this). And to be specific its the number in the solution above (between ans[k-1] and ans[k] — 1 i think!). The fun part about binary search solution is that you dont have to worry about some corner case! Hope this help
•  » » » 4 years ago, # ^ |   0 thank you for your help
 » 4 years ago, # |   0 Can someone explain me the editorial solution for D?
•  » » 4 years ago, # ^ |   0 Yes, Only a number with more powers of 3 can come early in sequence than the lower power of 3. If two numbers have same powers of 3, then we can only jump from a lower number to higher number. So, Sort the given sequence in such manner.
•  » » » 4 years ago, # ^ |   0 why is that so? 9 3 6 12 24 should be a valid sequence, right?
•  » » » » 4 years ago, # ^ |   0 Yes , it is.
 » 4 years ago, # |   0 Maybe I'm missing something simple in 977C, but if k == 0 why are we looking for a[0] — 1?
•  » » 4 years ago, # ^ |   0 because we need to find a number in [1-10^9]. so suppose we have an array [34,54,65] with k==0, the answer would be anything in 1-33. Not exactly a0-1 but anything from 1-(a[0]-1) would do. Also, if a[0] == 1, then obv answer does not exist.
•  » » » 4 years ago, # ^ |   0 Perfect. Thanks for the explanation
•  » » » 4 years ago, # ^ |   0 Why we need cnt and for loop to check each number in C? After sort we already know that first k digit less or equal of a[k] only we should check if a[k + 1] not equal a[k]. (but this submission have a wrong answer on 6 test) Why?
•  » » » » 4 years ago, # ^ | ← Rev. 2 →   0 test 6 has k=0, there can be no number which has 0 numbers less than or equal to that number. has to be atleast one (considering that the first number is 1). I submitted it recently again with a much smaller code. 40080970
 » 4 years ago, # | ← Rev. 2 →   0 My solution to last problem got hacked (input resulted in TLE). After changing "unordered_map" to simply "map" it gets accepted. Why is it so? I know that "unordered_map" are generally less efficient for range iteration through a subset of their elements, but here random elements (having value one less than the current one) is being accessed.
•  » » 4 years ago, # ^ |   +1 The standard unordered_map has worst case O(n) for insertion, and the implementation is really really bad so this is actually easy to exploit in practice, turning the whole solution into O(n^2).See also my other comment which links to an old blog post.
•  » » » 4 years ago, # ^ |   +3 I really appreciate your reply. Thanks.
•  » » » » 4 years ago, # ^ |   0 I definitely understand why many of the top unofficial contestants used map instead of unordered_map. I'll do that in the future unless map is too slow.When you need unordered_map, you can make it harder to exploit by calling M.reserve(N + ::rand() % 10000) in the beginning. For this problem, even a simple M.reserve(N) is enough to defeat the specific test case that was used to hack.
 » 4 years ago, # |   0 Can someone tell me why my submission for F got WA?http://codeforces.com/contest/977/submission/37961004
•  » » 4 years ago, # ^ |   0 guys, i really dont understand why my approach is wrong. I just look for every element that wasn't used yet next element of the sequence in the array, using binary search, while it is possible. And then just check if this sequence has the biggest length. I would be glad, if you will say what bug my implentation has, or what mistake in my approach, or some testcase which i can check by myself.
 » 4 years ago, # |   +1 The editorial's for D is amazing!We can also prove that under the operation (x2 and /3) no number occurs more than once, and since the problem says that there's always a solution, we can be sure that every number has a degree of at most 2, so we can just find the head of this chain (which has no predecessor) and just iterate from it giving an O(nlogn) complexity.submission 37959164
•  » » 4 years ago, # ^ |   0 how can we say it cannot have duplicates? I used a set after contest and passed but it still doesn't feel right
•  » » » 4 years ago, # ^ |   0 If there is a pair that duplicate (have the same value) then you'd not be able to include it. Hence its will conflict with the problem statement. That how i understand
•  » » » 4 years ago, # ^ |   0 Well, imagine you had two numbers with the same value say X, multiplying by 2, and dividing by 3 are two independent operations, meaning you can't reverse them by using the other operation, hence you can't have the same numbers unless you can multiply by 1 which is not mentioned in the statement, since there's no operation that will keep X as is for two or more operations, we conclude that all number must be distinct.Simple check against that fact: add assertion to your code to check the validity of this.
•  » » » » 4 years ago, # ^ |   0 awesome. Thanks :)
 » 4 years ago, # |   0 In problem D, how can I prove that for the solution to exist the graph has to be a chain?
•  » » 4 years ago, # ^ |   0 If we could prove that every vertex has at most one child. For explanation please refer: 977D expanation.
•  » » 4 years ago, # ^ | ← Rev. 2 →   0 If it diverges it can't have an answer. This is because you can view the answer space as an infinite tree. This is because x/3 and x*2 cannot be reversed. (i.e there is no x*3 and x/2 operation)Problem guarantees answer.Therefore it cannot diverge.
 » 4 years ago, # |   +8 Can someone explain me why my submission for C got TLE after contest finished? Yesterday it got Accepted but today it shows TLE on XX test :/ I already fixed this small optimization bug on reading big arrays but still. Kinda unfair in my opinion.http://codeforces.com/contest/977/submission/37940448
 » 4 years ago, # | ← Rev. 2 →   0 please someone explain the problem D in details with approach.. :( :(
•  » » 4 years ago, # ^ |   0 My best advice for you is solve more problem! Here is a good blog about that : http://codeforces.com/blog/entry/17842
•  » » 4 years ago, # ^ |   0 I feel you. My best advice to you is to learn Dynamic Programming and go through the archives of DP problems for more practice. Most of the problems belong to the DP tag in lower Rounds. If I have to choose one tag as a cheet-sheet of doing good in contests, its DP! So although you can do the D problem using graph (Topological order), you should try it to do in a DP way. While learning dynamic programming, focus on the 2 things: Getting DP result (how many ways, maximum sum etc) Printing the DP solution (which indexes/ values I have gone through to get DP result) Here is my recursive DP solution for this problem:http://codeforces.com/contest/977/submission/37976427Here is the archive of DP problems sorted in decreasing order of most submitted:http://codeforces.com/problemset/tags/dp?order=BY_SOLVED_DESC
•  » » 4 years ago, # ^ |   0 Read this one once:977D It's okay to not understand everything in beginning.
•  » » 4 years ago, # ^ |   0 I wrote an editorial for Problem D here. You can refer it.
 » 4 years ago, # |   +11 Great contest. I enjoyed the problems immensely even though they're easy. It's a great way to distinguish between participants who are green and cyan. It helped me become blue ! Which was the goal of my year. I'm so happy I was blessed with the grace to achieve this goal. I'll work hard to sustain my rating and increasing my knowledge. I was wondering if anyone could rate the difficulty of these questions in terms of Div 2. i.e. ... If these questions were used in Div 2, which number would they be at ?Here is my GitHub repository of my solutions. Feel free to ask if you have any doubts. :)
•  » » 4 years ago, # ^ |   0 Congrats on expert!
•  » » » 4 years ago, # ^ |   0 Thank you so much for your kind wishes :) Wish you the same :)
•  » » 4 years ago, # ^ |   0 Hey Man, What is the time complexity of the solution given for E?
•  » » » 4 years ago, # ^ | ← Rev. 2 →   +1 I may be wrong, but in my solution here, I visit each vertex exactly once. So, I'd say it's O(|V|) ... Even though there are two loops, it's actually not quadratic. This is true both for finding the components and then checking if each component is a cycle.Of course, I didn't consider taking the input. Then it is O(|V| + |E|).
 » 4 years ago, # |   0 Can Someone Explain Problem F With Example
•  » » 4 years ago, # ^ |   0 suppose I have an array [1,2,3], I push them all in a map one by one and also update an array. So upon reaching 1 i check if 0 is already there. If not the update arr[i] = 1 and put the value in map. Upon going to 2 i check if 1 was already there. Yes it was, then find the value of arr[2-1] from map and fill it accordingly. In the end iterate over arr and find the max. Then backtrack to find the solution.
•  » » » 4 years ago, # ^ | ← Rev. 2 →   0 got it.Thank You So Much!
•  » » » 4 years ago, # ^ |   0 Can you post a solution ling using this technique? I am not very familiar with maps.. I want to learn.
•  » » » » 4 years ago, # ^ |   0 37990140 but this is in java. Editorial sol is in C++.
•  » » » » » 4 years ago, # ^ |   0 Thanks BeardAspirant. Just a question.. Can I do LIS too using this approach with map?
•  » » » » » » 4 years ago, # ^ |   0 in LIS you do not know what the next element would be. So, it could be 1 4 99 10000 34242424. There is no pattern. Map cannot be used there. Best is nlogn using binary search but n^2 algo is pretty good.
•  » » » » » » » 4 years ago, # ^ |   0 But can't I find out the immediate smaller element than the element I am working with now and update dp[i] with dp[immediate_smaller_elements_index]+1 ?
•  » » » » » » » » 4 years ago, # ^ |   0 how would you find dp[immediate_smaller_elements_index] in O(1)?
•  » » » » » » » » » 4 years ago, # ^ |   0 Sorry I didn't keep that in my mind. By the way, your said n^2 is pretty good, but solving F in n^2 with LIS approach gets me TLE. Is there any way I could have predicted that I would get TLE knowing the timelimit is 2sec, the range of N and my O(n^2) runtime?
•  » » » » » » » » » 4 years ago, # ^ |   0 I am not the correct person to answer but I think anywhere in 10^5 will not go through with n^2.nlgn or below is needed for those. I think I have read this somewhere. Will try to fetch that post and revert later :)
•  » » » » » » » » » 4 years ago, # ^ |   0 Many thanks. I look forward to having more conversations with you in future. :)
•  » » » » » » » » » 4 years ago, # ^ |   0 Link gives you an idea.
•  » » » 4 years ago, # ^ |   0 what if array is [1 5 7] then the length will be one which isnt desired result
•  » » » » 4 years ago, # ^ |   0 check at 1, update arr[0]=1; check at 5, if 4 is present,no then update arr[1]=1. Likewise for 7.answer =1;
 » 4 years ago, # |   +8 Many specialist became expert. it seems that new expert become instead of old specialist.
 » 4 years ago, # | ← Rev. 2 →   0 Because, as it was said above, every number can be in sequence only once and moreower every pair in the result sequence is unique, I used another approach (not found the short solution which was represented by author). I read a list of initial values, begun from the first element and formed a new list try to found appropriate predecessor for front or follower for back. O(n^2) I think so... My submission: http://codeforces.com/contest/977/submission/37968300
 » 4 years ago, # |   0 F was a variation of LIS problem. I used recursive DP but got TLE... How can I optimize it any further or do I have to use Iterative DP instead of recursive?Here's my code:http://codeforces.com/contest/977/submission/37962276
•  » » 4 years ago, # ^ |   0 I have not read your code but I do think LIS is n^2 (nlgn if binary search is used)and it fails here. need a O(n) algo to make things work.
•  » » 4 years ago, # ^ |   0 I also did LIS and got TLE :(
 » 4 years ago, # |   0 This submission: http://codeforces.com/contest/977/submission/38003904 for problem D: http://codeforces.com/contest/977/problem/D works well on my machine, and is not able to pass test 1 on server. Can anyone help me with it ?
•  » » 4 years ago, # ^ | ← Rev. 2 →   +1 I made some changes in your code. In bool DFS(int idx, int cnt) function you were not checking if idx can be last vertex of sequence, and in the end of same function you should return false. Corrected Solution change at line no. 43 and 58.
•  » » » 4 years ago, # ^ |   +1 Thanks lot my friend, about: "In bool DFS(int idx, int cnt) function you were not checking if idx can be last vertex of sequence" It is not necesary since I always enter in a non-visited node, the very bug here was that I wasn't returning false, as you certainly pointed: "in the end of same function you should return false." I already fixed it !!! and AC. Thanks a lot again
 » 4 years ago, # |   0 For problem #F, if the input is: 3 1 3 4 why the ans is: 2 2 3 there is no 2 in the array? Maybe I haven't understand the meaning?
•  » » 4 years ago, # ^ |   0 You have to print the index not the value
 » 4 years ago, # |   0 For problem E,why the output is 0,not 2 if the input is: 6 7 1 2 2 3 3 4 4 1 4 5 5 6 6 4
•  » » 4 years ago, # ^ | ← Rev. 3 →   0 There is only one connected component in the graph.We are searching for component which itself is cycle. Here we see that 1-2-3-4 and 4-5-6 are two cycles in component but component itself is not a cycle so answer is 0 not 2.
 » 4 years ago, # |   0 I have question, you have said " To qualify as a trusted participants of the third division, you must: take part in at least two rated rounds (and solve at least one problem in each of them)", So, why someone are rated in div3? (just like Milhous who is the rank1 in the contest)
•  » » 4 years ago, # ^ |   0  Regardless of whether you are a trusted participant of the third division or not, if your rating is less than 1600, then the round will be rated for you. So although those participants are not trusted, they are still rated.
 » 4 years ago, # | ← Rev. 2 →   0 Question D was very interesting and had many solutions. The editorial's approach was to sort by powers of 3 first and then powers of 2 to break the tie. But since the operations only affect the power of 2 and the power of 3, we can say that if the power of 3 is equal, the number with the greater power of 2 will be the larger number. So, sort by power of 3 first, and then the number itself. My approach was to sort it by the criteria exp(2) — exp(3). Here is a detailed analysis of my approach on Quora.
 » 4 years ago, # |   0 For D, just sort with custom cmp function: if exp_2( a ) < exp_2( b ) then a goes before b. if they are equal, then a goes before b if and only if exp_3( a ) > exp_3( b ) — so this time the sign is opposite. Then just sort array. complexity is nlogn so I dont understand why was n<=100 given.
 » 4 years ago, # |   0 How to solve problem E-Cyclic Components using Disjoint Sets?
 » 4 years ago, # | ← Rev. 3 →   0 Thanks for the contest! Very helpful
 » 4 years ago, # |   0 Another D solution by using std::deque: http://codeforces.com/contest/977/submission/37958510
 » 4 years ago, # | ← Rev. 2 →   0 I am unable to understand 977F. The problem states to "choose some subsequence of this array of maximum length such that this subsequence forms a increasing sequence of consecutive integers".How does 2 3 5 6 satisfy the condition about consecutive integers. Also 2 isnt even in the input!
•  » » 4 years ago, # ^ |   0 They are indices.
•  » » » 4 years ago, # ^ |   0 Thank You !
 » 4 years ago, # | ← Rev. 2 →   0 why no delete comment option
 » 4 years ago, # |   0 Can somebody tell me why my solution to F fails?Here's the link : Link. Thanks :)
 » 4 years ago, # |   0 Hi， I have a little problems. 977D — Divide by three, multiply by two Is "vector> v; " wrong? When I write it such as vector >v; It can successfully compile and execute
 » 4 years ago, # |   0 It would be a great help if someone explains what is logically wrong with this. http://codeforces.com/contest/977/submission/38408042
 » 4 years ago, # |   0 I solved E by dfs. when i used dfs by using stack i am getting tle on tc 6 whereas on using recursion my solution got accepted . Can someone please tell me the reason.
 » 4 years ago, # |   0 http://codeforces.com/contest/977/submission/39520609 Can someone tell me where I've gone wrong? Thanks!
 » 4 years ago, # |   +8 In problem E, Dont you mean if the vertices degree is divisible by 2?Here you have 1 of degree 4.
•  » » 4 years ago, # ^ |   -8 The graph in problem E is undirected.
•  » » 4 years ago, # ^ |   0 Vertices cannot repeat in a cycle. Otherwise, we would be talking about a circuit.
 » 4 years ago, # |   0 Can someone please tell me why I got the wrong answer on test 5 for this submision: 40518652
 » 4 years ago, # |   0 how to solve E
 » 3 years ago, # |   0 can someone help me about how i got tle in 977f48190103
•  » » 2 years ago, # ^ |   +1 i had a similar issue. i used unordered_map as i expected it to be faster than a regular map. but simply replacing my unordered_map with a regular map resulted in AC. i don't know why.
•  » » » 2 years ago, # ^ | ← Rev. 2 →   0 it's because there are two prime numbers for which the accessing time taken by the unordered_map is o(n^2). there was a blog on codeforces which cleared this doubt. https://codeforces.com/blog/entry/62393
 » 3 years ago, # |   0 In problem 4, Divide by 3 multiply by 2. I understood the code but I can't get the logic.Can someone please let me understand the code's logic??Thanks in advance.
 » 3 years ago, # |   0 problem D could also be solved using graphnumbers ->> nodes operations *2 or /3 ->> give us the edges between theses nodes use map to represent the graph cuz of the high constraint on the numbers get the root of the graph which is the number that no other number can get it(root) using any operation , with simple math and some examples we can prove that we have a root. do DFS to obtain a path that have n nodes , then you are done.[submission:https://codeforces.com/contest/977/submission/54551142]
 » 3 years ago, # |   0 Also, we can solve D by using DFS. We can build a graph of given numbers: if we have number u and (u / 3 or 2 * u) -> create edge. Our task is to find the path of n length.
 » 2 years ago, # |   0 For the problem D you can be sure that given a number x in the list the direct successor is either 2x (if in the list), x/3 (never both) or none of the former (for the last element). Also the direct predecessor is either 3x (if in the list), x/2 (never both) or none of the former (for the first element). Existence checks can be optimized by using a HashSet. So you pick any number x and you can easily compute the successors until you reach the last element and then the predecessors until you reach the first element.
 » 2 years ago, # |   0 Can someone please explain why this solution for question D gives a TLE verdict? Isn't the time complexity for this code O(nlogn)? Or is there something else that makes this code really slow? Here's the link to the code. 71393068
 » 2 years ago, # | ← Rev. 2 →   0 Hi All,can any one guide me here, what am i doing wrong?I implemented Problem B (Two-gram)This was my solution: int main() { int n; string s; string tmp; int cur_count, max_count = 0; cin >> n >> s; for (int i = 0; i < n - 1; i++) { cur_count = 0; for (int j = i; j < n - 1; j++) { if (s[i] == s[j] && s[i + 1] == s[j + 1]) { cur_count++; } } if (cur_count > max_count) { max_count = cur_count; tmp = s.substr(i, i + 2); } } cout << tmp << endl; return 0; } But it failed on testcase 6, so after failing to debug on my own, I compared it with the Solution here, the only difference I could find was I'm starting 2nd look with j=i as my understanding is any two-gram before that has already been accounted for.But in any case, I modified it to start with j=0 but still it's failing on test case 6. I can't figure out what am i missing, any help is appreciated.can you please guide me vovuh
•  » » 2 years ago, # ^ |   0 Hi everyone!So I figured the error.It nothing related to what I was wondering before.Actually it's related to the wrong use of s.substr(pos, span)I thought first parameter was start index and second parameter was end index (exclusive) so it was printing a longer sub-string, funnily enough it doesn't throw an exception when span goes out of bound, instead it makes a sub string from pos to span or end of string, whichever comes first, without throwing an error.And also that when I tried the code from tutorial I copied that part too.(It's been years I coded in C++ and I mainly work in Python so you can understand the confusion.)
•  » » 2 months ago, # ^ | ← Rev. 2 →   0 B. Two-gramvoid solve() { int n; cin >> n; string s; cin >> s; map mp; for(int i = 0, i < n-1, i++) { string k = ""; k += s[i]; k += s[i + 1]; mp[k]++; } string ans; int max = 0; for (auto x : mp) { if (x.second > max) { max = x.second; ans = x.first; } } cout << ans;}
 » 2 years ago, # |   0 Can someone please tell me a short test case where my code for problem F may have gone wrongLink for my code : https://codeforces.com/contest/977/submission/80704453Link for question : https://codeforces.com/contest/977/problem/FMy approach : I inserted all the positions of each element in a map< long long, vector< long long>>.Then I'm simply traversing over all the keys of the above map, and checking if the keys are consecutive or not.If they are not then break, otherwise check if that element is present in the right part of the array from where we have picked the last element.If not possible then break, otherwise make that element as our current and continue doing the same while inserting the picked up indexes in a temp vector and check if size of that vector is greater than previously stored ans and then replace it.Now there's obviously sth wrong or incomplete in my approach, and it would be highly helpful of anyone to help me.Thanks in advance !!
 » 22 months ago, # |   0 Could anyone please explain why my submission got "Wrong Answer on Testcase 18" for E?https://codeforces.com/contest/977/submission/86116656
 » 21 month(s) ago, # |   0 977D: Easy to implement with this approach ; just find whether *(2) or *(1/3) exists or not and proceed forward 89188467
 » 17 months ago, # |   0 The spoiler is bugged, please fix.
 » 14 months ago, # |   0 I can't understand the problem C (Less or Equal). Can anyone explain that.
 » 12 months ago, # | ← Rev. 2 →   0 Please Help. I am a beginner and I am solving this contest for practice. (sorry for necroing) in D, Can someone please explain what's wrong in this approach?: #include #include #include #define ll __int64 using namespace std; int main() { short n; cin >> n; ll a[n]; set nos, fixed; vector v; for (short i = 0; i < n; i++) { cin >> a[i]; fixed.insert(a[i]); } nos = fixed; short j = 0; ll s = a[j]; v.push_back(s); nos.erase(s); for (short i = 0; i < n; i++) { if (a[i] == s) continue; if ((s % 3 == 0) && (nos.count(s / 3))) { s /= 3; v.push_back(s); nos.erase(s); } if (nos.count(s * 2)) { s = s * 2; v.push_back(s); nos.erase(s); } if ((i + 1 == n) && (v.size() != n)) { v.clear(); i = -1; j++; s = a[j]; v.push_back(s); nos = fixed; nos.erase(s); } } for (short i = 0; i < n; i++) { cout << v[i] << endl; } return 0; }  Your code here... 
 » 12 months ago, # |   0 Can Anyone point out why my submission for E is failing E problem sub
•  » » 12 months ago, # ^ |   0 Anyone struggling with test case 18 of E check your answer for 5 4 1 2 5 1 5 3 3 4this is a tree so ans must be 0 for this one.
•  » » » 12 months ago, # ^ |   0 Adding Problem E in comments so that it is reachable through find in web browser.
 » 4 months ago, # |   0 Can anyone tell me why this solution doesn't work for E Cyclic Components?check cycle by count the edges and nodes and index of the cycle node and they all must be the same.