Warawreh's blog

Codeforces Round #533 (Div. 2) — Editorial

By Warawreh, 6 years ago, In English
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
  • Vote: I like it
  • +207
  • Vote: I do not like it

Comments Comments (142)
| Write comment?
»
6 years ago, # |
  Vote: I like it +16 Vote: I do not like it

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

→ Reply
  • »
    »
    6 years ago, # ^ |
    ← Rev. 2   Vote: I like it +14 Vote: I do not like it

    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.

    → Reply
    • »
      »
      »
      6 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Thanks

      → Reply
    • »
      »
      »
      6 years ago, # ^ |
        Vote: I like it +5 Vote: I do not like it

      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.

      → Reply
»
6 years ago, # |
  Vote: I like it +11 Vote: I do not like it

The Editorial is so fast!

→ Reply
»
6 years ago, # |
  Vote: I like it +32 Vote: I do not like it

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

→ Reply
»
6 years ago, # |
← Rev. 3   Vote: I like it 0 Vote: I do not like it

Problem B alternate ideas!!

→ Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

    → Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

    → Reply
»
6 years ago, # |
  Vote: I like it +3 Vote: I do not like it

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.

→ Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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?

    → Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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

    → Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it +21 Vote: I do not like it

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

    → Reply
    • »
      »
      »
      6 years ago, # ^ |
        Vote: I like it +3 Vote: I do not like it

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

      → Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

    → Reply
»
6 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

Thanks, for the great round.

→ Reply
»
6 years ago, # |
  Vote: I like it +11 Vote: I do not like it

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

→ Reply
  • »
    »
    6 years ago, # ^ |
    ← Rev. 2   Vote: I like it +1 Vote: I do not like it

    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.

    → Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it -12 Vote: I do not like it

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

    → Reply
    • »
      »
      »
      6 years ago, # ^ |
      ← Rev. 5   Vote: I like it +16 Vote: I do not like it

      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.

      → Reply
    • »
      »
      »
      6 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Are you planning to redo the system tests?

      → Reply
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

A Player from China

→ Reply
»
6 years ago, # |
  Vote: I like it +12 Vote: I do not like it

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

→ Reply
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it +2 Vote: I do not like it

    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

    → Reply
    • »
      »
      »
      6 years ago, # ^ |
      ← Rev. 2   Vote: I like it 0 Vote: I do not like it

      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

      → Reply
    • »
      »
      »
      6 years ago, # ^ |
        Vote: I like it -6 Vote: I do not like it

      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.

      → Reply
      • »
        »
        »
        »
        6 years ago, # ^ |
          Vote: I like it +6 Vote: I do not like it

        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

        → Reply
    • »
      »
      »
      6 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

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

      → Reply
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Hi, can someone tell me what happened here ?

gcc-14 WA 48634660

gcc-11 AC 48641033

(Codes are identical)

→ Reply
  • »
    »
    6 years ago, # ^ |
    ← Rev. 2   Vote: I like it +2 Vote: I do not like it

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

    → Reply
»
6 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

Hello there :D Concerning problem D

https://codeforces.net/contest/1105/submission/48642557 https://codeforces.net/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

→ Reply
  • »
    »
    6 years ago, # ^ |
    ← Rev. 2   Vote: I like it +6 Vote: I do not like it

    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

    → Reply
    • »
      »
      »
      6 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      wow, that is very very strange...

      → Reply
    • »
      »
      »
      6 years ago, # ^ |
        Vote: I like it +3 Vote: I do not like it

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

      → Reply
    • »
      »
      »
      6 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Thank you very much

      → Reply
»
6 years ago, # |
← Rev. 3   Vote: I like it 0 Vote: I do not like it

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.net/contest/1105/submission/48643495

→ Reply
  • »
    »
    6 years ago, # ^ |
    ← Rev. 4   Vote: I like it 0 Vote: I do not like it

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

    → Reply
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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?

→ Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

    → Reply
    • »
      »
      »
      6 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

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

      → Reply
      • »
        »
        »
        »
        6 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it 
        1
2 a
2 b
1
2 a
2 b

        Why isn't the anwser 2?

        → Reply
        • »
          »
          »
          »
          »
          6 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          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

          → Reply
          • »
            »
            »
            »
            »
            »
            6 years ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

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

            → Reply
            • »
              »
              »
              »
              »
              »
              »
              6 years ago, # ^ |
                Vote: I like it 0 Vote: I do not like it

              No, he has to see his name every time

              → Reply
»
6 years ago, # |
← Rev. 2   Vote: I like it +2 Vote: I do not like it

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

→ Reply
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    How?

    → Reply
    • »
      »
      »
      6 years ago, # ^ |
      ← Rev. 4   Vote: I like it +15 Vote: I do not like it

      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.

      → Reply
»
6 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

.

→ Reply
»
6 years ago, # |
  Vote: I like it +3 Vote: I do not like it

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

→ Reply
»
6 years ago, # |
← Rev. 2   Vote: I like it +6 Vote: I do not like it

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.net/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?

