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

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

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

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

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

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

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

omg satyam343 round

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

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?

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

PREFIXMAX is a mastapeece!

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

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

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

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

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

    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.

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

      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.

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

is it possible to solve Largest Y using binary search?