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

Автор cdkrot, история, 5 лет назад, перевод, По-русски

Авторы задач:

1138A - Sushi for Two, идея и разработка KAN

1138B - Circus, идея MikeMirzayanov, разработка cdkrot

1137A - Skyscrapers, идея Жюри олимпиады, разработка achulkov2

1137B - Camp Schedule, идея и разработка wrg0ababd

1137C - Museums Tour, идея ch_egor, разработка qoo2p5

1137D - Cooperative Game, идея и разработка mingaleg

1137E - Train Car Selection, идея и разработка Schemtschik

1137F - Matches Are Not a Child's Play , идея GlebsHP, разработка cdkrot

И, собственно, разбор:

Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
Разбор задач Codeforces Round 545 (Div. 1)
Разбор задач Codeforces Round 545 (Div. 2)
  • Проголосовать: нравится
  • +64
  • Проголосовать: не нравится

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

Can we do div2B in O(n)?

  • »
    »
    5 лет назад, # ^ |
      Проголосовать: нравится +5 Проголосовать: не нравится

    div2B can be solved in O(n) by directly construction, but it is complicate to code. In my code 51091100 I divide number of artists into a total of 3 cases. They are

    1. nb + nc = 0
    2. nb ≥ nc and na ≥ nb - nc
    3. nb ≥ nc and na < nb - nc

    and each case have 2 subcases, by constructing each subcase, they can be solved in O(n).

    I have tried my best to simplfy my code, but I still wonder if there are any simpler code that solve this problem in O(n)

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

      There is simple O(n) solution for this problem. We have a + b + c + d = n / 2 and b + c + 2d = nb + nd which can reduce to a - d = n / 2 - nb - nd which can brute force in O(n). See my submission 51116077.

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

        I see..

        For every value of a, we can find d from the reduced equation. Plugging the values in the given two equations, it's possible to uniquely find values of b and c.

        Well done!

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

        Thank You for sharing . I understood your concept. But can you please explain why you have used if(f>a[3]) condition ? What exactly is it's usage?

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

          $$$f$$$ is the total of numbers need to be printed after printing values from $$$q[1]$$$ and $$$q[2]$$$. If $$$f>a[3]$$$ means that we have to use values from both $$$q[3]$$$ and $$$q[4]$$$, otherwise the value from $$$q[3]$$$ is enough( There is else statement before return 0). It's just more convenient for me to implement this way. It's not necessary. Array $$$a[]$$$ is not necessary too since we can use $$$q[].size()$$$ instead. My submission is still a bit messy.

          • »
            »
            »
            »
            »
            »
            5 лет назад, # ^ |
            Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

            Why u have not used f>a[4] condition instead of f>a[3] condition? What is the correct use of f>a[3] condition i cannot understand it,could u please clear my doubt of not using f>a[4] condition or how can u say that if f<=a[3] then there is no need to look for q[4]?

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

              Both of them would be fine. :) From the fourth condition, we can guarantee that $$$f=\frac{n}{2}-x-i<=a[3]+a[4]$$$. If you understand the concept, you will know that we can choose any $$$f$$$ numbers from $$$q[3],q[4]$$$ which is always possible since $$$f<=a[3]+a[4]$$$.(if it passed four conditions in my code). Of course, $$$f>a[3]$$$ is not necessary. It’s just alternate way of implementation. Sorry if array $$$a[]$$$ makes you confused, you can think of it as $$$q[].size()$$$ instead. :)

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

        I have a o(n) solution where I first put all artists in second performance then count number of people who are good as acrobat : f, no artist in first performance yet so let no of people are good as clown : 0 so the delta is currently : f-0=f

        So to get an answer I need to move n/2 people to first performance to make delta : 0 and moving artists {1,0} or {0,1} makes delta-- and moving artists {1,1} makes delta-=2,{0,0} does nothing, so then I brute forced count of artists {1,1} to be taken and checked whether I can somehow get no ofArtist doing delta-- + no of artists doing delta-=2 + no of artists doing nothing<=n/2 & they are combined making the delta 0

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

    Hey, I am new here.

    Solved Div2B in O(1) logic. check my solution here.

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

Написал решение как у автора по задаче С тл 18

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

Div2B is a beautiful problem!

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

    since the recent rounds , division 2 has became slightly tougher than previous rounds and question are really much interesting and new . and also this one was moscow olympiad finals , so u can expect them to be good .

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

      From what I've understood in the announcement, div2 problems only were not part of the competition.

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

Typo in the tutorial of 1137D — Cooperative Game.

"Let r denote the distance from finish vertex to the one fast and slow met."

The r here should be x.

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

It seems too many points for Cooperative Game problem. It is just the search a cycle in a list. Very known problem!!

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

I have submited a solution of Museums Tour problem. It has Run Time Error on test 16 with try http://codeforces.com/contest/1138/submission/51133791. I very carefully look at my code and don't understand what problem is. Can tell me what to do to find error.

»
5 лет назад, # |
Rev. 4   Проголосовать: нравится +37 Проголосовать: не нравится

Another solution for F with treaps:

Lets have an implicit treap of the order of the vertices. Initially we build it in by simulating the burning process with heap or set.

"When" and "Compare" queries are now easily done in by simply finding the position of a given node (we keep pointers for each vertex id to its corresponding node in the treap).

For "Up" query we notice that we need to extract nodes on the path from the last updated vertex (initially assume this is n) to vertex u, then reverse their order and finally insert this new reversed subsequence to the end of the treap.

