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

Автор 300iq, 3 года назад, По-английски

We invite you to participate in CodeChef’s November Lunchtime, this Saturday, 28th November, from 7:30 pm to 10:30 pm IST onwards 3 hours, 5 problems.

We will also be hosting two live problem discussion sessions on Sunday (29th) from 5pm to 6:30pm IST (first 4 problems) and on Monday (30th) from 5pm to 6:30pm IST (last 3 problems), where our panelist, rajarshi_basu will discuss the Lunchtime problems. Find more details here.

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.

Joining me on the problem setting panel are:

  • Setter & Admin: Ildar 300iq Gainullin
  • Tester: Nikolay budalnik Budin
  • Editorialist: Alei Morphy Reyes
  • Video Editorialists: Chirayu Jain, Prachi agarwal19 Agarwal, Darshan darshancool25 Lokhande, Yashodhan ay21 Agnihotri, Bharat Singlai, Aryan Aggu_01000101 Agarwala, Radoslav radoslav11 Dimitrov
  • Statement Verifier: Jakub Xellos Safin
  • Mandarin Translator: Qingchuan qingczha Zhang
  • Vietnamese Translator: Team VNOI
  • Russian Translator: Fedor Mediocrity Korobeinikov
  • Bengali Translator: Mohammad solaimanope Solaiman
  • Hindi Translator: Akash Shrivastava

Prizes: Top 10 Indian and top 10 Global school students from ranklist will receive certificates and CodeChef laddus, with which they can claim cool CodeChef goodies. Know more here. The video editorials of the problems will be available on our YouTube channel as soon as the contest ends. Subscribe to get notifications about our new editorials.

Good luck and have fun!

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

»
3 года назад, # |
  Проголосовать: нравится -83 Проголосовать: не нравится

300iq orz

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

Highly Unbalanced contest! Were you really employed to make codechef better than it was before??

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

Why problem difficulty gradient is so bad at codechef ?

»
3 года назад, # |
  Проголосовать: нравится +56 Проголосовать: не нравится

Finally reached Div1!

JK. I enjoyed the problems, thank you.

»
3 года назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

Spent two and a half hours figuring out that a fake eulerian cycle edge can be between vertices in the same component. :(

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

The constraint of Chinese version of Circle Coloring is different to English version. And the translator say it's a mistake made by Codechef team because their final constraint it different to the constraint in repository...

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

Is there a linear solution for B? I spent the entire contest optimizing my N log N on B... and I was only able to get it down to like 1.2s with bitset cheese.

»
3 года назад, # |
Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится

In Fractions, we are supposed to count the number of divisors of $$$i \cdot(i+1)$$$ which are $$$ \leq n-i $$$ and add them into the answer for each $$$ i, 1 \leq i \leq n $$$. Why, the answer is always $$$ = \sum_ {i=1}^{n} ( \frac{nod(i) \cdot nod(i+1)} {2} - 1 ) $$$, where $$$nod(i)$$$ = number of divisors of $$$i$$$ ?

»
3 года назад, # |
  Проголосовать: нравится +68 Проголосовать: не нравится

Gasoline — fine but very binary-scored, I can't imagine an easy-ish solution for partial points
Fractions — interesting problem but tight limits. Why only ten points for $$$N \leq 10^5$$$? And did you want $$$O(N)$$$? My $$$O(N \cdot \log N)$$$ sieve was too slow. I ended up binary searching tests (which were just $$$10^6$$$ and $$$10^6-1$$$) and hardcoding solutions.
Rooks — standard graph problem
Coloring — weak tests, many people got 80 points with a solution that doesn't work for small $$$N$$$. And why no subtask for a small sum over $$$|A_i|$$$?
Eating — fine but why limits $$$N \leq 20$$$, $$$\sum N \leq 200\,000$$$ for brute force? $$$O(2^N)$$$ will get TLE.

This is for sure not a good contest for people who prepare for IOI. Please spend some time making subtasks. You can even use fewer problems then.

  • »
    »
    3 года назад, # ^ |
    Rev. 3   Проголосовать: нравится +46 Проголосовать: не нравится

    In Fractions, The editorial describes $$$O(N \cdot \log N)$$$ solution too. I checked that tester's solution works in 0.5s because it does something non-trivial to reconstruct divisors instead of just storing them. So why set TL to 1s instead of 2-3s? Come on, at least give us 90 points for your complexity with a worse constant factor.

    In Coloring, the editorial actually describes a solution that consists of parts for small and big $$$N$$$. So you knew that big $$$N$$$ can be solved separately and you didn't make a subtask for that and instead made us guess (which was easy by looking at standings) that you didn't put tests with small $$$N$$$ in subtask 2.

    On the bright side, I very much like the solution for Coloring!

    • »
      »
      »
      3 года назад, # ^ |
        Проголосовать: нравится -7 Проголосовать: не нравится

      Regarding Fractions, we can use some memory optimizations (implementing a vector with reserved memory without freeing memory at exit) to fit it in around 0.97 seconds (it barely fits anyway), and I agree that a very slightly worse constant factor doesn't warrant a 90 point penality.

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

      For Fractions, my complexity is $$$\mathcal O(N \log \log N)$$$ I think, you can see my submission here. It runs in 0.12 seconds, but yeah I agree that there was no reason to make the bounds so high and the time limit so low.

»
3 года назад, # |
  Проголосовать: нравится -6 Проголосовать: не нравится

Looking at the number of submissions, seems like the contest was made only for GM+ level people

»
3 года назад, # |
Rev. 2   Проголосовать: нравится +6 Проголосовать: не нравится

Video editorials for 3 problems have been uploaded here. The other 4 videos will be uploaded over the next day or two.

»
3 года назад, # |
  Проголосовать: нравится -11 Проголосовать: не нравится

bad contests no dp problems