300iq's blog

By 300iq, 4 years ago, In English

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!

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

| Write comment?
»
4 years ago, # |
  Vote: I like it -83 Vote: I do not like it

300iq orz

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Why problem difficulty gradient is so bad at codechef ?

»
4 years ago, # |
  Vote: I like it +56 Vote: I do not like it

Finally reached Div1!

JK. I enjoyed the problems, thank you.

»
4 years ago, # |
  Vote: I like it +1 Vote: I do not like it

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

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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...

  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    There was an announcement during the contest about these constraints.

    • »
      »
      »
      4 years ago, # ^ |
      Rev. 2   Vote: I like it +23 Vote: I do not like it

      WoW, I don't receive any notice about it. Now I see when I participate Codechef Contest, I should read the announcement frequently.

      • »
        »
        »
        »
        4 years ago, # ^ |
          Vote: I like it +1 Vote: I do not like it

        CodeChef supports CF like notifications. One has to enable them. Sometimes a popup comes asking if you want to enable them or not. If you use chrome you can search how to turn on notifications for a website.

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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.

  • »
    »
    4 years ago, # ^ |
      Vote: I like it +6 Vote: I do not like it

    The answer is sum(d(i)*d(i+1)/2-1), where d(n) is the number of divisors of n.

»
4 years ago, # |
Rev. 3   Vote: I like it 0 Vote: I do not like it

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$$$ ?

»
4 years ago, # |
  Vote: I like it +68 Vote: I do not like it

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.

  • »
    »
    4 years ago, # ^ |
    Rev. 3   Vote: I like it +46 Vote: I do not like it

    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!

    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it -7 Vote: I do not like it

      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.

    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it +12 Vote: I do not like it

      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.

»
4 years ago, # |
  Vote: I like it -6 Vote: I do not like it

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

»
4 years ago, # |
Rev. 2   Vote: I like it +6 Vote: I do not like it

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

»
4 years ago, # |
  Vote: I like it -11 Vote: I do not like it

bad contests no dp problems