Codeforces Round #533 (Div. 2) — Editorial

6 лет назад, # ^ |

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.

→ Ответить

Cain

6 лет назад, # |

+11

The Editorial is so fast!

→ Ответить

phyzzmat

6 лет назад, # |

+32

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

→ Ответить

kbagoli1999

6 лет назад, # |

← Rev. 3 →

Problem B alternate ideas!!

→ Ответить

Rishabhj

6 лет назад, # ^ |

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.

→ Ответить

kbagoli1999

6 лет назад, # ^ |

Thanks!!!

→ Ответить

sabertooth

6 лет назад, # ^ |

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

→ Ответить

Wielomian

6 лет назад, # |

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.

→ Ответить

Death_Scythe

6 лет назад, # ^ |

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?

→ Ответить

Wielomian

6 лет назад, # ^ |

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

→ Ответить

AwakeAnay

6 лет назад, # ^ |

There still won't be bipartite graph tho.

→ Ответить

T1duS

6 лет назад, # ^ |

+21

I don't think this will work. A name needs to be chosen every time for it to be happy.

→ Ответить

Wielomian

6 лет назад, # ^ |

This is what I overlooked. Thanks for letting me know! :)

→ Ответить

boltUsain

6 лет назад, # ^ |

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

→ Ответить

Undying

6 лет назад, # |

← Rev. 2 →

Thanks, for the great round.

→ Ответить

soul_voyage

6 лет назад, # ^ |

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

→ Ответить

6 лет назад, # |

+11

Should a randomized solution pass for E? Can anyone figure out a chance of success. Can use this algo for reference: https://mirror.codeforces.com/contest/1105/submission/48630631

→ Ответить

LLI_E_P_JI_O_K

6 лет назад, # ^ |

← Rev. 2 →

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.

→ Ответить

Warawreh

6 лет назад, # ^ |

-12

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

→ Ответить

LLI_E_P_JI_O_K

6 лет назад, # ^ |

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

→ Ответить

6 лет назад, # ^ |

Are you planning to redo the system tests?

→ Ответить

LLI_E_P_JI_O_K

6 лет назад, # ^ |

← Rev. 2 →

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

→ Ответить

QieziMin

6 лет назад, # |

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

A Player from China

→ Ответить

wery0

6 лет назад, # |

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

→ Ответить

BledDest

6 лет назад, # ^ |

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

→ Ответить

yassin_

6 лет назад, # ^ |

← Rev. 3 →

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

test

→ Ответить

wery0

6 лет назад, # ^ |

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

→ Ответить

orangeorange

6 лет назад, # |

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

→ Ответить

6 лет назад, # ^ |

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

→ Ответить

himank

6 лет назад, # ^ |

← Rev. 2 →

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

→ Ответить

funtik

6 лет назад, # ^ |

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

→ Ответить

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

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

→ Ответить

WolfBlue

6 лет назад, # ^ |

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

→ Ответить

MalivuK

6 лет назад, # |

Hi, can someone tell me what happened here ?

gcc-14 WA 48634660

gcc-11 AC 48641033

(Codes are identical)

→ Ответить

denison7111

6 лет назад, # ^ |

← Rev. 2 →

You haven't initialised a variable pr so that a comparison sol != pr ends up with undefined behaviour.

→ Ответить

Solo_Player.

6 лет назад, # |

← Rev. 2 →

Hello there :D Concerning problem D

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

→ Ответить

TheRedLegend

6 лет назад, # ^ |

← Rev. 2 →

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

→ Ответить

Djok216

6 лет назад, # ^ |

wow, that is very very strange...

→ Ответить

dasfex

6 лет назад, # ^ |

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

→ Ответить

Solo_Player.

6 лет назад, # ^ |

Thank you very much

→ Ответить

reza

6 лет назад, # |

← Rev. 3 →

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://mirror.codeforces.com/contest/1105/submission/48643495

→ Ответить

6 лет назад, # ^ |

← Rev. 4 →

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

→ Ответить

6 лет назад, # |

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?

→ Ответить

denison7111

6 лет назад, # ^ |

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.

→ Ответить

6 лет назад, # ^ |

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

→ Ответить

tantam75

6 лет назад, # ^ |

1
2 a
2 b
1
2 a
2 b

Why isn't the anwser 2?

