KunalSin9h's blog

By KunalSin9h, history, 7 weeks ago, In English

Yesterday I created problems using the Polygon system.

there is one Problem with two Parts($$$n \le 400$$$ and $$$n \le 2\times10^5$$$)

i would love if you see and solve the problems!

gym link : https://codeforces.com/contestInvitation/ef9be4fa454826fa1bcc152a56c098d0b5c260f8

UPD : I have also Uploaded Editorial, Link : Editorial

 
 
 
 
  • Vote: I like it
  • +68
  • Vote: I do not like it

»
7 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

good problems,

first one is easy but second one is not easy.

»
7 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
7 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

I am unable to solve this problem

»
7 weeks ago, # |
  Vote: I like it +22 Vote: I do not like it

The problem is interesting (second part), but it requires just one observation and one standard algorithm.

Overall this is a good problem.

»
7 weeks ago, # |
  Vote: I like it +31 Vote: I do not like it

Now Watch Leetcode copy your problem without giving any credit xD

»
7 weeks ago, # |
  Vote: I like it -10 Vote: I do not like it

An awesome problem bro. Keep adding more to the community with this kind of creativity...

»
7 weeks ago, # |
  Vote: I like it -6 Vote: I do not like it

Nice problem. I'd say it would make a good Div2 C problem!

»
7 weeks ago, # |
Rev. 2   Vote: I like it -10 Vote: I do not like it

Nice one, enjoyed it !!

»
7 weeks ago, # |
  Vote: I like it +10 Vote: I do not like it

Probably inspired from this problem.

»
7 weeks ago, # |
  Vote: I like it +10 Vote: I do not like it

Forget using long long. :(

»
6 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Enjoyed solving it!

»
6 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Nice.

»
6 weeks ago, # |
  Vote: I like it +14 Vote: I do not like it

Nice (but a bit standard) problem with a good idea. I felt the editorial was somewhat unclear, so here's how I thought about it.

Consider another permutation $$$p$$$, and apply $$$p$$$ to both $$$a$$$ and $$$b$$$ to get $$$a'$$$ and $$$b'$$$ respectively (i.e., $$$a'_i = p_{a_i}$$$ and $$$b'_i = p_{b_i}$$$). The answer doesn't change, because of the bijection mapping pairs of indices $$$(i, j)$$$ to $$$(p_i, p_j)$$$ that also preserves cross connections (and pairs which don't form a cross connection are not mapped to cross connections). Now we can simply choose $$$p$$$ to be $$$a^{-1}$$$, which would make $$$a'$$$ the identity permutation, and $$$b'$$$ can be computed in $$$O(n)$$$. After that, we just need to count inversions in $$$b'$$$, which can be done by Fenwick trees, segment trees, any BBST, or merge sort.

»
6 weeks ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

Nice Problem! solved with ordered set (pbds).

»
6 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Good problem, wonder why you still pupil if you can think about segment tree problem like that, recently I see a lot of round using segment tree so that weird :v

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

    Currently I don't know about segment trees. But I know about Fenwick Trees and BBST. So I solved using them.

    • »
      »
      »
      6 weeks ago, # ^ |
      Rev. 2   Vote: I like it 0 Vote: I do not like it

      Try to learn segment tree if you already familiar with Fenwick Tree because ST have way more application, I think the only bad think about segment tree is that if you don't use library then try to implement it will a little long but since the contest are online so it always benefit you

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

        And segment trees are much slower than fenwick trees and takes more memory.

        • »
          »
          »
          »
          »
          6 weeks ago, # ^ |
          Rev. 4   Vote: I like it 0 Vote: I do not like it

          But the different in performance is not much, I have never encounter a problem that BIT pass but ST fail. I think it like compare vector and array :v

      • »
        »
        »
        »
        6 weeks ago, # ^ |
        Rev. 2   Vote: I like it +3 Vote: I do not like it

        imo segtree implementation isn't that long.

        my code
»
6 weeks ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it
Spoiler