### Warawreh's blog

By Warawreh, 2 years ago,

• +207

 » 2 years ago, # |   +16 Can someone explain me how the complexity in E becomes 2^(m/2)
•  » » 2 years ago, # ^ | ← Rev. 2 →   +14 Divide the friends in half and calculate the maximal independent set on each part, then merge them, every part can be done in O(2^(m/2) * (m/2)^2). From my solution you will easy see the complexity.
•  » » » 2 years ago, # ^ |   0 Thanks
•  » » » 2 years ago, # ^ |   +5 can you please elaborate how you are merging the results of two sets, each set have (m/2)*(2^m/2) states , i am not getting how we can use these result to combine because if a path come from set1 to set2 then the states of set2 is not valid anymore(means can't be used directly) since i could have visited some vertices in set1 which blocks some vertices of set2 whose effect is not included in set2 states. please help. in my graph each two nodes have edge between them if they both can be made happier.
 » 2 years ago, # |   +11 The Editorial is so fast!
 » 2 years ago, # |   +32 One of the best contests I wrote, interesting & balanced problems and a fast editorial!
 » 2 years ago, # | ← Rev. 3 →   0 Problem B alternate ideas!!
•  » » 2 years ago, # ^ |   0 Make a frequency array (not really frequency though) corresponding to small english alphabets (size:26). Iterate through the given string. Whenever you get consecutive occurences for a alphabet(use a simple while loop), increment the value corresponding to the alphabet in the array. Say you get 'm' consecutive occurences for a alphabet while iterating, this would mean you have to increment the corresponding array value of alphabet by m/k (Think!). Do this whenever you get consecutive occurences for any alphabet. When you have finished iterating, the answer would then be the maximum value in the frequency array.
•  » » » 2 years ago, # ^ |   0 Thanks!!!
•  » » 2 years ago, # ^ |   0 you need to find the maximum occurrence of a substring with length k where every letter is same
 » 2 years ago, # |   +3 I couldn't take part in the contest but invented another solution for E.One creates a bipartite graph in which edges are between (id of friend) and (id of group between two 1's) if this friend belongs to that group.Now I only have to find maximal matching in this graph — each selected edge will mean that we have to change our handle to that friend's name before this group.In my opinion it should fit in the time limit, because we can have only 40 friends.I will try to implement this solution later and will let you know if it works as well.
•  » » 2 years ago, # ^ |   0 Can you elaborate this a bit more? This was the route I took before switching to independent set formulation. Maximal matching would mean that you select only one of the edges from all the edges incident on a friend. How does finding this matching solve the problem?
•  » » 2 years ago, # ^ |   0 Ok, so a friend gave me a sign that I misunderstund the problem — I thought a friend should see his name at least once and it is not true — they should see their name each time they visit.Sorry for mistke. Anyway, this still solves a problem, just not this one :p
•  » » » 2 years ago, # ^ |   0 There still won't be bipartite graph tho.
•  » » 2 years ago, # ^ |   +21 I don't think this will work. A name needs to be chosen every time for it to be happy.
•  » » » 2 years ago, # ^ |   +3 This is what I overlooked. Thanks for letting me know! :)
•  » » 2 years ago, # ^ |   0 But in Bipartite Matching you can manipulate the already assigned match, but here can you ?
 » 2 years ago, # | ← Rev. 2 →   0 Thanks, for the great round.
•  » » 2 years ago, # ^ |   +1 It wasn't ABCD were just pure implementation and E has very much similarity with https://codeforces.com/blog/entry/4623
 » 2 years ago, # |   +11 Should a randomized solution pass for E? Can anyone figure out a chance of success. Can use this algo for reference: https://codeforces.com/contest/1105/submission/48630631
