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

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

Hello Codeforces!!

We're honored to invite you to TheForces Round #17 (AOE-Forces) which will take place on Jun/17/2023 18:05 (Moscow time).

What is a TheForces Round?
What is AOE?

The registration is open now! please don't forget the time.

You will have 2 hours and 15 minutes to solve 6 problems.

  • Also we want to thank You for participating in our rounds.

Discord Server (1000+ people, join for a cookie)

Contests' archive

Editorial

  • Проголосовать: нравится
  • +106
  • Проголосовать: не нравится

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

Nice round! Neat problems! Hope you'll enjoy!

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

As a tester, I can confirm to you that the round is great and all the problems are interesting. Good luck in the round!

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

    As a Friend of the tester. Please give him contribution because he deserves it.

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

As a tester, I remind you to join the Discord server!

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

Excited for this

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

AOE2 is my favorite game in my childhood! I still play it now. However every time when I play this game before a CF contest my performance would be a disaster...

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

As a tester, I can assure that everyone will have a non-negative delta in this round.

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

As a tester, problems are interesting, hope you can enjoy them!

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

As an author, give me contribution ;)

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

TheForces Orz!

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

My favorite RTS game! Wow!

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

OMG AOE-Forces Round :)

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

excited

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

As a tester, I like playing as holy roman empire in aoe4.

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

as a tester, u will enjoy solving the problems:)

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

I'm excited for this Thanks for your efforts guys

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

Warrior Scouts are the best!! ILALUUUUUUU

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

I'm coming with the mangudai

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

As a participant,I shall play as english

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

I wish I won't go with the late game choice Xd

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

As a tester, You will enjoy balanced problemset ;)

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

I think it's time for real eltihab my friend

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

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

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

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

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

For problem D, I have a complexity of O(n * 2^k * k). The author's solution seems to have the same complexity. But my solution keeps getting TLE. Can anyone tell me where I am going wrong? Link to Submission: Link. Thanks in advance.

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

    Note that you are using __gcd() too. So your complexity is not $$$O(n \cdot 2^k \cdot k)$$$.

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

      But in the editorial there is also a line checking if __gcd(a[i], a[j]) is 1. I think the solution in the editorial also uses O(n * 2^k * k) other than the __gcd() check.

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

I nuked $$$D$$$ with the Micali-Vazirani (MV) algorithm. See:

An $$$O(|E|\sqrt{|V|})$$$ algorithm for finding maximum matching in general graphs, Silvio Micali and Vijay V. Vazirani, 21st Annual Symposium on Foundations of Computer Science, 1980.

It is a very advanced algorithm. Note that the complexity of the Edmonds blossom algorithm is $$$O(|E||V|^2)$$$, which is not sufficiently fast! For the MV algorithm, I adapted a code from a github repository. Its code quality is reliable.

My final code:

Spoiler

Overall complexity:

Part1: Calculating the gcd and constructing the graph: $$$O(nklogmaxa_i)$$$.

Part2: There are $$$|V|=n$$$ vertices and at most $$$|E|=nk$$$ edges in this graph. Thefore, the complexity of the matching process is: $$$O(n^{\frac{3}{2}}k)$$$. In practice, there is an additional log, i.e., $$$O(n^{\frac{3}{2}}k logn)$$$.

Therefore the overall complexity is:

$$$O(nk(logmaxa_i + \sqrt{n}logn))$$$, which can pass this problem easily. Also, MV algorithm is not a randomized algorithm, so the complexity is guaranteed no matter what the test data are.