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

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

We invite you to participate in CodeChef’s Starters 78, this Wednesday, 22nd February. The contest will be rated for users upto $$$6$$$-star, i.e, with rating $$$\lt 2500$$$.

Time: 8 PM — 11:00 PM IST

Joining us on the problem setting panel are:

Written editorials will be available for all on discuss.codechef.com. Pro users can find the editorials directly on the problem pages after the contest.

The video editorials of the problems will be available for all users for 1 day as soon as the contest ends, after which they will be available only to Pro users.

Also, if you have some original and engaging problem ideas, and you’re interested in them being used in CodeChef's contests, you can share them here.

Hope to see you participating. Good luck!

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

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

As an author, I recommend everyone to participate, the problems are really interesting!

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

MinAdd is exactly the same as https://codeforces.me/contest/1560/problem/F2, with a difference in the output answer.

(I'm not saying that it is copied)

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

How to solve Divisible Array Counting ?

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

    Hint: Any good subarray will contain atmost 30 distinct elements.

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

    Good array contains no more than $$$O(\log n)$$$ distinct elements. Also if subarray $$$[l; r]$$$ is good so is $$$[l; r - 1]$$$. So let's calculate array $$$r$$$ where $$$r_i = max \, j$$$ such that $$$[i; j]$$$ is good. We can do it naively in $$$O(n\log^2 n)$$$. Now we can answer queries off-line with a couple of Fenwick trees and scanline.

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

What is the intended solution for Balanced Suffix?

My solution has a complexity of $$$O(n \cdot |C|^3)$$$ and it passed in 0.56 s.

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

    I did it squared and passed w/ 0.03s

    For each position you could iterate through the alphabet quadratically

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

    Mine is $$$O(n|C|^2)$$$ but it can be improved to at least $$$O(n|C|\log|C|)$$$. UPD: Now that I think about it, it can be solved in $$$O(n\log|C|)$$$ Don't think it can be done faster than that.