Tutorial is loading...

Tutorial is loading...

Tutorial is loading...

Tutorial is loading...

Tutorial is loading...

# | User | Rating |
---|---|---|

1 | tourist | 3697 |

2 | Benq | 3583 |

3 | Petr | 3522 |

4 | ecnerwala | 3467 |

5 | Radewoosh | 3466 |

6 | maroonrk | 3369 |

7 | Um_nik | 3358 |

8 | jiangly | 3330 |

9 | Miracle03 | 3314 |

10 | scott_wu | 3313 |

# | User | Contrib. |
---|---|---|

1 | 1-gon | 213 |

2 | Errichto | 189 |

3 | awoo | 188 |

4 | rng_58 | 187 |

5 | SecondThread | 186 |

6 | Um_nik | 179 |

7 | Ashishgup | 177 |

8 | maroonrk | 172 |

8 | vovuh | 172 |

8 | antontrygubO_o | 172 |

Tutorial is loading...

Tutorial is loading...

Tutorial is loading...

Tutorial is loading...

Tutorial is loading...

Tutorial of Codeforces Round #533 (Div. 2)

↑

↓

Codeforces (c) Copyright 2010-2021 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Apr/15/2021 18:13:44 (f2).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|

Can someone explain me how the complexity in E becomes 2^(m/2)

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.Thanks

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.

The Editorial is so fast!

One of the best contests I wrote, interesting & balanced problems and a fast editorial!

Problem B alternate ideas!!

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.

Thanks!!!

you need to find the maximum occurrence of a substring with length k where every letter is same

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.

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?

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

There still won't be bipartite graph tho.

I don't think this will work. A name needs to be chosen

everytime for it to be happy.This is what I overlooked. Thanks for letting me know! :)

But in Bipartite Matching you can manipulate the already assigned match, but here can you ?

Thanks, for the great round.

It wasn't ABCD were just pure implementation and E has very much similarity with https://codeforces.com/blog/entry/4623

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

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.

Yes I am trying to make counter tests for it, thanks for bringing it out :D

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.

Are you planning to redo the system tests?

I suppose it can be done only in archive, the contest results are final.

I like your game very much. Thank you very much.

A Player from China

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 — количество друзей. Или я где-то ошибся?

This solution is incorrect, here is a countertest. Your solution outputs 2, while it's possible to satisfy 3 friends (b, c and d).

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

testOk, were added testcase 30. But this problem can solve by random))

Can we solve problem E with other way(solution with no graphs)?

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

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.

Submission 48636151

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.

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

You can still solve it without graphs, it will just not be in polynomial time...

Hi, can someone tell me what happened here ?

gcc-14 WA 48634660

gcc-11 AC 48641033

(Codes are identical)

You haven't initialised a variable

`pr`

so that a comparison`sol != pr`

ends up with undefined behaviour.Tnx :D

Hello there :D Concerning problem D

https://codeforces.com/contest/1105/submission/48642557 https://codeforces.com/contest/1105/submission/48642301

I 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 this

while(ok) { ok = 0; for(int i = 1 ; i <= p ; i++) if(v[i].size())

ok |= bfs(i); }

thanks in advance

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

wow, that is very very strange...

This is not strange. All because u create a queue many times, i.e. call the constructor every time. It takes a long time.

Thank you very much

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

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

What am I missing in E? Lets say that between first two borders there are friends

AandBand they are connected by edge. Lets say that between second and third border there are also friendsAandBand they are connected too. MIS of given graph is 2 but answer is 1 as far as I know, so where am I wrong?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.

Oh so we make 1 graph that contains edges based on all gaps, and not more graphs for each gap. Okay, thank you :)

Why isn't the anwser 2?

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

oh, i though that a friend were happy if he saw his handle at least once lol

No, he has to see his name every time

I was trying problem C by stars and bars method of combinatorics. DP didn't occur to me.

Problem C can be solved in O(logn) and memorisation.

How?

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

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.

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.

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.

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.