•  » » 2 years ago, # ^ | ← Rev. 2 →   +1 Yeah, tests must be stronger, of course. Such solutions should not pass.But nowadays, random is strong enough :(( Everywhere, on TopCoder, Codeforces and other programming platforms such solution pass when it should not be happened, I see this fact once or twice a week.
•  » » 2 years ago, # ^ |   -12 Yes I am trying to make counter tests for it, thanks for bringing it out :D
•  » » » 2 years ago, # ^ | ← Rev. 5 →   +16 Why there were no tests with the answer 15...38 for the task E? Only 39,40 and small one.I suppose that "39" for the last testcase corresponds to the "challenge" test, there were challenges on E.So, without this challenge all tests were < 15 and only "40". Do you know that it can easily be beaten with some solution for small answers and printing "40" otherwise?How many "bad" solutions you've wrote to check the test pack? It should be > 10 different bad (random, brute force, greedy) solutions that must be written by jury to test their tests and how they are strong enough.The main thing, that this is not done on Codeforces or other platforms, weak tests lead to weak solutions, random accepts everywhere... Lazy problem setters. Only money. Nothing personal..Give one contest in a month but strong one, with tests like from Andrew Stankevich on geometry neerc problems.I was also completely infuriated with random solutions for recent Topcoder SRM 746 task 500, where you have to generate string with length <= 100 from letters "a" and "b" and the number of "good" substrings equal to N (N <= 1000 is given), "good" is a substring where "palindrome check" pairwise symbols are different at all positions. The people divided into 2 groups, one that solved it by creating the technique of generating such strings, other, like Kunyavskiy solved with 10000 or more iterations of random strings where next character is changing with 3/10 probability! So dirty solution for 500 task. And it is only because authors like to accept them.
•  » » » 2 years ago, # ^ |   0 Are you planning to redo the system tests?
•  » » » » 2 years ago, # ^ | ← Rev. 2 →   +3 I suppose it can be done only in archive, the contest results are final.
 » 2 years ago, # |   0 I like your game very much. Thank you very much.A Player from China
 » 2 years ago, # |   +12 In my solution to E for finding max independent set I remove vertex and her neighbor vertex and edges, which incident by all this vertex, which have minimal neighbor vertexes. And this is got AC. Overall complexity O(M^2). Or am I mistaken somewhere?В моём решении задачи Е для нахождения минимального независимого множества вершин я находил вершину, имеющую на текущий момент наименьшее количество оставшихся соседей и удалял её, её соседей, и все рёбра, смежные со всеми удаляемыми вершинами. Это решение получило Accepted. Сложность O(M^2), где M — количество друзей. Или я где-то ошибся?
•  » » 2 years ago, # ^ |   0 This solution is incorrect, here is a countertest. Your solution outputs 2, while it's possible to satisfy 3 friends (b, c and d).
•  » » » 2 years ago, # ^ | ← Rev. 3 →   0 True, you can also use the countertest from here https://stackoverflow.com/questions/13921679/why-is-greedy-algorithm-not-finding-maximum-independent-set-of-a-graph test21 6 1 2 d 2 c 1 2 d 2 e 1 2 a 2 b 1 2 a 2 f 1 2 b 2 c 1 2 b 2 f 1 2 f 2 e 
•  » » 2 years ago, # ^ |   0 Ok, were added testcase 30. But this problem can solve by random))
 » 2 years ago, # |   0 Can we solve problem E with other way(solution with no graphs)?
•  » » 2 years ago, # ^ |   +2 No, because this problem can be directly converted to finding maximum independent set. If you end up solving this another way you would have essentially solved the maximum independent set problem
•  » » » 2 years ago, # ^ | ← Rev. 2 →   0 I solved it using greedy algorithm and was quiet surprised to see it accepted. Solution — Formed the graph in same fashion as mentioned in editorial. Repeat until graph is empty - Choose the node with minimum degree and increment answer by 1. Remove this node and all its neighbour from the graph. Submission 48636151
•  » » » 2 years ago, # ^ |   -6 It doesn't mean anything. To prove that there is no polynomial solution, you should convert the maximum independent set problem to this problem, but not vice versa.
•  » » » » 2 years ago, # ^ |   +6 This problem is a bijection to the maximum indepent set problem. This is because every single graph can be produced in the problem. Every single graph can also be written in the form of our problem so they are essentially the same problem
•  » » » 2 years ago, # ^ |   0 You can still solve it without graphs, it will just not be in polynomial time...
 » 2 years ago, # |   0 Hi, can someone tell me what happened here ? gcc-14 WA 48634660gcc-11 AC 48641033(Codes are identical)
•  » » 2 years ago, # ^ | ← Rev. 2 →   +2 You haven't initialised a variable pr so that a comparison sol != pr ends up with undefined behaviour.
•  » » » 2 years ago, # ^ |   0 Tnx :D
 » 2 years ago, # | ← Rev. 2 →   0 Hello there :D Concerning problem DI wanted to know why my first solution passed. I only changed this while(ok) { ok = 0; for(int i = 1 ; i <= p ; i++) ok |= bfs(i); }to thiswhile(ok) { ok = 0; for(int i = 1 ; i <= p ; i++) if(v[i].size()) ok |= bfs(i); }thanks in advance