The problem is that we are not sure that these vertices are consecutive in the treap. But we can prove that the number of consecutive segments is amortized . The proof is similar to the one for link-cut tree's complexity. So now we have a straight forward by doing binary lifting and "when" query for finding the consecutive segments in the path. I had this solution during the onsite version, but unfortunately it's too slow. Fortunately we can do this finding in by going through the treap and keeping "next" and "prev" pointers in each treap node. This way the complexity is and without optimizations passes in ~3 sec.

Here is the code if someone is interested: 51142776

Also if I'm not mistaken by replacing the treap with splay tree, the complexity will become just .

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

If you use Google properly, you may solve div1D in one minute.

I don't think problems like this should appear in Codeforces.

I spent my time and effort just to find that my friends all used Google to solve it(they told me after the contest).

It's not fair.

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

Can someone describe solution for Div1C. "Museums Tour" in more detail? I can't understand why my submission got WA 79 on this problem.

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

HELP! Why I got RE on test 73? Submission: 51210282

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

I wonder why my div1C code gets either TLE18 using array analog link list to storage edges, or MLE16 using vectors :( TLE18: https://codeforces.com/contest/1137/submission/51214068 MLE16: https://codeforces.com/contest/1137/submission/51253929

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

simple o(n) solution for the B problem we need to check for 3 formulas

c= clown(10) b=both(11) no=none(00) a=acrobates(01) Aa=allacrobates Ab=allboth Ac=allclowns Aa=allacrobates
(1) c+a+b+no=n/2; // first condition all the numbers in the first half should be equal to n/2
(2) c+b=(Aa-a)+(Ab-b); c+2b+a=Aa+Ab; // second condition all the clowns should be equal to the acrobates
(3) no-b=n/2-Aa-Ab; //subtract the first equation from the second one to get the third one which is the one we will solve with 

step1 :
first of all use a loop to fix (no variable) in the third equation and find b as the right hand side is given in the third equation now we have no-b=(n/2-Aa-Ab) (no is now known as we used loop for it now find b and check for validation through the 3 equations and b>=0  and save no and b in temp variables then break the loop see the code for more details )  

step2: 
so after finding (b) variable in the same loop and checking if it's valid now use the second or the first formula (number 1 or 2 ) to find c+a as you now found (no and b variables ) put them in this formula  (c+2b+a=Aa+Ab;) for example to find (c+a) you can also use the first formula 

step3: 
after this use another loop (not nested)  (to fix a or to fix c loop in it as no variable in step 1) and to find the other variable a or c now you have (a and c and b and no variables) you have the four variables just print the answer check the link below for the solution link 

https://codeforces.com/contest/1138/submission/51265926 link to submission

  • »
    »
    5 лет назад, # ^ |
      Проголосовать: нравится +8 Проголосовать: не нравится

    why to many negative votes??!!1

    • »
      »
      »
      5 лет назад, # ^ |
      Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится

      Maybe because there has been another comment described this solution, your explanation is much more detailed though. (Although the last paragraph is really hard to read)

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

Can anyone tell me what's going wrong here?? Problem C Code

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

How to solve 1137B — Camp Schedule by hashes?

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

For DIV1 problem B,Why I WA on Test 71,using the fail array(may like Aho-Corasick automation)to calculate the max same prefix and suffix. What is the hacks in Test71. my code is as following https://codeforces.com/contest/1137/submission/51554217

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

For Div1.C,why do we have to compute in SCC? We can stop our tour in an arbitary city besides 1.

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

F :

At the beginning, burns out the leaf

this sentence doesn't really make sense, can you please fix it

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

Alternate simple $$$O(q\log{q})$$$ solution for div-1 E:

It's easy to see that only the leftmost car added in any add operation matters. Also, whenever type-1 operations are performed, the optimal car always becomes the leftmost (first one).

So now we can basically solve for all segments of queries between type-1 queries independently. Let's look at any such segment. It contains only type-2 and type-3 queries.

Let's maintain a set $$$S$$$ of cars which have the potential to be the optimal cars (min convienence value).

What will this set $$$S$$$ be like? It will contain the first car and leftmost cars added in some type 2 queries. Also, for any two adjacent elements $$$S_i$$$, $$$S_{i + 1}$$$ in this set (when sorted in ascending order of index), we will always have $$$convenience_i > convenience_{i + 1}$$$. (easy to see why this is true). The optimal car will always be the car with the greatest index in $$$S$$$.

How do we maintain this set?

  • Type-2 operations: simply add the leftmost added car into this set.
  • Type-3 operations: The main issue is that when we perform type-3 operations, the condition $$$convenience_i > convenience_{i + 1}$$$ might be violated for some $$$i$$$, as elements with greater index recieve greater increments.

    Observe that, for any $$$i$$$, whenever $$$i + 1$$$'th element is inserted, from that moment onwards $$$convenience_i > convenience_{i + 1}$$$ gets violated only when sum of $$$s$$$ across all type-3 queries from that moment becomes $$$\geq \left\lceil \frac{value_{S_i} - value_{S_{i + 1}}}{S_{i + 1} - S_i} \right\rceil$$$. It's easy to simplify this further and say that the $$${i, i + 1}$$$ pair will become invalid at time $$$T$$$ when $$$\sum_{t = 0}^{T} {s} \geq \sum_{t = 0}^{P}{s} + \left\lceil \frac{value_{S_i} - value_{S_{i + 1}}}{S_{i + 1} - S_i} \right\rceil$$$. With this simplification we can solve this task with a simple priority queue (store this threshold value for all $$$(i, i + 1)$$$ and greedily keep removing stuff during type-3 queries). Note that the calculation of value for any point can be done in $$$O(1)$$$ just like the way in the editorial.

Implementation: link