ko_osaga's blog

Hello 2020
By ko_osaga, 5 years ago, In English

새해 복 많이 받으세요, 코드포스! (Happy new year, Codeforces!)

Welcome to the first Codeforces Round of the new decade, Hello 2020! The round will be held on Jan/04/2020 15:05 MSK.

Some information about the round:

  • Div 1, 2 combined
  • 2.5 hours!
  • 7 problems!
  • No subtasks!
  • Score distribution: 500-1250-1750-2500-2750-4000-4000
  • Yes, it is rated!

This round is prepared by ko_osaga nong ckw1140. I am personally very thrilled to deliver my first Codeforces contest as such a memorable one!

More credits for the contest:

UPD: Editorial. Thank you for your participation!

UPD2: Winners:

  1. mnbvmar
  2. TLE
  3. Benq
  4. tourist
  5. gamegame
  6. never_giveup
  7. dario2994
  8. yosupo
  9. Marcin_smu
  10. kczno1
Announcement of Hello 2020
  • Vote: I like it
  • +1231
  • Vote: I do not like it

Comments Comments (264)
| Write comment?
»
5 years ago, # |
  Vote: I like it +312 Vote: I do not like it

First comment of the decade on a CF round blog.

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

Happy New Year!

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

No offense, but how can a blue coordinate a round written by orange writer? not to say such an important round.

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

Hello ko_osaga!

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

Where's the interactive :o

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

The decade starting with Korean round! This is so great!

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

Hi ko_osaga.

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

Hi ko_osaga

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

everyone can participate?

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

The first contest in2020.Hope everyone can get a good place！

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

Hope I will became expert for first time in this round!!!

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

Hello 2020!

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

Кажется, что подзадачи на cf стали настолько нормальной практикой, что контест, который обходится без них, воспринимается как нечто необычное и хорошее, раз составитель отмечает это.

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

But it is not the new decade, except you consider that every year(not only year, it can be month, day, etc.) starts a new decade, with start in that year. Now it is 21 century, it started on January 1, 2001, not 2000. And this year is not a first year of 203 decade, it is the last year of 202 decade.

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

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

    For your information, ISO 8601 defined decade like this.

    3.1.2.22

    decade

    time scale unit (3.1.1.7) of 10 calendar years (3.1.2.21), beginning with a year whose year number is divisible without remainder by ten

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

      they define century as time scale unit (3.1.1.7) of 100 calendar years (3.1.2.21)duration (3.1.1.8), beginning with a year whose year number is divisible without remainder by 100 which is let's say questionable

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

        I always hope that every people count centuries in 0-indexed style.

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

hope pretest passed => system test passed

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

Waiting for anyone asking if it's rated or not..

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

i hope that my rate exceeds 2020 Through 2020

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

Is the score format like educational rounds or like goodbye 2019 ?

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

Good competition is coming. (Radewoosh, jqdai0815 and tourist)

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

다들 새해 복 많이 받으세요~~ happy new year~~

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

I am very sad that I have no time.For a terrible exam. o(╥﹏╥)o

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

good bye 2019

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

⠀ ⠀ ⠀ ⠀

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

Wow!! I can't wait!!!

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

2020!

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

ko_osaga On a genuine note, in last contest too, it was said there wont be any subtasks but there were subtasks. If there are going to be subtasks, then please don't say "No subtasks"

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

    There weren't subtasks in the last contest.

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

Really NOT friendly for US time T_T TAT TvT TwT

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

I have a suggestion guys. It would be great if the problem setters include some ques on Graphs an Trees in any of the A,B,C,D ques of the contest . It is generally there on the E,F ques which a not so good programmer like me find it too hard to solve and doesn't get enough exposure of these kind of problems in the real time.

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

    A B C graph problems is kinda boring or well known .. if not contest would be unbalanced

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

Welcome 2020!

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

I admire the Coordinator because he usually makes simple problem statements that are easy to read and understandable.

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

Happy new year!

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

Wow there is more than 14,000 registeration.

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

Ceremony sense of New Year

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

The prize of the contest has no T-shirt?

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

Happy New Year!

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

Look like, it going to be first contest in codeforces with 15000+ registrations.