•  » » 2 years ago, # ^ | ← Rev. 2 →   +6 The initiation of the queue takes a lot of time. This is why you get TLE, I had the same problem. You can take a look at my solutions, I changed the queue from a local variable to a global one and it made a huge difference. ;)Local variable: > 2000ms Global variable: 46ms
•  » » » 2 years ago, # ^ |   0 wow, that is very very strange...
•  » » » 2 years ago, # ^ |   +3 This is not strange. All because u create a queue many times, i.e. call the constructor every time. It takes a long time.
•  » » » 2 years ago, # ^ |   0 Thank you very much
 » 2 years ago, # | ← Rev. 3 →   0 I'm getting WA on test 38 in problem D I simply process all the rounds with bfs I'm curios to know what's wrong with my code can anyone help me. My submission: https://codeforces.com/contest/1105/submission/48643495
•  » » 2 years ago, # ^ | ← Rev. 4 →   0 Well, as I see you've lost almost 1000 cells: you got 500488+498514=999002 and not 1000000. You've counted all the 1's and 2's so let's submit your code and see whats inside those cells that wasn't counted: submission Looks like rubbish. Can you find how it got there?Oh, now I see it — guess its got sucked in from the sides, because of copy-pasting a misspell. Look, it's working.. But what happened with that rubbish in 13th line? Why only 13th? Interesting...
 » 2 years ago, # |   0 What am I missing in E? Lets say that between first two borders there are friends A and B and they are connected by edge. Lets say that between second and third border there are also friends A and B and they are connected too. MIS of given graph is 2 but answer is 1 as far as I know, so where am I wrong?
•  » » 2 years ago, # ^ |   0 We add an edge (A, B) to the graph iff A and B appear simultaneously in-between borders at least once. So the size of the MIS is 1 because A and B are connected.
•  » » » 2 years ago, # ^ |   0 Oh so we make 1 graph that contains edges based on all gaps, and not more graphs for each gap. Okay, thank you :)
•  » » » » 2 years ago, # ^ |   0 1 2 a 2 b 1 2 a 2 bWhy isn't the anwser 2?
•  » » » » » 2 years ago, # ^ |   0 Because if first name is a and second is b(or first is b and second is a) then answer is 0, If first is a and second is a answer is 1, same in the case of b. Answer cannot be 2
•  » » » » » » 2 years ago, # ^ |   0 oh, i though that a friend were happy if he saw his handle at least once lol
•  » » » » » » » 2 years ago, # ^ |   0 No, he has to see his name every time
 » 2 years ago, # | ← Rev. 2 →   +2 I was trying problem C by stars and bars method of combinatorics. DP didn't occur to me.
 » 2 years ago, # |   0 Problem C can be solved in O(logn) and memorisation.
•  » » 2 years ago, # ^ |   0 How?
•  » » » 2 years ago, # ^ | ← Rev. 4 →   +15 Let's say You have given range [L, R] and a value n. and you have to find the number of ways so that the after division by 3 remainder should be r (0 <= r < 3). Let's find  solve(n, r) Now you can divide n in two parts: n/2 and (n — n/2). Apply the same process to these parts considering these three cases:case 1: sum of all the numbers in first part(n / 2) has remainder 0, hence the other part must have remainder r.  solve(n/2, 0) * solve(n - n/2, r) case 2: sum of all the numbers in first part(n / 2) has remainder 1, hence the other part must have remainder (3 + r — 1) % 3.  solve(n/2, 1) * solve(n - n/2, (3 + r - 1) % 3) case 3: sum of all the numbers in first part(n / 2) has remainder 2, hence the other part must have remainder (3 + r — 2) % 3.  solve(n/2, 2) * solve( n/2, (3 + r - 2) % 3) For base case consider n = 1 for r = 0, 1, 2.That's it. Now sum all these cases and you are done. Time Complexity: O(logn) if you will use unordered_map.
•  » » » » 2 years ago, # ^ |   0 Its like counting a^b .
•  » » » » 2 years ago, # ^ |   0 slappy Can you share your code ?
•  » » » » » 2 years ago, # ^ |   0
•  » » » » » » 2 years ago, # ^ |   0 Tnx :D
•  » » » » » » 8 months ago, # ^ |   0 well written code. easy to understand.
•  » » » » 8 months ago, # ^ |   0 Actually same approach came to my mind,we can use divide and conquer algorithm, since 2 nos which are multiple of 3 , its sum will also be multiple of 3
 » 2 years ago, # | ← Rev. 2 →   0 .
 » 2 years ago, # |   +3 Thank you for this contest <3, I became pupil again :p
 » 2 years ago, # | ← Rev. 2 →   +6 time limit for D was too strict, no python solution passed the TLE during the contest.you can check out my python2 implementation of intended solutions gets TLE at test case 13also all these other solutions from other users in python3 got TLE even if most of them are correct as in the editorial TLE test case 13 TLE test case 13 [TLE test case 13](https://codeforces.com/contest/1105/submission/48640359EDIT: I implemented a solution using collections.deque but still gets TLE, does anyone have any idea how to get AC with python?