Its like counting a^b .

slappy Can you share your code ?

48637454

Tnx :D

well written code. easy to understand.

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

.

Thank you for this contest <3, I became pupil again :p

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 13

also 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/48640359

EDIT: I implemented a solution using collections.deque but still gets TLE, does anyone have any idea how to get AC with python?

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.

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

Can Someone Help me in D problem ? I am getting Memory Limit Exceeded on test 20

My submission — https://codeforces.com/contest/1105/submission/48646487

You forget to pop from the queue :)

Lol.. Then I should got TLE bro xD

I don't know try it maybe it works.

Please, can someone explain to me test 5 in problem D?

Test: #54 4 2

1 1000000000

....

....

..2.

...1

Answer of Judge3 13

I think it should be5 11

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

..11

then the second player moves to all not-occupied cells and the grid looks like this

2222

2222

2221

2211

hope you understand this and sorry for my bad english..

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

onlyhisorigincell.Can someone elaborate on Problem C? TIA

Yes if someone can further explain it it would be really nice.

yes it would be helpful, i am also not able to figure it out

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 =`j`

The base case is dp[1][0] = m0, dp[1][1] = m1, dp[1][2] = m2

Let'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

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

plzz can you explain why you have multiplied dp[i-1][0] with m0 (and similar for others)because order of array matters

what do you mean "order of array matters"?

great

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

now 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 = 8

lets 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))/3

and 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.

Could you elaborate the last paragraph? Could you also post a link to the code? Thanks

Here is the link to my code: https://codeforces.com/contest/1105/submission/48648308

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

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

Dance Link can fuck E. Believe me.Very fast.

Can you put your code here?

https://codeforces.com/contest/1105/submission/48645958

Can you explain how you applied dancing links to solve it?

Can someone explain 1105-C?

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

Can someone please explain why my submission for D is giving TLE? I used BFS. https://codeforces.com/contest/1105/submission/48650058

This is a small test case where your code will give TLE think about why it gives TLE and how to fix it :)

Ah! Didn't consider the case when it's impossible to cover all empty cells. Thanks a lot!

You're welcome.

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

Can anyone explain why an algorithm like this one: 48645129 doesn't MLE? It seems to be storing 2

^{m}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 2^{m / 2}. Can anyone help?I think it is just that the test are weak. There surely are 2

^{m}states in the worst case.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.

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.

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".approach in submission 48651576 problem E. runs through all masks from 1 till 2^(m/2) (exclusive). and ran a loop to check that mask M contains nodes such that they are not neighbors to each other by going in another loop from 0 to m/2 (exclusive) and getting the or of all masks OM of these nodes (nodes are present in mask) neighbors if OM&M is positive then this mask is invalid otherwise its answer dp(m)=number of bits in M.

then i made bottom up building of dp such that dp(mask) is max(dp(mask),dp(submasks)) by turning one bit off at a time. and going in dp table (bottom up).

