antontrygubO_o's blog

Invitation to CodeChef September Lunchtime 2020

By antontrygubO_o, 4 years ago, In English

We invite you to participate in CodeChef’s September Lunchtime, this Saturday, 26th September, from 2000 hrs to 2300 hrs IST.

Please Note — Unusual starting time. The Contest will begin at 2000 hrs instead of 1930hrs

The contest will feature 5 problems for 3 hours. I am author of all problems. I hope you will like them.

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:

  • Tester: Alexander scanhex Morozov
  • Statement Verifier: Jakub Xellos Safin
  • Editorialist: Colin galen_colin Galen
  • Admin: Ildar 300iq Gainullin
  • Mandarin Translator: Gedi gediiiiiii Zheng
  • Vietnamese Translator: Team VNOI
  • Russian Translator: Fedor Mediocrity Korobeinikov
  • Bengali Translator: Mohammad solaimanope Solaiman
  • Hindi Translator: Akash Shrivastava

Prizes: The 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.

Good luck and have fun!

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

Comments Comments (30)
| Write comment?
»
4 years ago, # |
  Vote: I like it +68 Vote: I do not like it

I am author of all problems.

Hmm. The chances of getting a balanced problemset have increased exponentially.

→ Reply
»
4 years ago, # |
  Vote: I like it +44 Vote: I do not like it

Ad-hoc problems incoming....

→ Reply
»
4 years ago, # |
  Vote: I like it -20 Vote: I do not like it

Well, I am starting codechef

→ Reply
»
4 years ago, # |
  Vote: I like it -46 Vote: I do not like it

I honestly think that somebody should tag the GMs and above here, because the expected quality of the contest is pretty damn high, and most people think the contrary!

→ Reply
»
4 years ago, # |
  Vote: I like it +5 Vote: I do not like it

No mention of divisions , will there be same problems in both divisions?

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

would not miss this for the world!!!!

→ Reply
»
4 years ago, # |
  Vote: I like it +34 Vote: I do not like it

Please move the codechef discussion to codeforces as atcoder does, if possible.
what codechef lacks is community and quality of discussion, codechef discussion page just looks like spam.

→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it -35 Vote: I do not like it
    codechef discussion page just looks like spam.

    That is the way the cc admins decided it to be. It was supposed to be like a stackoverflow for cp.Thats why people can freely ask whatever newbie level problem they want to ask. Thats why it doesn't have downvote system.

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

      What do u mean stackoverflow, there is downvote system on stackoverflow.and you cannot even comment if u don't have atleast 50 reputation points.
      But there should be downvote system, so people won't ask most famous question,"how to begin with cp, or please debug my code"

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

        I said "supposed to be like stackoverflow". I never said it is. XD

        → Reply
  • »
    »
    4 years ago, # ^ |
    ← Rev. 3   Vote: I like it -22 Vote: I do not like it

    According to me, codechef discussion forum is one of the best, where people at least don't do partiality and don't just downvote without even reading the post, like here in codeforces. It's just like- If you are Newbie on cf -"You don't have right to ask questions here, it is only meant for high rated coders, who ask meaningful questions".
    A simple doubt here by some beginner gets downvoted. Even doubts remain unanswered for days or weeks. At least on codechef, someone is always there who answers doubts, however basic it may be or at least provide the resources to study.

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

      But is that the right thing to do? People must learn at some point that first they should try to search on the internet if someone has already asked the same thing.

      That's the right attitude. Quora and stackoverflow both show similar questions(previously asked) to keep users from asking redundant questions. That's why these forums are relatively clean and organized.

      But in codechef you will find the same kind of questions asked countless times.

      Beginners must first try to debug on their own. But most people come directly and paste their codes and start asking others to debug for them. Codeforces teaches them the right thing to do by downvotes.

      Genuine doubts are answered in codeforces whether it was asked by a beginner or a LGM.

      → Reply
»
4 years ago, # |
  Vote: I like it +110 Vote: I do not like it

Are you planning to write more Codechef contests? If yes, I would take part in Div.2 this time and get enough ratings for future Div.1 contests.