•  » » 2 years ago, # ^ | ← Rev. 3 →   +12 Here's the thing, there are multiple python interpreters. The one you used is called CPython and is the standard one, but it is very slow. The standard python interpreter used for competitive programming is called pypy, use that one and everything should run a lot quicker!Your code submitted in pypy3 easily got accepted (only took 560 ms out of 2000 ms). It's the exact same code, just submitted under pypy3 instead of CPython 3. There really is an insane difference between CPython and pypy but for some reason many websites don't make it obvious. For example Kattis lets you pick between python 2 and python 3 when you submit, but it is actually pypy2 and CPython3. So anyone submitting under python 3 will essentially get timeout.A small thing to note, from my experience I think that pypy2 is slightly quicker than pypy3, so if you want to be competetive using python, I highly advice using pypy2. Also speeding up input/output can really be helpful.EDIT: Saw that what I submitted in pypy3 was not your code but one of the ones you linked. I then tried to submit your code in pypy2. Even in pypy your solution gets timeout because of sorting a huge list of lists is super slow, this time around it can easily be fixed by switching to a bucket sort. However with the TL problems fixed the code gets wrong answer at testcase 15. I think that the way you use double ended queues is wrong. Here is my pypy2 solution if you want to see one way of using them (it is also a pretty quick only taking 405 ms). Your problem is that you've mixed all players into one double ended queue which messes with the order.
•  » » » 2 years ago, # ^ |   0 Wow this was a really valuable answer! Thank you very much.Made a lot of clarity for me on the topic. I will experiment as you said and report here my findings :)
 » 2 years ago, # | ← Rev. 3 →   +1 Can Someone Help me in D problem ? I am getting Memory Limit Exceeded on test 20My submission — https://codeforces.com/contest/1105/submission/48646487
•  » » 2 years ago, # ^ |   0 You forget to pop from the queue :)
•  » » » 2 years ago, # ^ |   0 Lol.. Then I should got TLE bro xD
•  » » » » 2 years ago, # ^ |   0 I don't know try it maybe it works.
 » 2 years ago, # | ← Rev. 2 →   0 Please, can someone explain to me test 5 in problem D? Test: #54 4 21 1000000000..........2....1 Answer of Judge3 13 I think it should be5 11
•  » » 2 years ago, # ^ |   +4 the first player can only move to a cell with a sequence of moves no more than 1 and the second player can move to a cell with a sequence of moves no more than 1000000000 which means that he can move to any other cell in the grid if it has not been visited by the first player in the first round player 1 can move from cell (4,4) to cell (3,4) and cell (4,3) and the grid looks like this ..........21..11then the second player moves to all not-occupied cells and the grid looks like this 2222222222212211hope you understand this and sorry for my bad english..
•  » » » 2 years ago, # ^ | ← Rev. 3 →   +1 Thank you.I have just read the announcement that explain what wasn't explained in the statement. I thought that one can move either up or right or down or left starting from only his origin cell.
 » 2 years ago, # |   0 Can someone elaborate on Problem C? TIA