UPD -: 15000+ registrations achieved.

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

Happy New Year, Codeforces...!!!

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

Korean round assa!

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

.

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

15k+ registration

I think it is highest ever. Best of luck for all and server as well as.

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

$$$15521$$$ registered users, I think it would be wiser not to participate, as the servers will surly suffer :(

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

    But if there is less query problem, the server would rather less suffer.

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

    There will be a lot like you to reduce the load of server so that other can participate safely.

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

Oh Oh, 15k5 Participants @@

→ Reply
»
5 years ago, # |
← Rev. 3   Vote: I like it -57 Vote: I do not like it

Queueforces for the first contest of this decade...

Edit: Sorry seems it didn't matter much. Next time I will sent such comment after contest.

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

tough one

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

I am new to CF. The submission result alarms me each time, as my logic works alright in IDE, but here it says it's an error

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

Tough!

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

Hardest contest I had participated so far

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

What is TC9 in E ?

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

    Mostly, it will fail if you use atan2.

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

      Why? atan2 is a cpp function. Isn't that supposed to work correctly?

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

        Precision error is too big to even considering passing it.

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

          It is interesting that even atan2l which uses Long Double has not enough precision to pass...

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

      Hm, somehow my atan2 passed system tests...

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

What is the idea to solve B other than segment tree?

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

    How can It be solved using segment tree?

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

      I don't know efficiently count every subsequence how many number bigger than x, or lower than x but discard that for next subsequence, so I calculate from segment tree 0 to x, or x to 1e6

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

    Use prefix sums instead of segment tree.

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

    If a subsequence already has an ascent, add n. If not, add (# of subsequences that have an ascent) and all subsequences that have a max value greater than this subsequence's min value (and do not have an ascent). To do this query fast, I used a suffix array from 1 to 1e6 for suffix[i] = number of sequences with max_value >= i that do not have an ascent.

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

      ah, I just realize why suffix or prefix is good enough thanks!

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

      I implemented exact this approach, what's wrong with my submission 68210144? I got WA on testcase 21.

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

    Binary search?

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

    binary search works

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

    with binary search

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

    First, count the sequences already with an ascent (let there be asc of them) and discard them. Then interpret all remaining sequences as line segments (from their min value to their max value), create 2 events (start and end) for every one, and sort them. Use that to count how many segments start after the current segment ends for every segment and sum these numbers, i.e. find the number of non-overlapping segments, and use that to find the number of overlapping segments (m*m - non_overlapping_count where m is the number of remaining segments). The answer is m*m-non_overlapping_count + 2*n*asc - asc*asc (add pairs of sequences where at least one already has an ascent, and subtract those where both do).

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

    So, there can be two types of valid concat. One is ascents exists in either the s_x or in s_y, second is smaller element exists in s_x and greater element exist in s_y.

    So if we find an array where we got a ascent, we can pair it with all arrays. Now, we will count how many subarrays of type two exist. for each array which doesn't contain any ascent, you can pair this with such type of array where the maximum element is greater than the minimum element of the current array.

    → Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    • Find min, max of each sequence — store that (no need to store the entire list)
    • Store how many numbers are greater than and less than each min/max in an array (doesn't need segment tree)
    • If a sequence is already sorted, maintain a count of that and don't count its min/max. This is because this sequence concatenation will always result in a desired sequence
    • For each sequence, check how many min's its max is greater than. Add that to total.
    • Note that a sequence can be concatenated with itself (so make sure that's not double counted)

    68188241

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

    Why so many downvotes? My solution is accepted using segment tree, but I'm sure it should be not the intended solution. That's why I'm asking here

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

Good contest, thanks!

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

How to solve D?

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

    Instead of checking subets, check only pairs.

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

      I got that, but how to even check that in the required time.

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

        Let's denote first range as $$$[a_i, b_i]$$$, and second range as $$$[c_i, d_i]$$$. Sort by a, add all $$$[c_j, d_j]$$$ where $$$b_j < a_i$$$ into some data structure(You can use BIT). Now check if there is intersection with segment $$$[c_i, d_i]$$$ with BIT(Don't forget case when your segment fully lies inside another segment).

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

    My idea was the following.

    Suppose you have a graph for each venue. Vertices are the intervals, we connect them only if they don’t intersect. The problem asks if those two graphs are equal.

    The size of each graph is quadratic, so you can’t just create them and compare. My idea was to make the hash of each graph and compare them. For each vertex you can get the sum of its neighbors indices multiplied by some power of 2s .You can check out the hashing method in more details in my solution.

    Did anyone else solve the same way with hashing?

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

      I check all intervals that start after the current one and all intervals that finish before the current one on both sets and check that their hashes are equal. Hashes are xor of random 64 bit numbers assigned to each interval.

      Update: Idea was correct, there was a bug in the code

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

        I tried the same hash. Got WA on test 16.

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

        I did the same, but instead of using xor, I used multiplication on Zp for large prime p (1000000007)

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

      I also used hash, but I wonder if there are other ways to solve it (deterministic, also easier to implement.)

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

        68193999 2 segments [u,v] and [x, y] are NOT intersecting if either y < u or v < x. With the use of multisets, you can bulk check if a segment is NOT intersecting with any of many other segments. This will take O(logN) time. Do this for each segment and you get O(NlogN) time. I saw many solutions with segment trees, this one uses only STL.

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

      I solve it with hashing too, but way different that what you are doing. I hash for every element the set of neighbors and compare each pair of sets.

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

      For each vertex you can get the sum of its neighbors indices multiplied by some power of 2s
      How do you do that if it's a complete graph?

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

        Sort based on left coordinate and use suffix sums. Then do the symmetric procedure with reversing the segments.

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

    In D, I figured out one observation, say intervals at the same indices at venue A and venue B must have the same number of overlapping intervals. This is a necessary condition and we can also easily prove by induction that it is sufficient condition as well.

    Now the task is to calculate the number of overlapping intervals for each index which can be easily calculated using sorting.

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

      Interesting. I realized it was necessary but it wasn't evident to me that it was sufficient

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

        It is sufficient when n=2, Now say it is sufficient for n=k(Somehow we figured out the number of overlapping intervals for each index), For n=k+1 if we have updated counts and result for n=k we can easily update it for n=k+1, Hence It is sufficient.

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

      Umm, no. That is not sufficient. I am not sure how this passed, I have hacked your solution :). Poor test data?

      Here's a counter case:

      4
1 5 1 5
2 8 7 10
7 10 2 8
9 20 9 20
      → Reply
»
5 years ago, # |
  Vote: I like it +36 Vote: I do not like it

How to solve E?

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

    Let K be the sum of the points lying inside each triangle. The answer is: K * (N-4) / 2;

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

      How to calculate K?

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

        For each triangle, calculate the number of points in it. To do this, we calculate for each segment the number of points under it. Now we can calculate the number of points in the triangle for $$$O (1)$$$, we just need to analyze the cases.

        And don't forget about pragmas.

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

          I thought there's some cleaner logic to compute this. But I guess it's easier if one already has that code for some other task sitting in their computer and pastes it straight away.

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

            What about not computing K? xd

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

            I didn't use any prewritten code and it took me 15 minutes to solve this problem. Learn how to solve geometry problems instead of complaining.

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

            I think further simplification might make this easier.

            Instead of calculating no of points inside every triangle, we can just subtract no of convex quadrilaterals, which then gives;- $$$ K = \binom{n}{4}- num of line segment intersections $$$

            Since diagonals of convex quadrilaterals intersect.

            I think line segment intersections is a well known problem. However, I didn't have sufficient time left to code it during the contest, so the formula is unverified, please let me know if there are any mistakes.

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

              How were you considering computing the number of segment intersections?

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

                Ah, my bad. I thought Bentley ottoman would work fine, didn't remember about the no of intersections being in complexity.

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

        Fix the point which lies inside. make it center and sort the rest of the points ccw wrt the center. Now we can count the number of triangles using prefix sums of number of points that give positive cross product for each point.

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

        Goal : A point $$$p$$$ and a set of $$$N$$$ points $$$S$$$ are given. We want to compute the number of triangles containing $$$p$$$.

        We can easily know that the answer is "$$$N \times (N-1) \times (N-2)/6$$$ — (the number of triangles which do NOT contain $$$p$$$)". If the triangle $$$s_1 s_2 s_3$$$ does not contain $$$p$$$, then there is a straight line $$$l$$$ that splits $$$p$$$ and three points $$$s_1$$$, $$$s_2$$$ and $$$s_3$$$. Thus, we can design the algorithm below:

        1. Consider the line $$$l$$$, which passes the point $$$p$$$.

        2. Rotate $$$l$$$ about $$$p$$$.

        3. When $$$l$$$ touches a point of $$$S$$$, compute the number of points that are on the left side of $$$l$$$.

        4. Let $$$k$$$ be the number, then add $$$(k-1) \times (k-2)/2$$$ to the answer.

        5. Do the step 2. to 4. until $$$l$$$ is rotated by 360 deg.

        The naive algorithm is $$$O(N^2)$$$. But you can do it in $$$O(N lgN)$$$ with sorting points $$$S$$$ about $$$p$$$ — something like ccw-sort

        Now, whole the problem can be solved. Just do the steps above about all the $$$N$$$ points. The time complexity is $$$O(N^2 lgN)$$$.

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

Problem C was very nice.

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

    How to solve C? TIA

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

      We can rewrite the sum as, in how many permutations, subarray with size k exists. Then we can sum these values from k = 1 to n. This technique can be called as contribution sum technique.

      Now, notice that, for a fixed k length, there can be n — k + 1 choices for min and max element. And there can be n — k + 1 subarrays in an n size permutation. So we can permute k elements in fact(k) ways, and other n — k elements as f[n — k] ways.

      So ways(k) = (n — k + 1) * (n — k + 1) * fact(k) * fact(n — k)

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

        Can you explain better on why is there (n-k+1) choices for min and max and (n-k+1) subarrays in an n size permutation?

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

          k is the length of the sub-permutation, there are n-k+1 positions where it can start.

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

            So It should not be k! * (n-k)! * (n-k+1)

            as k numbers can be permute in k! and it can be placed in (n-k+1) position of (n-k)! possible permutation of (n-k) numbers

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

              This n-k+1 is there twice. Once it is the number of positions where a subseq of len k can start. Second it is the number of possible smallest numbers of this subsequence.

              So you multiply that twice, and once with (n-k)!.

              Adding up for all possible k is answer.

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

    What was nice about it? :)

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

F: It is always possible to achieve a perfect matching. Proof using hall's theorem.

Call the initial set of edges in $$$T_1$$$ original edges. Iterate on edges $$$(u, v)$$$ of $$$T_2$$$ and find any original edge $$$(a, b)$$$ in $$$T_1$$$ on the path between $$$u$$$ and $$$v$$$ (there will always exist an original edge, otherwise we have a cycle in $$$T_2$$$). Cut $$$(a, b)$$$ from $$$T_1$$$ and link $$$(u, v)$$$. We can use hall's theorem to prove a perfect matching among unmatched edges.

Can we solve this problem without LCT?

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

    Yes. Try to find constructive proof not using Hall.

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

    My solution (pending systests) doesn't use a LCT (or something similar). My solution was to find an edge $$$(u, v)$$$ in $$$T_2$$$ such that $$$u$$$ is a leaf. Let $$$w$$$ be the first neighbour of $$$u$$$ in $$$T_1$$$ on the path from $$$u$$$ to $$$v$$$ (in $$$T_1$$$). Then we print $$$(u, w)\in T_1$$$ and $$$(u, v)\in T_2$$$, remove $$$(u, v)$$$ from $$$T_2$$$ and contract the edge $$$(u, w)$$$ in $$$T_1$$$. One can prove the resulting graphs are trees on $$$n-1$$$ vertices, correctness follows inductively. The contraction operation requires some careful bookkeeping with vectors/sets, but ultimately doesn't require anything fancy.

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

D was interesting to me ^^. Could you guys show your solution to this problem?

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

    The main idea is check venue-sensitive set with size 2

    For each lecture, check if the list of lectures that intersect with it in venue $$$a$$$ is the same as the list of lectures that intersect with it in venue $$$b$$$

    Instead of comparing each element in two list, we'll check does any element that appear in this list but doesn't appear in the other list

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

What was the trick for C? So many people solved it, I haven't even got any idea how to solve it.

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

    for length k permutations, the sum is (n-k+1) * (n-k+1) * k! * (n-k)!

    eg n=4,k=2

    we have 12 23 34 (4-2+1 kinds)

    and for 12, it has 2! permutations

    the numbers left are 34, has (4-2)! permutations

    we want to put 12 into ()3()4() , which have (4-2+1 blanks)

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

      Why we are multiplying by extra (n-k+1) ?

      If we consider k numbers then they can permuted in k! manner and can be placed in (n-k+1) position. So k! * (n-k+1) and rest (n-k) numbers can be permuted in (n-k)! manner

      So in total k! * (n-k+1) * (n-k)!

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

        k numbers could be 1~k, 2~k+1, 3~k+2, total n-k+1 kinds

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

I made a big strategic mistake :(

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

    It is almost always not the right idea to start with the harder problems.

    Here is the explanation: It is more probable that you will get the easier problem quickly and harder problem will take more time. Submitting earlier ensures that you don't accumulate the penalty for the easier problems. Even in a simple scenario where you solve A in 3 minutes and E in 30 minutes, your penalty is 3 + 33 = 36 minutes. If you solve A later, you penalty for A is 33 minutes and so the total penalty is 63 minutes. I don't exactly know about how scoring works, but at least in the time penalty approach you can see how worse it can be to not solve an easier problem.

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

In task D, why the answer for test case 3 is "YES"? We can attend 1 and 3 at A (1-2 and 3-7), but can't attend at B (5-9 and 6-11)

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

    Your input format is a bit messed up — You cannot attend 1 and 3 at A (1-5/3-6) nor can you attend 1 and 3 at B (2-9/7-11)

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

      Oh, really, i thought format was sa, sb, ea, eb. Thank you

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

    1 and 3 are 1-5 , 3-6 at A and 2-9 , 7-11 at B so we can't attend at A and neither at B

    → Reply
  • »
    »
    5 years ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it
    1. in A starts at time 1 and ends at 5. The times are ordered as start A, end A, start B, end B
    → Reply
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

The difficulty of problemset was high a bit for me, but it was good problemset.

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

How to solve C?

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

Can anyone explain me solution of Problem C I wasn't able to find any pattern in answers neither I was able to think of any dp approach

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

    Let'x fix length of good segment, there is (n — len + 1) ways to choose starting number, (n — len + 1) ways to place those numbers, len! ways to permute those len numbers, (n-len)! ways to permute remaining numbers.

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

In problem D I created 2 segment tree one for a and one for b

Then in each query I check if all cells between xa and ya is empty and if it true I mark in array that he can attend this lecture and make update query and makes all this cells occupied, (the same with xb, yb).

at the end iterate over the attended array and if there is attended1 != attended2 I print No

if all have the same values I print Yes.

I got Wa on test 17, anyone know why ?

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

E is a very interesting and original problem. The best problem of the decade

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

    Most geometry problems are like that.

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

    Actually, it was very similar to problem D of Argentinian Programming Tournament 2019

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

how can I implement this for problem c:

t=0
for (i=0;i<n;i++){
t += (n-1)*(n-i)* factorial(n-(i+1)) * factorial (i+1)
}
→ Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it +6 Vote: I do not like it

    Pre-compute factorials from 1 to n before implementing this loop.

    → Reply
»
5 years ago, # |
← Rev. 3   Vote: I like it -9 Vote: I do not like it

A-D were trivial, F and G too hard so I was stuck solving the geometry problem for a hour and a half. And of course as is usual with geometry problems, of that around 15 minutes was spent solving the problem, then the rest trying to fix case handling to avoid double-counting and issues with angles. Why did I even try?

Could we please leave geometry to ICPC and have good problems in contests instead? :)

EDIT: 180 lines and FIVE Fenwick trees later I think I'm done debugging.

EDIT2: And my code for sorting by angle was too slow. After lots of constant optimisation of a $$$\mathcal{O}(n^{2} \log n)$$$ solution I finally got AC (68205536)

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

H2S E?

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

As the long and detailed header of my submission for problem F might suggest, I already knew problem F. I wanted to propose it as part of an online contest.

I am happy about the rating boost I will get, but I am sad that I cannot use in a future contest the best problem I had ever invented. At least I have participated in the round, otherwise there would be only the sad part.

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

We are all waiting for the solutions ^^

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

How to solve E, I spend 1.5 hours but no idea. May be I only NEED 2 more points,then I can become CM:(

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

    Sadly.... I need 92 more points.Because I got FST on problem D.

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

How do you solve C? My approach: write a stupid solution, get a table for small values of n <= 11, try to find a pattern. Unfortunately, both OEIS and me trying to figure out the pattern failed. How do you solve it then?

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

hello 2020 & goodbye rating again

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

Here's a cool reduction I made for $$$E$$$:

Claim: Find the sum of number of points in all possible triangles in the given set. Divide this by $$$2$$$ and multiply by $$$n-4$$$, that's the answer.

Proof: For any castle of $$$4$$$ points and a point $$$P$$$ which lies inside it, consider all the $$$4$$$ triangles made by taking the castle points $$$3$$$ at a time. Out of these $$$4$$$ triangles, $$$P$$$ will lie in exactly $$$2$$$ of them. Conversely, consider any triangle and any point $$$P$$$ lying inside it. If you add any of the other $$$n-4$$$ points to make the triangle into a quadrilateral, you will get a valid castle of the triangle points and this new point which will protect $$$P$$$.

Thus, we have proven a two-one bijection between these two quantities.

Now, if you could find the sum of number of points lying inside each triangle in $$$O(n^2)$$$, you have solved the problem!

→ Reply
»
5 years ago, # |
← Rev. 3   Vote: I like it -11 Vote: I do not like it

Is E about finding how many Concave (or) Convex Pentagons can be formed from N points? If so, then how?

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

    Almost. Let $$$f_n = (\text{number of pentagons with n points on convex hull})$$$. Answer is $$$f_3*2+f_4$$$. We know that $$$f_3+f_4+f_5 = \binom{n}{5}$$$. In my solution i found $$$f_3*3+f_4*4+f_5*5 = \sum_{i\neq j} \binom{\text{number of point p having }(a[i]-p)\times (a[j]-a[i])>0}{3}$$$.

    $$$f_3*2+f_4 = (f_3+f_4+f_5)*5 - (f_3*3+f_4*4+f_5*5)$$$

    . Finding $f_5$ is $$$\mathcal{O}(n^3)$$$ problem. 1146H - Satanic Panic

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

    You haven't to do it. Consider a tuple of 5 points, the contribution of this tuple to answer is ((number of lines can split plane to 2 halfplanes and a half has 1 point, another one has 2 points) — 5). It is easier to solve base on the above observation.

    → Reply
»
5 years ago, # |
← Rev. 3   Vote: I like it -8 Vote: I do not like it

Damnit, slightly late with F... if I'm not completely wrong. My idea is:

  • consider paths in T1 corresponding to edges in T2
  • augmenting paths imply that if we create subtrees from them by merging overlapping (on edges) paths, then in each such subtree, there's either no unmatched path (edge in T2) or no unmatched edge in T1
  • this works for any graph T2, but T2 is a tree, so it should cover at most as many edges in T1 as its own number of edges — there must be no unmatched edge in T1 and the max. matching is equal to the number of edges covered by the paths (which is N-1 because they have the same size)
  • we can proceed with simple DFS in T2 and for each edge (v, leaf), try to find the first edge in T1 on the path leaf->v that's unmatched and take this edge

UPD: Yep, it works.

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

I had a noob bug at F, but I want to know can flow pass this problem ?

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

    Not intended, but one participant managed to squeeze it with push-relabel flow (We failed)

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

I love this problem set(especially, F&G), thank you problem setters!

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

I derived the formula for C with probability and found Expected number of framed segments with length i.

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

Why geometry problem...

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

In E, if I manage to find for every point P:

$$$a$$$ $$$-$$$ the number of points in the upper left side of P

$$$b$$$ $$$-$$$ the number of points in the upper right side of P

$$$c$$$ $$$-$$$ the number of points in the lower left side of P

$$$d$$$ $$$-$$$ the number of points in the lower right side of P

Won't the answer for point P be the sum of:

$$$cnk(a + b,i)$$$ $$$*$$$ $$$cnk(c + d,4 - i)$$$

$$$-$$$ $$$cnk(a,i)$$$ $$$*$$$ $$$cnk(c,4 - i)$$$

$$$-$$$ $$$cnk(b,i)$$$ $$$*$$$ $$$cnk(d,4 - i)$$$

for every $$$1<=i<=3$$$ ?

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

I just realize E's polygon is NOT necessary convex...

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

In problem G, the checker told me that I must place a wall between rock cells. However, I couldn't find the statement which specifies that point.

Did I overlook something? Or was the statement incomplete?

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

    How to solve G?

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

      It's unweighted matroid intersection. The universe is the set of all edges in the graph, and we'll try to remove as many edges from the graph as possible. We intersect two matroids:

      • A cographic matroid (a set of edges belongs to the matroid iff we can erase this set without disconnecting the graph),
      • A matroid limiting the number of edges incident to each black cell. In other words, the edges are partitioned into disjoint subsets, and each subset has the upper bound on the number of edges taken to the set. Fortunately, each edge belongs to only one subset, so this is easily a matroid (as a sum of disjoint uniform matroids).

      We then find the largest set belonging to the intersection. If you found enough edges to make the graph a tree, the answer is YES.

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

        What's test 77 in G?

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

          Some anti-random cases.

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

          We used a bunch of hill-climbing to kill random solutions of G. kriii spent several days for preparing awesome tests of G. I think he will have a lot to talk about ;)

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

        Yesterday matroid intersection blog came up in the CF feed, and I decided to read it. After 15 min I thought "come on, what is the chance that I will ever encounter such an unusual construct" and gave up on it...

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

      The problem is equivalent to finding a tree over the free cells such that all the leaves are white or (1,1). This can be seen as a matroid intersection. The two matroids to intersect are:

      • Independent sets are sets of edges (pair of neighbouring free cells) without a cycle.
      • Independent sets are sets of edges (pair of neighbouring free cells) such that any black cell different from (1,1) is contained in at most one such pair.

      [Not sure it is correct, since I was not able to code it]

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

more like Hello WW3

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

Once again he showed who is the real boss (respect you 3000).

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

How to solve D? I was thinking at hashing the intersections after you sort the intervals as you would when you want to calculate the maximum number of intervals overlapping (put both start and end points in a vector and sort). Does this lead to anything? Is there a nicer solution?

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

    Yes, it works. You can hash random weights for it to work better. I just xored all weights of intervals not intersecting with a specific one. This can be done by using 4 maps.

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

    Yes, I solved it like this. We need to check for each interval i if its set of intersecting intervals is equal in both the graphs. We compare two sets by considering hashing a set $$${a_1, a_2, \ldots}$$$ to a polynomial $$$p(x) = x^{a_1} + x^{a_2} + \ldots$$$. Then we can evaluate it at random points and check equality. The degree of the polynomial is $$$n$$$ so if you use a mod around $$$10^9$$$ the probability of failure is $$$10^{-4}$$$ by Schwartz-Zippel if you evaluate at a single point. I evaluate at four points for probability $$$10^{-16}$$$.

    68192135

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

Instead of "No subtasks!" you guys should mention "No Geometry!".

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

Gotta feel bad for tourist. TLE on Test 77 of G.

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

Thanks a lot for the round!

My screencast, mostly trying to squeeze in incorrect solutions for F and G without much success :)

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

