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

Автор Artyom123, 3 года назад, По-русски

Мы надеемся, что вам понравился контест. Сразу к разбору:

A: Максимизация медианы
B: MIN-MEX разрез
C: MAX-MEX разрез
D: Рассадка в кинотеатре
E: Пересадка почек
F: Движение точек
G: Четыре вершины
H: Xor-квиз
Кто что делал?
Разбор задач Codeforces Global Round 16
  • Проголосовать: нравится
  • +372
  • Проголосовать: не нравится

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

Thx for fast editorial

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

Thanks for the round and fast editorial.

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

Fastest Editorial I've ever seen

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

I can't read the condition!!! For task D2 , I thought that there are columns and rows that do not affect anything. Because of this, I did not solve the problem. OMG

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

Got the logic for D2 but wasn't able to convert it to code :(

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

    solving lot of implementation questions helps! and generally it comes with time and consistency.

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

      Did i tell wrongly? Downvoters should comment the appropriate answer before degrading my answer.

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

Feels bad to solve B and C but not A ):

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

Thanks for the editorial. I noticed that the second solution for Problem A has the editorial for Problem B. It will be great if it can be rectified.

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

I think you over-killed F with seg-trees. it could be done with just one sort and the rest was O(n) dp.

first remove all covered segments that have either a point or another segment inside them. then sort all segments and points.(compare segments by right ends with points). now let dp_i be answer for the first i things(segments and points together) and let pd_i be answer if we force that after our operations, we have a point in the position X_i.(if the i'th thing is a point X_i is its position otherwise its the segment's leftpoint) you can see details of updating the table in my submission.128662794(its very messy cause I finnished debugging in last minute of the contest)

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

    I have something similar with just a sort and O(n) dp.

    First keep only useful segments and assign them to the point on their right. Then for each point, we want to calculate dp[i][c], which is the minimal cost to cover all segments on the left of point i if the point i travels to the left c times (c = 1 or 2). Either point i goes to the left, then comes back and goes to the right, or vice versa.

    Then to go from point i to i + 1, there are (k + 1) ways to split the k intervals between them, and for each of them there are 4 transitions. Finally, the answer is just dp[n] (we add a point with position +inf at the start).

    You can see my submission here 128653517

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

    Code is good, but logic description would be better.

    I have also O(n) dp without trees. I did check point coverage by binary search, then removed overlapping segments using simple sort and stack. Additional observation is that you don't need to move point over any previous point initial position. So dp[i][j] was where dp[i+1][j] would tell how much we need to move points [0,i] to cover everything up to point i would be visited and j segments in between point i and i+1 exactly visited by point i. So dp[2][1] would tell how much should we move points 0 and 1 such that every segment up to point 1 would be visited and exactly single segment between points 1 and 2 would be visited by point 1. For each j I did brute force how far we should go left and then rearranged it a bit and noticed fact that we actually pick one of two choices for each j. 128674186 (commented part is brute force version).

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

    the author's approach to finding segments that don't contain other segments might also be overkill. If we consider all segments in decreasing order of L then we can just maintain the min r[j] we've met so far. When considering {l[i], r[i]}-> this segment contains another segments if (min r[j]) <=r[i];

    I'm not really sure why the author decided to use Fenwick trees here

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

    Nice Approach

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

This was a nice round. For the first time I solved more than 2 problems of a global round. Could have solve D2 also, but the implementation was beyond me....

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

For E, Can anyone explain why Sum of Leaves + Sum of Buds = n — 1? Precisely, why this holds true?

Initially, there are n - k - 1 leaves (total amount of nodes — the amount of buds — root)
  • »
    »
    3 года назад, # ^ |
      Проголосовать: нравится +3 Проголосовать: не нравится

    Because if initially a node is neither a bud nor a leaf, when you remove all the buds under this node, it becomes either a bud or a leaf (doesn't apply to the root).

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

Constraints in D should've been stricter IMHO

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

    I instinctively went straight to ordered multiset (happy that I would finally use this thing in a contest) to achieve $$$O(nmlog(m))$$$ but yeah, I didn't notice that $$$O(nm^2)$$$ fits.

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

    I completely agree. I myself used the Fenwick tree, not noticing that the constraints allow us to solve for a square.

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

    I strongly disagree — the problem is nice in its current state, increasing constraints just unnecessarily adds some data structure work on top of that.

    In my opinion adding data structures is usually justifiable if its easier than the actual ad-hoc part of the problem. Even a fenwick tree (or any other easy method of inversions) is way tougher than the observations needed in D1, maybe even D2.

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

      In my opinion, counting inversion is actually easier (or more straightforward) than the construction part. Still, I agree with you that it adds no value to the problem.

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

        I see your point, but I'd argue its more standard, not easier. It still requires someone to know Fenwick / pbds / merge sort trick.

        This is most likely trivial for anyone 17-1800 or higher as they've likely encountered the idea before.

        However I suspect there are a lot of participants in the 14-1600 range who could make the observations for D1/D2 but don't know any of the standard methods for inversions. I certainly didn't till I was 16-1700.

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

          Some knows, some don't. With this logic "there are some people who don't know these alg/ds" you could cut them out from any problem.

          Your argument makes sense, but I think you underestimate what people know. Pretty sure half the cyans know about Fenwick/Segtree nowadays and would be happy to practice them

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

      Ya your point is fine increasing constraints force the participants to use data structures like fenwik tree/segment-tree but in my opinion this has a positive outcome,If the participant couldn't solve the problem during the contest due to lack of data structure knowledge but it enables them to learn these data structures after the contest and then try to solve it again that's what upsolving all about. Having knowledge of more data structures always helps :)).

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

    Ya I did it in O(nmlogm) by counting inversion with divide and conquer whereas my friend got also got passes with naive O(nm^2) algo.T_T

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

