Please, try EDU on Codeforces! New educational section with videos, subtitles, texts, and problems. ×

Cache's blog

By Cache, history, 4 weeks ago, In English,

We’re halfway through the year and its time for our sixth Long Challenge of the year 2020. We invite you to participate in CodeChef’s June Long Challenge, this Friday, 5th June, 15:00 IST onwards The contest will be open for 10 days i.e. until 15th June.

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: - Setters: Sahil sahi1422 Chimnani , Naman smartnj Jain , Vikas _wildfire_ Pandey , Vinit vitz Solanki , Taranpreet taran_1407 Singh, Raja raja1999 Vardhan Reddy , Sofiia sonechko Melnyk , Ildar 300iq Gainullin , Arthur arthur.nascimento Nascimento

  • Admin : Teja Cache Vardhan Reddy

  • Tester: Felipe fmota Mota

  • Editorialist & Post-Contest Streaming: Rajarshi RestingRajarshi Basu

  • Statement Verifier: Jakub Xellos Safin

  • Mandarin Translator: Hanlin I_love_PHP Ren

  • Vietnamese Translator: Team VNOI

  • Russian Translator: Fedor Fedosik Korobeinikov

  • Bengali Translator: Mohammad solaimanope Solaiman

  • Hindi Translator: Akash Shrivastava

Prizes

Top 20 performers in the Indian category and top 10 performers in the Global category will get CodeChef laddus, with which the winners can claim cool CodeChef goodies. First to solve each problem except challenge — 100 laddus. Know more here

Good Luck!
Hope to see you participating!!
Happy Programming !!

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

»
4 weeks ago, # |
  Vote: I like it +9 Vote: I do not like it

Contest starts in 10 minutes!

»
4 weeks ago, # |
Rev. 2   Vote: I like it -8 Vote: I do not like it

I hope that the problems are tasty!

»
3 weeks ago, # |
  Vote: I like it +75 Vote: I do not like it

User hehaodele, currently in rank 8, solved the problem PPARTS by asking in the CF forum in the last 5 hours, pretending it is the problem he came up with. Now the article is deleted, but there is already some witness (Um_nik). Please investigate and disqualify him.

  • »
    »
    3 weeks ago, # ^ |
      Vote: I like it +36 Vote: I do not like it

    I am a witness too. Um_nik answered the question saying that he learned it 4 days ago.

  • »
    »
    3 weeks ago, # ^ |
      Vote: I like it +38 Vote: I do not like it

    Thanks, will escalate it.

  • »
    »
    3 weeks ago, # ^ |
      Vote: I like it -44 Vote: I do not like it

    Still participating in long-plagiarized-contests?

  • »
    »
    3 weeks ago, # ^ |
      Vote: I like it +21 Vote: I do not like it

    Thanks for reporting! We have removed the user from the ranklist, and blocked their account on CodeChef. We'll update here if they provide any reasonable explanation for what's happened.

    • »
      »
      »
      3 weeks ago, # ^ |
      Rev. 3   Vote: I like it -57 Vote: I do not like it

      Are you going to block all those users who witnessed this/got AC after that blog?

      Don't let things change your good character. Stop participating in these plagiarized challenges.

      PS: CodeChef_admin Remove these ridiculous longs and start some Dinner/Break-Fast, post editorials at the right time.

      • »
        »
        »
        »
        3 weeks ago, # ^ |
          Vote: I like it -30 Vote: I do not like it

        CodeChef_admin Remove these ridiculous longs

        Noone asked a cheater for advice.

        • »
          »
          »
          »
          »
          3 weeks ago, # ^ |
            Vote: I like it -28 Vote: I do not like it

          So you think I am hehaodele xD,

          There exists many who hate Codechef Longs & its braggers in discuss

          • »
            »
            »
            »
            »
            »
            3 weeks ago, # ^ |
              Vote: I like it -16 Vote: I do not like it

            You admitted you are cheating.
            I never said you are hehaodele you only bought this here.

            its braggers in discuss

            You can do a lot of productive things other than opening discuss.

            There exists many who hate Codechef Longs

            Looking at you comments your reason for hating it is cheating which you are encouraging. You can simply stop participating in long. Codechef_admin is not coming to your house and forcing you to participate.

            • »
              »
              »
              »
              »
              »
              »
              3 weeks ago, # ^ |
                Vote: I like it +23 Vote: I do not like it

              You can simply stop participating in long.

              I did that mistake once. Never participated thereafter. BTW Thanks for the advice.

  • »
    »
    3 weeks ago, # ^ |
      Vote: I like it +86 Vote: I do not like it

    I can confirm that roughly 10 hours ago I answered a question by hehaodele and my answer can be used as a solution to PPARTS.

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

      Now that the contest is over can you tell your solution?

      I solved it by applying the xDln operator on the question which converted it into a simpler form.

      • »
        »
        »
        »
        3 weeks ago, # ^ |
          Vote: I like it +29 Vote: I do not like it

        https://judge.yosupo.jp/problem/sharp_p_subset_sum

        You can watch submissions there.

        In short:

        We want first $$$n$$$ coefficients of $$$Q(x) = \prod_{k=1}^{n} (1 + x^{k})^{c_k}$$$

        Let's define $$$P(x) = \ln Q(x) = \sum_{k=1}^{n} c_k \ln (1 + x^k)$$$

        $$$\ln (1 + x) = \sum_{i=1}^{\infty} \frac{(-1)^{i + 1} x^{i}}{i}$$$

        $$$P(x) = \sum_{k=1}^{n} \sum_{i=1}^{n/k} \frac{(-1)^{i+1} x^{ik}}{i}$$$

        We can calculate $$$P(x)$$$ in $$$O(n \log n)$$$ since there $$$O(n \log n)$$$ summands. Then $$$Q(x) = \exp P(x)$$$ which can be calculated in $$$O(n \log n)$$$.

        • »
          »
          »
          »
          »
          3 weeks ago, # ^ |
            Vote: I like it +3 Vote: I do not like it

          Yeah thanks, I did almost exactly that but I took the derivative of $$$ln(1+x^k)$$$. And integrated it to get the same result you got.

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

          math.stackexchange link Here, there is a method of nth derivative of generating function, can we somehow apply the same method here,if we just want to Calculate for sum a_i * b_i =n, is it possible?