Good move ! by jqdai0815 ...

Now , he will be the rank 1 ...

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

when will the virtual participation for this round start?

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

My randomised sol for D passed:

If there exists a pair of segments which intersects in one of the events and not the other then answer is NO. So each segment has to intersect with the same exact other segments in each events. This implies that for any subset the number of intersections in each event has to be the same.

So here's what I did: Take a random subset (50% chance of a segment being in it). Count number of intersections if Event A was chose, and same for Event B. If the number of intersections is diff output NO, otherwise repeat again with a diff subset(for 50 iterations). To count number of intersections, i sorted segment by left endpoint, then used binary search on each element.

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

    I reckon your power came from your new handle

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

Systests have been completed and upsolving is still unavailable. What's wrong?

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

왜 한글이 없나... 과연 어캐ㅔ 될까요

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

    It is because foreigners can't read Hangul.

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

I have a technical question.

After this round I will become candidate master. but before my rating changes I registered for round 612 div2. Now... if I participate in it, will it be rated for me?

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

    I don't think you will be able to participate for div2. If you become candidate master then you will have to register for div1, once the rating calculation is done.

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

And it's a moment right after contest. AND... Where is the editorial?)

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

Did they just rejudge G?

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

i don't understand why test 3 in task B have output is 72. Can you explain for me !.

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

    My output is 74.

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

      How are you counting?

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

      Try this.

      2