→ Reply
  • »
    »
    4 years ago, # ^ |
    ← Rev. 4   Vote: I like it +24 Vote: I do not like it

    Idk why mike wants to spoil all the fun.

    Btw Anton said he authored cc contest because he wanted to boost his friend's career. Lets hope his friend has a lot of geniosity friends who would like to boost his career.

    P.S. — You will need two rated contest for div 1 rating.

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

    I am afraid I am not planning to write more Codechef contests in the nearest future, but I would still encourage you to join. I feel like Codechef is changing for better, with 300iq and Ashishgup in the team :) (Not mentioning the rest)

    → Reply
»
4 years ago, # |
  Vote: I like it +5 Vote: I do not like it

Reminder 1 — Contest starts in less than 3 hours.

→ Reply
»
4 years ago, # |
← Rev. 2   Vote: I like it +17 Vote: I do not like it

In addition to the textual editorials, the hardest 3 problems of Div-1 will be discussed in live sessions on YouTube — 11:30 pm IST today, and at 11pm IST on 27th and 28th. The easiest 4 problems will have pre-recorded video editorials. All the 7 video editorials will be added to this playlist.

→ Reply
»
4 years ago, # |
← Rev. 2   Vote: I like it +52 Vote: I do not like it

How to solve PERMSPL:

  1. Try to write "stupid" solution that just flips the state of some random element a lot of times;
  2. Realize that the impact of the flip on the difference only matters on what its initial state is.
→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it +35 Vote: I do not like it

    I had a fairly clean argument for it although I didn't understand why the equivalent condition works in the end:

    Build a graph, let $$$w_{uv}=1$$$ if $$$P_u > P_v$$$ else 0.

    Let $$$a_u \in [0,1]$$$ be the assignment of index $$$u$$$.

    Want assignment such that $$$\sum w_{uv}(1-a_u)(1-a_v) - \sum w_{uv} a_u a_v = 0$$$.

    This simplifies to: $$$\sum w_{uv}(1-a_u) = \sum w_{uv}(a_v)$$$.

    Which is equivalent to whether there is a partitioning where the sum of outdegrees in each partition is equal, which is easily done with knapsack.

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

    Exactly my story as well.

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

    I used this idea in contest. Consider two subsequences $$$A$$$ and $$$B$$$ that form $$$p$$$. Then there are three types of inversions in the original array:

    • Inversions between elements in $$$A$$$
    • Inversions between elements in $$$B$$$
    • Inversions between an element in $$$A$$$ and an element in $$$B$$$.

    Let the number of inversions of the first kind, second kind, and third kind be $$$x, y, z$$$. We want to find $$$A, B$$$ such that $$$x = y$$$, or $$$x+z = y+z$$$, or $$$2(x+z)=2(y+z)$$$. Note that the left side is simply twice the number of inversions in the original array that use an element in $$$A$$$, and the right side is twice the number of inversions using an element in $$$B$$$. Let's design a new array $$$x[i]$$$ such that $$$x[i]$$$ is the number of inversions $$$p[i]$$$ is involved in. Then $$$2(x+z)$$$ is the sum of $$$x[i]$$$ for all elements in $$$A$$$, and $$$2(y+z)$$$ is the sum of $$$x[i]$$$ for elements in $$$B$$$. We can easily compute $$$x[i]$$$. Thus we want to split $$$x[i]$$$ into to parts with equal sum. We can do this with knapsack DP in $$$\mathcal O(n^3)$$$. Note that this also gives us a way to recover how to split the array.

    Submission link

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

After this contest I confirm that I am not constructive!

→ Reply
»
4 years ago, # |
  Vote: I like it +45 Vote: I do not like it

that was an amazing problemset :)

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

Great contest, a lot of thinking!

I overcomplicated PERMSPL and ADDONSEG a lot. I solved the former with some randomized solution (trying to get some split for every difference) and I didn't get the ifs right for ADDONSEG even for a subtask. My screencast & commentary https://youtu.be/R9AJxwWptQY

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

As a video editorialist I enjoyed solving Anton's problems!

→ Reply