→ Ответить

6 лет назад, # ^ |

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

→ Ответить

tantam75

6 лет назад, # ^ |

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

→ Ответить

6 лет назад, # ^ |

No, he has to see his name every time

→ Ответить

saint_coder

6 лет назад, # |

← Rev. 2 →

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

→ Ответить

6 лет назад, # |

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

→ Ответить

index_

6 лет назад, # ^ |

How?

→ Ответить

6 лет назад, # ^ |

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

→ Ответить

ahshafi

6 лет назад, # ^ |

Its like counting a^b .

→ Ответить

ChevishaUchiha

6 лет назад, # ^ |

slappy Can you share your code ?

→ Ответить

6 лет назад, # ^ |

48637454

→ Ответить

Storm_Stark

6 лет назад, # |

← Rev. 2 →

→ Ответить

Silver_Lining

6 лет назад, # |

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

→ Ответить

alessandrosolbiati

6 лет назад, # |

← Rev. 2 →

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://mirror.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?

→ Ответить

pajenegod

6 лет назад, # ^ |

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

→ Ответить

alessandrosolbiati

6 лет назад, # ^ |

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

→ Ответить

6 лет назад, # |

← Rev. 3 →

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

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

→ Ответить

6 лет назад, # ^ |

You forget to pop from the queue :)

→ Ответить

6 лет назад, # ^ |

Lol.. Then I should got TLE bro xD

→ Ответить

6 лет назад, # ^ |

I don't know try it maybe it works.

→ Ответить

aboAdnan

6 лет назад, # |

← Rev. 2 →

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

Test: #5

Answer of Judge

I think it should be

→ Ответить

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

6 лет назад, # ^ |

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

2221

2211

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

→ Ответить

aboAdnan

6 лет назад, # ^ |

← Rev. 3 →

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.

→ Ответить

Rishabhj

6 лет назад, # |

Can someone elaborate on Problem C? TIA

→ Ответить

youssefbou62

6 лет назад, # ^ |

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

→ Ответить

mini4141

6 лет назад, # ^ |

← Rev. 2 →

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

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

→ Ответить

Prajwal_

4 года назад, # ^ |

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

→ Ответить

mini4141

4 года назад, # ^ |

what do you mean "order of array matters"?

→ Ответить

tanmax

4 года назад, # ^ |

great

→ Ответить

Sixpathsguy

6 лет назад, # ^ |

← Rev. 2 →

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.

→ Ответить

zmagzhanz

6 лет назад, # ^ |

← Rev. 2 →

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

→ Ответить

Sixpathsguy

6 лет назад, # ^ |

Here is the link to my code: https://mirror.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)

→ Ответить

Moysenko

6 лет назад, # |

← Rev. 2 →

Может ли кто-нибудь объяснить, почему мое решение по E зашло, причем так быстро? 48633102

Мое решение: Я строил граф, где между двумя друзьями было ребро, если они не могли быть счастливы одновременно, затем делил его на компоненты связности, а потом по каждой компоненте отдельно запускал перебор. В переборе я смотрел на текущий набор вершин (изначально брались все в компоненте), если была какая-то пара вершин, соединенных ребром, то я брал наилучший результат от двух рекурентных запусков

от такого же набора вершин, только без одной из этой пары (обозначим ее за А)
от такого же набора вершин, только без всех, соединенных ребром с А

Если никакая пара вершин текущего набора не соединена ребом, то этот набор нас вполне устраивает, и я возвращаю его размер. Результаты переборов для всех компонент я складывал, очевидно, это и был ответ. Вот только я вообще не понимаю, почему это решение работает за быстро. Интуитивно кажется, что существует антитест за 2^m.

→ Ответить

Moysenko

6 лет назад, # ^ |

47th-draganov подсказал, что вот этот алгоритм

→ Ответить

ILoveBitches

6 лет назад, # |

+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

→ Ответить

newgate

6 лет назад, # |

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

→ Ответить

bzh_2

6 лет назад, # ^ |

Can you put your code here?

→ Ответить

newgate

6 лет назад, # ^ |

→ Ответить

Bassel

6 лет назад, # ^ |

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

→ Ответить

frontseatastronaut

6 лет назад, # |

← Rev. 2 →

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

→ Ответить

6 лет назад, # ^ |

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