•  » » 2 years ago, # ^ |   0 Yes if someone can further explain it it would be really nice.
•  » » 2 years ago, # ^ |   0 yes it would be helpful, i am also not able to figure it out
•  » » 2 years ago, # ^ | ← Rev. 2 →   +7 Let's denote m0 as number of x in range L and R, such that x % 3 = 0 m1 as number of x in range L and R, such that x % 3 = 1 m2 as number of x in range L and R, such that x % 3 = 2 You can find this 3 numbers in O(1)Also dp[i][j] the number of ways of the lost array of length i and its sum % 3 = jThe base case is dp[1][0] = m0, dp[1][1] = m1, dp[1][2] = m2Let's think about how to find value for some i > 1, dp[i][0]. There is 3 case to get (a + b) % 3 = 0, we can pair any (a, b) such that a % 3 = 0 and b % 3 = 0, or a % 3 = 1 and b % 3 = 2, or a % 3 = 2 and b % 2 = 1 so dp[i][0] = dp[i - 1][0] * m0 + dp[i - 1][1] * m2 + dp[i - 1][2] * m1 sum of the 3 possible case. You can apply the same logic to find dp[i][1] and dp[i][2]answer is dp[n][0]. My submission
•  » » » 10 months ago, # ^ |   0 plzz can you explain why you have multiplied dp[i-1][0] with m0 (and similar for others)because order of array matters
•  » » » » 10 months ago, # ^ |   0 what do you mean "order of array matters"?
•  » » » 5 months ago, # ^ |   0 great
•  » » 2 years ago, # ^ | ← Rev. 2 →   +5 We need to find ways of choosing n numbers in an array, each of which may vary from l to r inclusive such that their sum is a multiple of 3. first we may recast this problem:let p(x)=(x^l + x^(l+1)+ x^(l+2)+ x^(l+3)+ x^(l+4)+......x^r)^nnow in this p(x), the coefficient of x^i is simply the number of ways we can use n numbers varying from l to r to sum upto i.As each time an x^i term comes out when we multiply out the n brackets of (x^l + x^(l+1)+ x^(l+2)+ x^(l+3)+ x^(l+4)+......x^r), taking some powers of x between l and r from each bracket and multiplying them out such that their sum reaches i, each unique way we can do this, we increase coefficient of x^i by 1.So basically the coefficient of x^i in p(x) is the number of ways of choosing the n numbers in the array each varying from l to r such that their sum is i.So, now we want all ways in which this sum is a multiple of 3. in other words we want the sum of all coefficients of p(x) which are coefficients of powers divisible by 3. so basically if p(x)= x+4x^2+x^3+x^4+x^5 +7x^6 (arbitrary example); we only want coefficient of x^3 and x^6 or 1 + 7 = 8lets call this sum our answer So for that we can use 3*answer= p(1) + p(w)+ p(w^2)(where 1, w, w^2 are cube roots of unity) as in the expansion of p(1)+p(w)+p(w^2),only powers divisible by 3 remain as for example if p(x)=2x+3x^2+6x^3:p(1)+p(w)+p(w^2) will be 3*(6)or 6+6+6 (coefficient of x^3 ) as x and x^2 will sum up to zero (as 1+w+w^2 =0 )So basically we calculate our answer as (p(1)+p(w)+p(w^2))/3and p(x)=(x^l + x^(l+1)+ x^(l+2)+ x^(l+3)+ x^(l+4)+......x^r)^n can be easily calculated in log(n) time using fast exponentiation and g-p series sum.
•  » » » 2 years ago, # ^ | ← Rev. 2 →   0 Could you elaborate the last paragraph? Could you also post a link to the code? Thanks
•  » » » » 2 years ago, # ^ |   0 Here is the link to my code: https://codeforces.com/contest/1105/submission/48648308I'm saying that the final problem is (p(1)+p(w)+p(w^2))/3 where p(x)=(x^l + x^(l+1)+ x^(l+2)+ x^(l+3)+ x^(l+4)+......x^r) now summing this from l to r is tedious. but thankfully we can do so in constant time as the formula for a geometric progression sum is known. x^l + x^(l+1)+ x^(l+2)+ x^(l+3)+ x^(l+4)+......x^r= (x^l)*(x^(r-l+1)-1)/(x-1)
 » 2 years ago, # |   +14 Warawreh Can you provide me with some link of The maximum independent set tutorial? also, it would be nice if that explains how to combine meet in the middle technique as well. Thanks
 » 2 years ago, # |   +3 Dance Link can fuck E. Believe me.Very fast.
•  » » 2 years ago, # ^ |   0 Can you put your code here?
•  » » » 2 years ago, # ^ |   +3
•  » » 2 years ago, # ^ |   0 Can you explain how you applied dancing links to solve it?
 » 2 years ago, # |   0 Can someone explain 1105-C?
 » 2 years ago, # |   0 I can't get, why my submission received runtime error on first preset, while locally everything is OK, with very same code and test data https://codeforces.com/contest/1105/submission/48633734
 » 2 years ago, # | ← Rev. 2 →   0 Can someone please explain why my submission for D is giving TLE? I used BFS. https://codeforces.com/contest/1105/submission/48650058
•  » » 2 years ago, # ^ | ← Rev. 3 →   +3 This is a small test case where your code will give TLE think about why it gives TLE and how to fix it :) 3 3 1 1 ... ### 1.. 
•  » » » 2 years ago, # ^ |   0 Ah! Didn't consider the case when it's impossible to cover all empty cells. Thanks a lot!
•  » » » » 2 years ago, # ^ |   0 You're welcome.
 » 2 years ago, # |   0 Most people (including me) passed problem E by using a randomized method.I wonder if this is the right way to do it.Because you can hardly make its time complexity worse. :)If you can hack it,please let me know.Thank you very much!my code:48652621 Time:62ms
 » 2 years ago, # |   +5 Can anyone explain why an algorithm like this one: 48645129 doesn't MLE? It seems to be storing 2m states in the worst case? I'm not sure where my logic is wrong, and I can't prove that it achieves a bound of 2m / 2. Can anyone help?