→ Reply
  • »
    »
    6 years ago, # ^ |
    ← Rev. 3   Vote: I like it +12 Vote: I do not like it

    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.

    → Reply
    • »
      »
      »
      6 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

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

      → Reply
»
6 years ago, # |
← Rev. 3   Vote: I like it +1 Vote: I do not like it

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

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

→ Reply
»
6 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

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

Test: #5
Answer of Judge
I think it should be
→ Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it +4 Vote: I do not like it

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

    → Reply
    • »
      »
      »
      6 years ago, # ^ |
      ← Rev. 3   Vote: I like it +1 Vote: I do not like it

      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.

      → Reply
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Can someone elaborate on Problem C? TIA

→ Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

    → Reply
  • »
    »
    6 years ago, # ^ |
    ← Rev. 2   Vote: I like it +7 Vote: I do not like it

    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

    → Reply
    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

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

      → Reply
      • »
        »
        »
        »
        4 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        what do you mean "order of array matters"?

        → Reply
    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      great

      → Reply
  • »
    »
    6 years ago, # ^ |
    ← Rev. 2   Vote: I like it +5 Vote: I do not like it

    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.

    → Reply
    • »
      »
      »
      6 years ago, # ^ |
      ← Rev. 2   Vote: I like it 0 Vote: I do not like it

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

      → Reply
      • »
        »
        »
        »
        6 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

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

        → Reply
»
6 years ago, # |
  Vote: I like it +14 Vote: I do not like it

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

→ Reply
»
6 years ago, # |
  Vote: I like it +3 Vote: I do not like it

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

→ Reply
»
6 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

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

→ Reply
  • »
    »
    6 years ago, # ^ |
    ← Rev. 3   Vote: I like it +3 Vote: I do not like it

    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..
    → Reply
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
6 years ago, # |
  Vote: I like it +5 Vote: I do not like it

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?

→ Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it +8 Vote: I do not like it

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

    → Reply
»
6 years ago, # |
← Rev. 3   Vote: I like it +10 Vote: I do not like it

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.

→ Reply
»
6 years ago, # |
← Rev. 2   Vote: I like it +19 Vote: I do not like it

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.

→ Reply
»
6 years ago, # |
  Vote: I like it +3 Vote: I do not like it

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

→ Reply
»
6 years ago, # |
← Rev. 3   Vote: I like it 0 Vote: I do not like it

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.

→ Reply
»
6 years ago, # |
  Vote: I like it +9 Vote: I do not like it

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.

→ Reply
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

48662260

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

→ Reply
  • »
    »
    6 years ago, # ^ |
    ← Rev. 2   Vote: I like it +6 Vote: I do not like it

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

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

    → Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    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.

    → Reply
    • »
      »
      »
      6 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      48677210

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

      → Reply
      • »
        »
        »
        »
        6 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        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.

        → Reply
»
6 years ago, # |
  Vote: I like it +1 Vote: I do not like it

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.

→ Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it +8 Vote: I do not like it

    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 .

    → Reply
    • »
      »
      »
      6 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

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

      → Reply
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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.net/contest/1105/submission/48635565

→ Reply
»
6 years ago, # |
  Vote: I like it +3 Vote: I do not like it

tutu

→ Reply
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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 ?

→ Reply
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

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

→ Reply
»
6 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

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

→ Reply
  • »
    »
    6 years ago, # ^ |
    ← Rev. 2   Vote: I like it +4 Vote: I do not like it

    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

    → Reply
    • »
      »
      »
      6 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

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

      btw, how do you construct this case?

      → Reply
    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

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

      → Reply
»
6 years ago, # |
← Rev. 3   Vote: I like it 0 Vote: I do not like it

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

→ Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

    → Reply
»
6 years ago, # |
  Vote: I like it +8 Vote: I do not like it

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.

→ Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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?

    → Reply
    • »
      »
      »
      6 years ago, # ^ |
        Vote: I like it +8 Vote: I do not like it

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

      → Reply
      • »
        »
        »
        »
        6 years ago, # ^ |
        ← Rev. 2   Vote: I like it 0 Vote: I do not like it

        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?

        → Reply
        • »
          »
          »
          »
          »
          6 years ago, # ^ |
            Vote: I like it +3 Vote: I do not like it

          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.

          → Reply
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

can anyone explain problem C in more detail ?

→ Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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

    → Reply
»
6 years ago, # |
← Rev. 2   Vote: I like it +5 Vote: I do not like it

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

EDIT — Here is the ternary search solution

→ Reply
  • »
    »
    6 years ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

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

    → Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

    → Reply
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

@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.net/contest/1105/submission/48716141

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

→ Reply
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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.

→ Reply
»
6 years ago, # |
  Vote: I like it +13 Vote: I do not like it

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.net/contest/1105/submission/48864093

→ Reply
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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.net/contest/1105/submission/50567716 (Comments added to every line of code for better understanding)

→ Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
18 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Anyone can help with Problem C?

I think my mistake is in the cnt() function though i dont know why it is incorrect

[submission:https://codeforces.net/contest/1105/submission/212810915]

→ Reply