IceKnight1093's blog

Invitation to CodeChef Starters 78 (Rated till 6-stars) — 22nd February
By IceKnight1093, 22 months 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?
»
22 months 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
»
22 months 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
»
22 months ago, # |
  Vote: I like it +5 Vote: I do not like it

How to solve Divisible Array Counting ?

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

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

    → Reply
  • »
    »
    22 months 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
  • »
    »
    22 months ago, # ^ |
    ← Rev. 3   Vote: I like it +8 Vote: I do not like it
    Spoiler
    → Reply
»
22 months ago, # |
  Vote: I like it +24 Vote: I do not like it

screencast with commentary

→ Reply
»
22 months 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
  • »
    »
    22 months 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
  • »
    »
    22 months 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