•  » » 2 years ago, # ^ |   +8 I think it is just that the test are weak. There surely are 2m states in the worst case.
 » 2 years ago, # | ← Rev. 3 →   +10 I think this round is a little bit too easy,maybe just as easy as Div3. However the time is pretty suitable for Chinese contestants.
 » 2 years ago, # | ← Rev. 2 →   +19 I don't think it is a good round. A-D are extremely easy in div.2, while E is an ordinary independent set in general graph, which is not suitable at all for a contest problem (too easy as well if you have seen similar problems). Maybe it is the author who wants to publish his idea to solve such a general problem, but I think it should be in an Edu Round rather than a regular round.Hope we will have better round in the future.
 » 2 years ago, # |   +3 A wording suggestion: In the tutorial of E, you said Let's find a first bit of mask. It would be more clear if you say "The first set bit of the mask".
 » 2 years ago, # |   +9 My solution (or say explanation) to problem E: To find the maximum clique, we first divide the points into two parts. For each subset in the second part, we find out its maximum sub-clique (just a bitmask dp, the transaction is to remove one of the vertices, or all the vertices form a clique). For each subset in the first part, we can easily find out all vertices in the second part that have edges to all vertices we have chosen in the first part, then we can use the maximum sub-clique we have found in the second part to get the answer.
 » 2 years ago, # |   0 Good tutorial and contest, but I am very weak,,,became pupil...QAQ
 » 2 years ago, # |   0 48662260Why does 0-1 BFS + dp WA15 for D?
•  » » 2 years ago, # ^ | ← Rev. 2 →   +6 let us see these two solutions.dir[4][2]={-1,0,1,0,0,1,0,-1} will return Wrong answer on test 15 .dir[4][2]={0,1,0,-1,1,0,-1,0} will return Accepted.who can tell me why?
•  » » 2 years ago, # ^ |   +3 The inner loop does not work as expected. (I made the same mistake...) For example, your code returns 8 2 to this input (9 1 is expected): 5 3 2 6 1 2## .## ... .#. 1..because the path (5,1), (5,2), (5,3), (4,3), ..., (3,1) is searched first, and then the shorter path to (3,1) is not considered.
•  » » » 2 years ago, # ^ |   0 48677210I changed about my code a bit to fix what you said, but I'm still getting WA15
•  » » » » 2 years ago, # ^ |   0 Oops, I didn't really understand how the original code works.I'm not quite sure why it does not work, but maybe you have to update dp[x][y] earlier. I just have tried it 48711922 and passed test 15, but got TLE on test 20.
 » 2 years ago, # |   +1 I think complexity of D can be easily reduced to O(n*m + p). A player won't be allowed to play in further rounds if he is blocked from all sides in a round.So the worst case would be when in each chance we acquire an additional cell only.
•  » » 2 years ago, # ^ |   +8 isn't the time complexity of authors solution already O(n*m+p) like we won't visit a vertex more than once during indvidual bfs .
•  » » » 2 years ago, # ^ |   0 Acc. to editorial, if all players are blocked except one and if that only unblocked expands by only one in each round.Something like this -2 3 4 5 6 7 8 # # # # # # # . . . # . . . . # . # . # . . # . # . # . 1 # . . . # .
 » 2 years ago, # |   0 Can anyone help with problem D? I used bfs and have the same complexity but got a TLE somehow... Here's my submission: https://codeforces.com/contest/1105/submission/48635565
•  » » 2 years ago, # ^ |   0 Use C++17 you will get Ac.
•  » » » 2 years ago, # ^ |   0 i tried and it didn't work
•  » » » » 2 years ago, # ^ |   0 Oh no.Sorry for I can't find the mistake.
•  » » » » » 2 years ago, # ^ |   0 Can You Help me why I am getting TLE on test 20 https://codeforces.com/contest/1105/submission/48682380Thanks in advance
 » 2 years ago, # |   +3 tutu
 » 2 years ago, # |   0 I think the solution is not enough to solve. To solve this problem is mainly about which language you choose(there is no code Accepted with Python2/3,but if I copy some codes and change them to pypy is enough.For C++ it is worse C++11 will Failed on system test and C++17 will Ac....).So I think the writer should try both java and python to make sure the time limit is enough.C++17'1000ms maybe can do things more than 3000ms of java and python!!
 » 2 years ago, # |   0 Problem B: You didn't mention that string will be only of lower case alphabets in problem.
 » 2 years ago, # |   0 In div 2 D, i used priority queue of vector and i got TLE and priority queue of struct worked properly and rather it was faster than the previous one ?
