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

Автор antontrygubO_o, 4 года назад, По-английски

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!

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

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

I am author of all problems.

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

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

Ad-hoc problems incoming....

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

Well, I am starting codechef

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

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!

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

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

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

would not miss this for the world!!!!

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

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.

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится -35 Проголосовать: не нравится
    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.

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

      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"

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

    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.

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

      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.

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

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.

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

    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.

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

    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)

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

Reminder 1 — Contest starts in less than 3 hours.

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

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.

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

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.
  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится +35 Проголосовать: не нравится

    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.

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

    Exactly my story as well.

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

    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

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

After this contest I confirm that I am not constructive!

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

that was an amazing problemset :)

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

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

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

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