IceKnight1093's blog

Invitation to CodeChef Starters 78 (Rated till 6-stars) — 22nd February
By IceKnight1093, 21 month(s) ago, In English

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!

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

Comments Comments (10)
| Write comment?
»
21 month(s) ago, # |
  Vote: I like it +14 Vote: I do not like it

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

→ Reply
»
21 month(s) ago, # |
  Vote: I like it +12 Vote: I do not like it

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

(I'm not saying that it is copied)

→ Reply
»
21 month(s) ago, # |
  Vote: I like it +5 Vote: I do not like it

How to solve Divisible Array Counting ?

→ Reply
  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

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

    → Reply
  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it +8 Vote: I do not like it

    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.

    → Reply
  • »
    »
    21 month(s) ago, # ^ |
    ← Rev. 3   Vote: I like it +8 Vote: I do not like it
    Spoiler
    → Reply
»
21 month(s) ago, # |
  Vote: I like it +24 Vote: I do not like it

screencast with commentary

→ Reply
»
21 month(s) ago, # |
  Vote: I like it 0 Vote: I do not like it

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.

→ Reply
  • »
    »
    21 month(s) ago, # ^ |
    ← Rev. 3   Vote: I like it 0 Vote: I do not like it

    I did it squared and passed w/ 0.03s

    For each position you could iterate through the alphabet quadratically

    → Reply
  • »
    »
    21 month(s) ago, # ^ |
    ← Rev. 2   Vote: I like it +8 Vote: I do not like it

    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.

    → Reply