•  » » 2 years ago, # ^ |   0 Can you please help me.. I getting TLE on test 20 in problem D.
 » 2 years ago, # | ← Rev. 2 →   0 My SubmissionMy aproach on E is given below-For 2nd type checked if Hiasat had a 1st type just before it. If yes, then Hiasat can change his handle to his friend name. So the friend beomes happy.If Hiasat don't have any 1st type just before the 2nd type, then he can't change handle. But if the current handle matches with the friend's handle who is visiting the site, then that friend stays happy. Otherwise that friend becomes sad.Finally checked every friend. If anyone is happy, then incremented count.Got WA on 8th case. The jury says ans is 9, but my code says 12.What's wrong in my aproach?
•  » » 2 years ago, # ^ |   0 Yours approach is greedy. Check this case: 7 2 1 2 b 2 a 1 2 a 1 2 b Right ans would be 1, but according to your approach it's 2.
•  » » » 2 years ago, # ^ | ← Rev. 4 →   0 [ Many thanks for the replay ]At first 1.Next b becomes happy.Next a becomes sad.Then again 1.So a becomes happy.Then 1.Then b becomes happy.So at last, both were happy, right?Am i missing something?
•  » » » » 2 years ago, # ^ |   0 A person is said to be ~~~~~ happy only if each and every time he visits, he see his name. ~~~~~ So if 'a' once becomes unhappy, he will never become happy again.
 » 2 years ago, # |   0 Can Anyone please help me.. I getting TLE on test 20 in problem D.
 » 2 years ago, # | ← Rev. 2 →   0 For problem D, I tried a solution using only two queues, but keep getting wrong answer on the test case 15 :( Can anybody help?My submission link
•  » » 2 years ago, # ^ | ← Rev. 2 →   +4 I solved. The problem was the choice of the queue. 4 3 2 2 1 1.. 1.. ..2 ... Outputs 9 3 instead of 10 2
•  » » » 2 years ago, # ^ |   0 Thanks for your case. It helps me a lot. :Pbtw, how do you construct this case?
•  » » » » 2 years ago, # ^ | ← Rev. 2 →   0 Actually I search for all the examples for problem D in this post and the original post. :(
•  » » » » » 2 years ago, # ^ |   0 Thanks :P
•  » » » 17 months ago, # ^ |   0 It would be really helpful if you say how you fixed this problem :)
 » 2 years ago, # | ← Rev. 3 →   0 Hello, I got stuck on problem E because my Algorithm outputs weird ans and If I run my solution on another compiler it can output the real answer, so I dont kow if I doing a mistake reading graph. Here is my last Subm: 48689549
•  » » 2 years ago, # ^ |   0 Put some "printf(i, count[i])" in your code and look how your count is growing
 » 2 years ago, # |   +8 Can E be solved in O(2m / 2)? I could solve it in but not sure if it can be solved in less than this complexity. The editorial is not clear to me and I am not quite sure about its solution's complexity.
•  » » 2 years ago, # ^ |   0 can you please explain your approach . if you did using meet in middle then how you proceed further after maintaining the bitmasks for each states for maximum distance in each set. how to merge the processing of both sets?
•  » » » 2 years ago, # ^ |   +8 Imagine each friend as a bit and nbr[i] is a value having set bits only in positions corresponding to friends adjacent to the ith friend. Let dp[j] be the maximum independent set size, where its participants have their corresponding bits set in j.How to calculate dp[j]? iterate on every set bit of j, let the current set bit in loop be the kth bit, if nbr[k] has no intersection with j (nbr[k]&j = 0), then continue looping normally, else, you have either to remove the kth friend or remove the intersection (nbr[k]&j) from j, so dp[j] will be max(dp[x], dp[y]), where x is j after clearing the kth friend bit, y is j after clearing the intersection bits. If the loop finished without entering the else branch, dp[j] will just be count of set bits in j.Assume we calculated dp1 for the most significant bits and dp2 for the least significant bits, for every possible mask m1 in dp1, make mask m2 for dp2, where the kth bit in m2 is set only if nbr[k]&m1 = 0 (no intersection with m1). And set ans = max(ans, dp[m1] + dp[m2]).
•  » » » » 2 years ago, # ^ | ← Rev. 2 →   0 thanks sir for explaining, while building dp[j] if we ever entered in else part then we have to remove either Kth bit or intersection part in both case mask(j) value is no longer j then why we are saving result in dp[j], according to dp[j] definition it should be only either zero or number of set bits in j isn't it?because definition of dp1[j] matters while choosing mask in dp2,but sir i think with your approch we will never miss the most optimal answer instead of not choosing the most optimal dp1[m1],dp2[m2] pair every time isn't it, am i right?
•  » » » » » 2 years ago, # ^ |   +3 If you chose a specific dp2's mask m2 based on a specific dp1's mask m1 which imposed clearing some bits in m2 because the friends representing these bits have neighbors which have their bits set in m1, then even if dp1[m1] was a number less than set bits count in m1, you will reach the optimal answer anyway. Because eventually you will reach that m1 where dp[m1] = set bits count in m1.
•  » » » » » » 2 years ago, # ^ |   +5 thanks a lot got it accepted:D
 » 2 years ago, # |   0 can anyone explain problem C in more detail ?