I recently encountered a problem during the contest. I don't know if it's a bug or a Codeforces thing. The problem is, if I give two correct submissions for the same problem, my last correct submission is taken into account for my points distribution. I think that logically, the first correct submission for the problem should be taken into account. I solved D1 first, and then, D2. After which, I submitted the solution for D2 in D1 also, due to which I lost half of the points of that question. So, it didn't matter if I got AC for D1 long ago, I got considerably low points .

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

    Not a bug, part of the rules. You might want to resubmit a problem if you think it won't pass sys tests or it will get hacked.

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

Thanks for the great round!

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

Really liked the question. This contest was really competitive, with people solving questions at high speed.And liked the editorial(idea of giving hint first).ThankYou

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

Really liked the question. This contest was really competitive, with people solving questions at high speed. And liked the editorial(the idea of giving hints first).ThankYou

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

I like this kind of editorial with spoiler hints

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

thx for good and fast editorial!

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

Didn't notice O(nm^2) fits into the solution.Was thinking of something else. Thanks for the round and a pretty fast editorial!

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

Thanks for the great contest!

Unfortunately, I think I saw problem G somewhere.

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

Is there meant to be special-casing for $$$C \in \{3,6,7,15,23,43\}$$$ in problem H? For these values, the number of square-free integers in $$$[1..C]$$$ is strictly greater than $$$\lceil 0.65 \cdot C \rceil$$$, which Hint 2 suggests is impossible.

EDIT: Whoops! I just noticed the unusual constraint $$$C \geq 100$$$, which is important for this reason.

EDIT2: But in light of this, I don't understand the problem-setting reasoning behind making the problem interactive at all. Was it originally intended to be an easier problem?

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

Why there are 700+ test cases for G... XD

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

Weak pretests on problem D2

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

My G (the case with two edges without common endpoints):

Paint each vertices in one of $$$c$$$ colors (I've chosen $$$c=5$$$). Now for each edge we know a pair $$$(a, b)$$$ ($$$1 \leq a \leq b \leq c$$$) which denotes the colors of it's endpoints. If for two edges and their pairs $$$(a, b)$$$ and $$$(x, y)$$$ each of $$$a \neq x$$$, $$$a \neq y$$$, $$$b \neq x$$$ and $$$b \neq y$$$ holds, then we know for sure that these edges have no common endpoints.

For each pair maintain a multiset of edge values (and the largest one of them) and iterate over a pair of pairs. Then, we can with probability around $$$0.416$$$ (for $$$c=5$$$) find a correct answer. Do as many iterations as you can fit in the time limit.

My H:

Also gaussian eliminations for each group to find any solution. To find a solution with correct $$$n$$$, use hill climbing.

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

Chinese universe students with a morning lesson cryyyyy.

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

Am ithe only one who implemented segment tree in D2?

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

Thanks for such a good round and fast editorial

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

So in reality the $$$\lceil 0.65 n \rceil$$$ can be replaced with the number of squarefree numbers smaller than $$$n$$$? (in H)

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

Love this contest

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

After looking at the constraints again, Order Statistic Tree seems like an overkill for D1 and D2.
My Submission

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

I think that the input in D2 is not easy to understand &_&

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

why not every contest tutorials are like this .. very well written tutorial and solution code thanks !

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

Help() Please

https://codeforces.me/contest/1566/submission/128700326

Here is my submission i'm trying to solve D1 with help of PBDA where the heck i'm wrong : ( Could'nt find any counter test case why I'm getting WA on Test Case 2

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

The first hint in problem E is incorrect, and here's a counter-example:

  1
 / \
2   3
     \
      4
     / \
    5   6

Re-hanging 4 (bud) to 2 (leaf) won't decrease the number of leaves.

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

 shouldn't it be min instead of max? as we need here the ending index (j) of the second last segment? Or I am getting it wrong? Here is my accepted solution using the given idea but using min : 128769652

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

128624993 why I am getting tle on Question c although my solution is of O(1e5) and editorial of d2 which is of O(1e8) is still running.

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

I am unable to get how having a leaf connected with root will always reduce the size. Can anyone explain in detail for the third test case given in the question.

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

Problem D can actually be solved in O(n*m*log(m)) by using an ordered set to calculate the inconvenience of a person in log(m). Here is my solution using Policy Based DS in cpp.

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

So Fast!

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

I think the difference in difficulty between E and F is too large.

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

For problem E, why we are subtracting 2*k, it is not clear to me. Can someone expalin?

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

I have a problem about PROBLEM B, 0002000 ,i think it ouput 1,but std output 2. Maybe I misunderstand the problem?

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

thanks for having a pictorial explanation of test cases...