»
3 weeks ago, # |
  Vote: I like it +19 Vote: I do not like it

Did anyone manage to fit $$$O(nlog^2n)$$$ in TL for DIFVAL? i.e without the dsu on tree approach.

I tried segtree on dfs time array where each node is a persistent segtree, and ended up having to create 7e7 nodes per case. Was unable fit it in TL. :(

  • »
    »
    3 weeks ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

    I used Sack (DSU on Tree) along with a persistent segtree to do it in Nlog²N.

    It ran in first attempt but I had done a few optimizations. Like adding the light subtrees by BFS instead of DFS (this is helpful because it guarantees minimum number of operations), also instead of removing elements from the segtree, I just applied the updates on the blank segtree (I can do this because it's persistent).

    Apart from this, my segtree was persistent as well as Dynamic.

    Here's the link to the solution: https://www.codechef.com/viewsolution/34062043

»
3 weeks ago, # |
  Vote: I like it +49 Vote: I do not like it

CodeChef_admin Hey I think its the time to either reduce the duration of long challenge maybe to 2 or 3 days or stop conducting long challenge. Instead come with something like Dinner, Breakfast, Snacks or something else. I find two reason for this

  1. Plagiarism (that usually remain undetected as person change the name of variable ,use different templates etc)

  2. Long challenge sounds odd one out from Lunchtime and Cook-off, so contest like Snacks , Dinner, Break-Fast will sound far more logical.

  • »
    »
    3 weeks ago, # ^ |
      Vote: I like it -21 Vote: I do not like it
    reduce the duration of long challenge maybe to 2 or 3 days or stop conducting long challenge.

    We all know that these absolutely logical words will have no effect whatsoever. It's so sad to see Codechef this way. :facepalm:

»
3 weeks ago, # |
  Vote: I like it +4 Vote: I do not like it

Top 20 performers in Indian category would mean top 20 in div1, or is top 10 from each division.

My name is on 19th in the following list : https://www.codechef.com/rankings/JUNE20A?filterBy=Country%3DIndia&order=asc&sortBy=rank (filter :India, sort : ASC).

Am I eligible for any laddus(assuming ranklist is unaffected after MOSS)? If yes then how many.

Thanks!

  • »
    »
    2 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    But how codechef determine someone is Indian or not because one can change his/her location to India just to get free laddus (in case he is not in top 20 in global but is in top 20 Indians)

    • »
      »
      »
      2 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Yes I also thought of this possibility, I'm unaware of how codechef chooses top 20 indians.