→ Ответить

frontseatastronaut

6 лет назад, # ^ |

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

→ Ответить

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

6 лет назад, # ^ |

You're welcome.

→ Ответить

DeerInForestovo

6 лет назад, # |

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

→ Ответить

ankeet

6 лет назад, # |

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?

→ Ответить

RobeZH

6 лет назад, # ^ |

I think it is just that the test are weak. There surely are 2^m states in the worst case.

→ Ответить

simem

6 лет назад, # |

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

→ Ответить

bzh_2

6 лет назад, # |

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

→ Ответить

RobeZH

6 лет назад, # |

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

→ Ответить

Odin-

6 лет назад, # |

← Rev. 3 →

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.

→ Ответить

bzh

6 лет назад, # |

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.

→ Ответить

BRCode

6 лет назад, # |

48662260

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

→ Ответить

bitetheDDDDt

6 лет назад, # ^ |

← Rev. 2 →

https://mirror.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?

→ Ответить

kozima

6 лет назад, # ^ |

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.

→ Ответить

BRCode

6 лет назад, # ^ |

48677210

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

→ Ответить

kozima

6 лет назад, # ^ |

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.

→ Ответить

crypt1k

6 лет назад, # |

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.

→ Ответить

stringray

6 лет назад, # ^ |

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 .

→ Ответить

crypt1k

6 лет назад, # ^ |

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

→ Ответить

Pankin

6 лет назад, # |

Can anyone help with problem D? I used bfs and have the same complexity but got a TLE somehow... Here's my submission: https://mirror.codeforces.com/contest/1105/submission/48635565

→ Ответить

MagicSpark

6 лет назад, # ^ |

Use C++17 you will get Ac.

→ Ответить

Pankin

6 лет назад, # ^ |

i tried and it didn't work

→ Ответить

MagicSpark

6 лет назад, # ^ |

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

→ Ответить

6 лет назад, # ^ |

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

→ Ответить

HMS_Warspite

6 лет назад, # |

tutu

→ Ответить

MagicSpark

6 лет назад, # |

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

→ Ответить

AK18

6 лет назад, # |

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 ?

→ Ответить

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

6 лет назад, # ^ |

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

→ Ответить

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

6 лет назад, # |

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

→ Ответить

shnoh

6 лет назад, # |

← Rev. 2 →

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

→ Ответить

shnoh

6 лет назад, # ^ |

← Rev. 2 →

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

→ Ответить

liuxueyang

6 лет назад, # ^ |

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

btw, how do you construct this case?

→ Ответить

shnoh

6 лет назад, # ^ |

← Rev. 2 →

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

→ Ответить

vrishinvv

5 лет назад, # ^ |

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

→ Ответить

linkRs

6 лет назад, # |

← Rev. 3 →

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

→ Ответить

6 лет назад, # ^ |

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

→ Ответить

mohamedeltair

6 лет назад, # |

Can E be solved in O(2^m / 2)? I could solve it in $\text{[math]}$ 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.

→ Ответить

6 лет назад, # ^ |

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?

→ Ответить

mohamedeltair

6 лет назад, # ^ |

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 $\text{[math]}$ bits and dp2 for the least significant $\text{[math]}$ 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]).

→ Ответить

6 лет назад, # ^ |

← Rev. 2 →

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?

→ Ответить

mohamedeltair

6 лет назад, # ^ |

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.

→ Ответить

6 лет назад, # ^ |

thanks a lot got it accepted:D

→ Ответить

Ahmed__mohamed

6 лет назад, # |

can anyone explain problem C in more detail ?

→ Ответить

6 лет назад, # ^ |

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

→ Ответить

6 лет назад, # |

← Rev. 2 →

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

EDIT — Here is the ternary search solution

→ Ответить

6 лет назад, # ^ |

← Rev. 2 →

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

→ Ответить

6 лет назад, # ^ |

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

→ Ответить

6 лет назад, # ^ |

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.

→ Ответить

6 лет назад, # ^ |

Proof ?

→ Ответить

6 лет назад, # ^ |

← Rev. 2 →

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

→ Ответить

Psp_98

6 лет назад, # |

@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://mirror.codeforces.com/contest/1105/submission/48716141

Solution 2 (verdict: AC): http://mirror.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!

→ Ответить