satyam343's blog

Invitation to CodeChef Starters 86 (Rated for All) — 19th April
By satyam343, 19 months ago, In English

We invite you to participate in CodeChef’s Starters 86, this Wednesday, 19th April, rated for all.

Time: 8:00 PM — 10:00 PM IST

Note that the duration is 2 hours. Read about the recent CodeChef changes here.

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!

UPD:

I hope you liked the problems!!

Congratulations to the winners of Div 1!

Editorial

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

Comments Comments (13)
| Write comment?
»
19 months ago, # |
  Vote: I like it +29 Vote: I do not like it

I liked solving the problems and hopefully you all will also like the problems

→ Reply
»
19 months ago, # |
  Vote: I like it +53 Vote: I do not like it

omg satyam343 round

→ Reply
»
19 months ago, # |
  Vote: I like it 0 Vote: I do not like it

what exactly does "contest admin" mean? I've seen a lot of different contest admins for CodeChef in the starters announcements. Is the contest admin the person who writes the round?

→ Reply
»
19 months ago, # |
  Vote: I like it +9 Vote: I do not like it

PREFIXMAX is a mastapeece!

→ Reply
»
19 months ago, # |
  Vote: I like it +2 Vote: I do not like it

LEASTSIZE: we can make min score always 1 by choosing centroid. Is this idea Right or Wrong?

→ Reply
  • »
    »
    19 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Yep, right.

    → Reply
    • »
      »
      »
      19 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Thanks. With 5 more min, I can complete my implementation. Again a bad contest :'(

      → Reply
»
19 months ago, # |
  Vote: I like it 0 Vote: I do not like it

https://www.codechef.com/problems/TREESAREFUN is an interesting problem. You have to observe that $$$\sum F_i = N$$$ implies that $$$F_i$$$ can take at most $$$\sqrt N$$$ distinct values. I have used this idea with small to large merging in my solution

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

    Your solution isn't really intended, unfortunately I don't believe it came up while testing and so there weren't any tests against it ($$$N = 10^6$$$ should be an indication that $$$\mathcal{O}(N\sqrt{N})$$$ probably isn't intended :))

    The intended solution is plain $$$\mathcal{O}(N\log N)$$$ with DFS and a segment tree, and is imo quite neat.

    → Reply
    • »
      »
      »
      19 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Well, I didn’t use this fact and coded the standard merge small to large. To avoid divisions, I have a segment tree to find the product of all numbers. Adding/removing a number is handled by recalculating the value of the leaf where this value is represented.

      My solution has complexity $$$\mathcal{O}(n\cdot \log(n)^2)$$$. To be honest, I coded it only because there was not enough time to think about optimizations. I expected an obvious TLE, and I was a bit surprised when I saw it was accepted.

      → Reply
»
19 months ago, # |
  Vote: I like it 0 Vote: I do not like it

is it possible to solve Largest Y using binary search?

→ Reply