•  » » 2 years ago, # ^ |   0 you need to store the number of ways to recover the array till index i such that the remainder of "sum so far" divided by 3 equals to 0,1 and 2 as you can have three remainders, this way you can calculate 3 same(same meaning) values for next index by using the number of different numbers you have in range l->r , means number of numbers giving remainder 0,1,2. for 0 -> previous=0 , current=0previous=1 , current=2previous=2 , current=1for 1-> previous=0 , current=1 ... and so on
•  » » » 2 years ago, # ^ |   0 thank you <3
 » 2 years ago, # | ← Rev. 2 →   +5 How to solve A if the constraints over Ai were large ?EDIT — Here is the ternary search solution
•  » » 2 years ago, # ^ | ← Rev. 2 →   0 I think the cost function cost(t) is unimodal. That means you can find the minimum cost using ternary search. overall complexity will be nlog(Max).
•  » » » 2 years ago, # ^ |   0 I see. Good point. Do you have a proof of unimodality ?
•  » » 2 years ago, # ^ |   0 You could take a median (n%2==1) or two (n%2==0) and +/-1 on each of median. Then check this 3-6 numbers.
•  » » » 2 years ago, # ^ |   0 Proof ?
•  » » » » 2 years ago, # ^ | ← Rev. 2 →   0 By median definition. And +/-1 is cause of problem statement.
 » 2 years ago, # |   0 @admin, I think the testcases in Problem D are weak. I have submitted 2 solutions (links below) having same code (just order of checking conditions is changed).Solution 1 (verdict: WA): http://codeforces.com/contest/1105/submission/48716141Solution 2 (verdict: AC): http://codeforces.com/contest/1105/submission/48716349As you can see I have just altered the checking condition in BFS to store in queue. It gave AC. The problem is we need to know maximum steps we can go from this cell before marking it visited. Else it is possible that not all cells (that could have been visited in this step) will be visited.If I am mistaking something do tell me. Thanks!
 » 2 years ago, # |   0 If constraints of N in Problem C were large (N <= 10^{18}), then we could use matrix exponentiation to solve it. Here is my code for reference. :)It is a faster way to find the solution if N were large. :)Complexity is O(K^3 log N), where K is the size of the matrix being used.
 » 2 years ago, # |   0 i am getting WA on tes#41, i am doing a BFS traversal for each player, dont know what sis wrong. Can anyone help? Thanks in advance! Link to submission
 » 2 years ago, # |   +13 We can also solve E without memoization or meet in the middle ideas. In solve(mask), we look at the first set bit of the mask. If this node doesn't have any other neighbors in mask, we should always take it and we do one recursive call. Otherwise, we have two options: we take it and we remove it and all its neighbors from mask, or we don't take it and we only remove it from mask.To analyze the time complexity of solve, let's define a function T(k) that is a bound on the time to compute solve(mask) if mask has k set bits. In the first case mentioned above (the first node has no neighbors in mask), we only do one recursive call, so T(k) ≥ T(k - 1). Otherwise, we have to do two recursive calls: one on a set of size k - 1 and one on a set of size at most k - 2 (this is because we removed at least one neighbor from mask). So T(k) ≥ T(k - 1) + T(k - 2). This is the worse bound, so let's take T(k) = T(k - 1) + T(k - 2) to get our bound on the running time. With base cases of T(0) = T(1) = 1, we see that T(k) is the kth Fibonacci number. That is, T(k) ≈ 1.618k. And since 1.61840 ≈ 108, this should run in time.Accepted submission: https://codeforces.com/contest/1105/submission/48864093
 » 2 years ago, # |   0 for problem C, I wonder why this solution got AC, it should not get AC because I switched the values of x mod 1 and x mod 2 by mistake and even so it passed, if I'm wrong please correct me. https://codeforces.com/contest/1105/submission/51246094
 » 2 years ago, # |   0 I tried to solve 1105D Kilani and the game using multi-source bfs but I keep on getting TLE,can anyone help me out?https://codeforces.com/contest/1105/submission/50567716 (Comments added to every line of code for better understanding)
 » 14 months ago, # |   0 Why am I getting TLE in the 45th test?
 » 3 months ago, # |   0 1105C — Ayoub and Lost ArrayIs best explained in this link: https://www.youtube.com/watch?v=eGCDdccErmQ
 » 7 weeks ago, # |   0 The idea of taking 3k,3K+1,3K+2 was very interesting.. thanks