2 1 2
2 3 4

      if you are getting 6 instead of 4. Then you might be counting 1 2 3 4 and 3 4 1 2 twice.

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

    I'm pretty sure that the test case is large enough that there is no good explanation that is not along the lines of "because this solution, proven correct, returns 72" or "if you look at the list of all concatenations and count those with an ascent, you get 72" here.

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

    In case it helps, check the output of this verbose brute-force solution.

    Brute-Force Solution
    Output
    → Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    1 with all 10

    2 with 9 (except 2)

    3 with 3(1,8,10)

    4 with 7(except 2,4,6)

    5 with 6(except 2,4,5,6)

    6 with 8(except 6,2)

    7 with 9(except 2)

    8 with all 10

    9 with 8(except 2,6)

    10 with 2(1,8)

    total 72

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

Does anyone know how to analyse the complexity of network flow(the number of edges can be $$$O(n\log n)$$$) in F？

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

    There can be $$$\Theta(n^2)$$$ edges in the matching graph of F.

    EDIT: Consider $$$T_1$$$ the path with vertices $$$(1,2), (2,3), (3, 4), \dots$$$, and $$$T_2$$$ a path with edges $$$(1, n), (n, 2), (2, n-1), \dots$$$. Then the $$$i^{th}$$$ edge of $$$T_2$$$ covers $$$n-i$$$ edges of $$$T_1$$$, giving the matching graph $$$\Theta(n^2)$$$ edges.

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

      The number of edges can be $$$O(n\log n)$$$ using some optimization.

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

    It's $$$O(n\sqrt{n}\log{n})$$$.For proof take a look at the editorial of this PrinceOfPersia's problem: ALT

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