then go through masks of the remaining nodes [m/2, m[ and checking if they themselves are valid and getting the mask of their neighbors from [0, m/2[ and now maximize answer over dp(NOT(neighborMask)) + numberOfBitsInThisMask. where NOT(a) is inverse of its bits.

Is that a wrong approach, coz I got wa on 11 and spent enough time to debug.

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.

Good tutorial and contest, but I am very weak,,,became pupil...QAQ

48662260

Why does 0-1 BFS + dp WA15 for D?

https://codeforces.com/contest/1105/submission/48663062.

https://codeforces.com/contest/1105/submission/48662882.

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?

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

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.

48677210

I changed about my code a bit to fix what you said, but I'm still getting WA15

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.

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.

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 .

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 # . . . # .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

Use C++17 you will get Ac.

i tried and it didn't work

Oh no.Sorry for I can't find the mistake.

Can You Help me why I am getting TLE on test 20 https://codeforces.com/contest/1105/submission/48682380

Thanks in advance

tutu

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

Problem B: You didn't mention that string will be only of lower case alphabets in problem.

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 ?

Can you please help me.. I getting TLE on test 20 in problem D.

Code https://codeforces.com/contest/1105/submission/48682380

My Submission

My 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?

Yours approach is greedy. Check this case:

Right ans would be 1, but according to your approach it's 2.

[ 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?

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.

Can Anyone please help me.. I getting TLE on test 20 in problem D.

Code https://codeforces.com/contest/1105/submission/48682380

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

I solved. The problem was the choice of the queue.

Outputs 9 3 instead of 10 2

Thanks for your case. It helps me a lot. :P

btw, how do you construct this case?

Actually I search for all the examples for problem D in this post and the original post. :(

Thanks :P

It would be really helpful if you say how you fixed this problem :)

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

Put some "printf(i, count[i])" in your code and look how your count is growing

Can E be solved in

O(2^{m / 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.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?

Imagine each friend as a bit and

nbr[i] is a value having set bits only in positions corresponding to friends adjacent to theithfriend. Letdp[j] be the maximum independent set size, where its participants have their corresponding bits set inj.How to calculate

dp[j]? iterate on every set bit ofj, let the current set bit in loop be thekthbit, ifnbr[k] has no intersection withj(nbr[k]&j= 0), then continue looping normally, else, you have either to remove thekthfriend or remove the intersection (nbr[k]&j) fromj, so dp[j] will bemax(dp[x],dp[y]), wherexisjafter clearing thekthfriend bit,yisjafter clearing the intersection bits. If the loop finished without entering theelsebranch,dp[j] will just be count of set bits in j.Assume we calculated

dp1 for the most significant bits anddp2 for the least significant bits, for every possible maskm1 indp1, make maskm2 fordp2, where thekthbit inm2 is set only ifnbr[k]&m1 = 0 (no intersection withm1). And setans=max(ans,dp[m1] +dp[m2]).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?

If you chose a specific

dp2's maskm2 based on a specificdp1's maskm1 which imposed clearing some bits inm2 because the friends representing these bits have neighbors which have their bits set inm1, then even ifdp1[m1] was a number less than set bits count inm1, you will reach the optimal answer anyway. Because eventually you will reach thatm1 wheredp[m1] = set bits count inm1.thanks a lot got it accepted:D

can anyone explain problem C in more detail ?

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=0

previous=1 , current=2

previous=2 , current=1

for 1-> previous=0 , current=1 ... and so on

thank you <3

How to solve A if the constraints over Ai were large ?

EDIT — Here is the ternary search solution

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

I see. Good point. Do you have a proof of unimodality ?

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.

Proof ?

By median definition. And +/-1 is cause of problem statement.

@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/48716141

Solution 2 (verdict: AC): http://codeforces.com/contest/1105/submission/48716349

As 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!

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.

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

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 functionT(k) that is a bound on the time to compute`solve(mask)`

if`mask`

haskset bits. In the first case mentioned above (the first node has no neighbors in`mask`

), we only do one recursive call, soT(k) ≥T(k- 1). Otherwise, we have to do two recursive calls: one on a set of sizek- 1 and one on a set of size at mostk- 2 (this is because we removed at least one neighbor from`mask`

). SoT(k) ≥T(k- 1) +T(k- 2). This is the worse bound, so let's takeT(k) =T(k- 1) +T(k- 2) to get our bound on the running time. With base cases ofT(0) =T(1) = 1, we see thatT(k) is thekth Fibonacci number. That is,T(k) ≈ 1.618^{k}. And since 1.618^{40}≈ 10^{8}, this should run in time.Accepted submission: https://codeforces.com/contest/1105/submission/48864093

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

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)

https://codeforces.com/contest/1105/submission/69937257

Why am I getting TLE in the 45th test?

1105C — Ayoub and Lost Array

Is best explained in this link: https://www.youtube.com/watch?v=eGCDdccErmQ

The idea of taking 3k,3K+1,3K+2 was very interesting.. thanks