Пожалуйста, подпишитесь на официальный канал Codeforces в Telegram по ссылке: https://t.me/codeforces_official. ×

Блог пользователя gritukan

Автор gritukan, история, 9 месяцев назад, По-английски,

Besides the editorial we prepared some challenges for you.

Tutorial is loading...

(Idea — MikeMirzayanov, developing — fcspartakm)

Tutorial is loading...

(Idea — _meshanya_, developing — Zlobober, KAN)

Tutorial is loading...

(Idea — Zlobober, developing — ch_egor)

Tutorial is loading...

(Idea and developng — Sender)

Tutorial is loading...

(Idea — V--o_o--V, developer — Flyrise)

Tutorial is loading...

(Idea — Sender, developer — _kun_)

Tutorial is loading...

(Idea — Zlobober, developer — malcolm)

Tutorial is loading...

(Idea and developng — gritukan)

Разбор задач Codeforces Round #469 (Div. 1)
Разбор задач Codeforces Round #469 (Div. 2)
 
 
 
 
  • Проголосовать: нравится  
  • +99
  • Проголосовать: не нравится  

»
9 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Auto comment: topic has been updated by gritukan (previous revision, new revision, compare).

»
9 месяцев назад, # |
  Проголосовать: нравится +2 Проголосовать: не нравится

Auto comment: topic has been updated by gritukan (previous revision, new revision, compare).

»
9 месяцев назад, # |
  Проголосовать: нравится +7 Проголосовать: не нравится

Auto comment: topic has been updated by gritukan (previous revision, new revision, compare).

»
9 месяцев назад, # |
  Проголосовать: нравится +57 Проголосовать: не нравится

"BONUS (medium): Given graph is not properly colored, but you don't have to minimize size of the set. Can you solve it?"

Yes, that's what I solved yesterday before solving actual problem xD

»
9 месяцев назад, # |
  Проголосовать: нравится +34 Проголосовать: не нравится

"BONUS (hard): Find answer minimizing number of subsequences."

Sorry if I'm missing something but isn't number of subsequences always equal to number of 0s — number of 1s, as each subsequence chosen increases number of 0s — number of 1s by 1.

»
9 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

The two bonuses for "Binary cards" are the same, should they be?

  • »
    »
    9 месяцев назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Oops, my bad. It should be n ≤ 105 in the second challengle. I'll fix it now.

»
9 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Please help in ques C, why am i getting TLE

http://codeforces.com/contest/950/submission/36191394

Thanks

»
9 месяцев назад, # |
Rev. 4   Проголосовать: нравится 0 Проголосовать: не нравится

"BONUS (medium): Given graph is not properly colored, but you don't have to minimize size of the set. Can you solve it?"

If a person stores his data at computers x and y and initially colorx = colory then if x is in the set we choose then y won't. Similarly if y is in the set then x won't. This is NAND 2-Sat clause. Additionally like in the statement we add directed edges for the cases — they are equivalent to implications.

Well now for the medium problem we simply need to find a valid 2-SAT solution with at least 1 variable true.

Well we simply try fixing all possible variables to be true and then check for a solution. This way we achieve . Probably there is a faster way to do it but still this should work.

The main reason for this comment is because I think I have a solution for the hard version. Not sure it's correct tho.

So let's assign costs to the vertices. We assign a cost of -1 to all variables x and a cost of 0 to . Now we search for a 2-SAT solution of the maximum cost with at least on 1 set to the original variables. Well this should be possible to be solved with the Maximum closure algorithm.

We again try fixing every variable and then running the algorithm.

The overall complexity will be .

UPDATE: it's wrong.

  • »
    »
    9 месяцев назад, # ^ |
    Rev. 2   Проголосовать: нравится +6 Проголосовать: не нравится

    Your solution for medium version is correct, of course. There are several ways of optimizing it to O(n + m) (for example by considering two cases), however it's not very interesting.

    I'm not completely sure about your solution for hard version, because I'm not sure if there are some correspondences between 2-SAT solutions and graph's closures as closure doesn't give any restrictions on taking both x and !x or taking none of them.

    • »
      »
      »
      9 месяцев назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      Yeah you are right. I forgot the fact that in graph closures you don't have a restriction about taking x and !x.

»
9 месяцев назад, # |
  Проголосовать: нравится -13 Проголосовать: не нравится

can some one plz tell me why my code is giving wrong answer for test 8 in Div 1 C. https://ide.geeksforgeeks.org/jwqoTyGzAy

»
9 месяцев назад, # |
  Проголосовать: нравится -10 Проголосовать: не нравится

Can anyone tell me how to maintain the list of zero's and almost zero's efficiently in the problem 949A-Zebras?

»
9 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

In F, what's the exact expected number of intersections we need to check, without O-notation? I solved the problem with a different random scheme, but had to const-optimise like crazy to be able to compute a sufficient number of intersection points. Since (2N)2 is approximately 27 million and computing one intersection + checking if it's valid requires a lot of operations, that 5s time limit is really tight. Even worse, with a non-deterministic solution, there's a non-zero chance of any solution having to check twice as many intersections on some test and getting TLE there.

I'm not surprised it has so few successful solutions to date and the only 2 solutions that passed pretests failed systests. Designing a solution that passes systests through anything but luck seems impossible (unless it's deterministic — does such a solution exist?).

»
9 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

It seems I have a solution for E that's linear in N and almost independent on (just through polylog).

The extra observation is that when we decide to use cards for the first k bits and skip the card for bit k + 1, we can shift each Ai by any number in a common fixed range [l, l + 2k) that contains 0 — the value of l can be chosen arbitrarily by setting the cards' signs. This shift needs to make each Ai divisible by 2k + 1, but since we can only shift by at most 2k - 1, the number we need to shift to is uniquely determined. This tells us a possible value of l for a given k (or that it doesn't exist).

This gives an obvious recursive, possibly exponential solution: try all possible k, shift each Ai and divide by 2k + 1, solve for this modified array recursively if it's possible to choose a valid l (stopping when everything is 0) and add k cards; choose the option that gives the fewest cards.

Now, intuition says we could take the first k that gives a valid l and set of shifts. I don't have proof this works, but I submitted it and got AC. (In fact, I got AC even with the possibly exponential solution. Idk if it can be hacked or the tests aren't strong enough?) Either way, since the recursion doesn't fork, this is clearly .

»
8 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

plzz provide correctness proof of 'Zebras' Div1A?

»
5 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

949A — Zebras is really badly written. Why? It asks us to find if it is possible to find a zebra sequence and if it is find how many ways. Now is it not given that there is any other property of those sequence, so for test input 0010100, the output 1 1 2 3 4 5 6 7 should work fine, because it satisfies the conditions, it is zebra and it a possible way to arrange the days, but jury doesn't accepts it. Don't know why. It is nowhere written in question that we have to do to other than finding a zebra sequence.