IceKnight1093's blog

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

How to solve Divisible Array Counting ?

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

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

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

screencast with commentary

→ Reply
»
2 years 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
  • »
    »
    2 years 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
  • »
    »
    2 years 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