I have a query : If a participant registers for a Div. 2 contest before rating change, and then enters Div. 1 after rating change, will Div. 2 be rated for him/her or do they require to re — register or something like that?

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

I think solutions for problem G are rejudged.

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

Just solved D with a 2D segment tree (more like a Dynamic segment tree + fenwick tree ) !

https://codeforces.me/contest/1284/submission/68203222

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

found this in tourist's code lol

rng_58

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

"Strong testcases on problem D.." xD

Check this out -> Problem D: 68195434

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

gamegame will win IOI2020!

→ Reply
»
5 years ago, # |
← Rev. 3   Vote: I like it -8 Vote: I do not like it

Hi Guys,

In the problem E, very very high precision is needed. Can anyone calculate?(or explain)

In 68214305 24 digits of PI couldn't pass.

But 68214338 using cos(-1.0) (more than 30 digits precision) is accepted.

Regarding the limits (and no three point collinear), how is it possible?

Note: M_PI gets compile error(not in my PC tho)... Purely correct submission(in 70 min left) would be AC if it could compile T-T

Note2: arctan(1/1e9) is like 1e-10 different than the actual PI, soo 1e-24... how???

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

    Don't use doubles to check on which side of a line a point lies (or to sort rays with common origin by angle, which is roughly equivalent). Use cross product instead

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

problem D is too difficult to understand the request

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

Can anyone please explain why my code for D is getting TLE? https://codeforces.me/contest/1284/submission/68243271

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

For Problem D, the statement is horrendous. You say that it is bad if they overlap, and then proceed to say it is actually fine if one is nested in the other...

→ Reply