When submitting a solution in C++, please select either C++14 (GCC 6-32) or C++17 (GCC 7-32) as your compiler. ×

radoslav11's blog

By radoslav11, history, 3 years ago, In English

We invite you to participate in CodeChef’s June Cook-Off, this Sunday, 20th June, 9:30 PM — 12 AM IST.

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 us on the problem setting panel are:

Prizes:

The winners will receive 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.

Hope to see you participating. Good Luck!

Update: Problem POLYRT has been rejudged so that it also accepts solutions that considered the answer modulo $$$10^9+7$$$. We once again apologise for the inconvenience caused by the wrong statement.

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

| Write comment?
»
3 years ago, # |
  Vote: I like it +57 Vote: I do not like it

As a problem setter ...

»
3 years ago, # |
  Vote: I like it +5 Vote: I do not like it

Pls do something about cheaters , Codechef contests are being ruined by cheaters ... And cheaters are rising in numbers rapidly :(

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

    As a programmer, I can say that don't think about cheater because they are not limited to codechef only, they are continuously doing same thing with other platform too and discussing on cheater is like wasting of time because we or any problem setter or any tester can't do anything to stop them completely. So forgot those thing just participate and enjoy every contest.

»
3 years ago, # |
  Vote: I like it +16 Vote: I do not like it

These Codechef short contests always clashes with my sleeping schedule.

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

    You ruined your sleep schedule practicing spikes with KAGEYAMA :)

»
3 years ago, # |
  Vote: I like it +2 Vote: I do not like it

Codechef short contests always have a weird contest timing.

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

I saw there are 3 divisions in Codechef, since I never participated I am Div. 3, does that mean I can only see the easy problems from the contest?

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

    Some problems from other divisions will also be visible to you and you are allowed to submit them too. However, you won't receive any points for those problems.

    If you scroll down the contest problems page, you will find a list of problems from other divisions which you are allowed to submit

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

    I just want to share my opinion that having 3 different divisions happening at the same time is a bit too much. Codeforces holds div3 rounds separately from Div2 and div1's because in that way you dont make more experienced newcomer miss the more challenging problems

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

      I mean it'll take you like 2 contests to reach div 1 probably, and it's not like you can't do the problems afterwards. Codeforces also holds div1 / div2 contests where experienced newcomers will have to participate in div2, so I don't see how that's any different.

»
3 years ago, # |
  Vote: I like it +6 Vote: I do not like it

Reminder — the contest starts in an hour.

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

In problem Binary String On steroids there is no mention about d. I have asked in the markdown but still did not received an answer.
[Edit : Can we chose any value of k?]
[Edit 2: I am sorry I got it]

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

There has been an announcement regarding the statement for POLYRT. Apologies for the inconvenience.

Announcement:

The statement of problem POLYRT had a mistake. You need to print the final answer without taking it modulo 10^9+7. The statement would be updated to reflect the change. Apologies for the inconvenience.

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

    But what about the cheater the whole happiness of contest is gone this is all because of these cheater why don't codechef take strict action to stop these type of things. If these type of things happen in only 2.5 to 3 hours then think about the codechef long challenges

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

      What strict actions are you suggesting? Should we kill them?

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

        We should make them listen to the 10 hour version of the nyan cat theme song

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

        cheaters should be fired with AK-47.

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

        You know better than me what you can do to stop these types things. Afterall you are my senior and have more experience than me.

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

        How about codechef suspending their account...

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

      But what about the starving children in Africa? The comment you responed to has nothing to do with cheaters.

»
3 years ago, # |
  Vote: I like it +7 Vote: I do not like it

Please do something about the cheaters I have left the contest in the mid, Just once type cookoff solutions on youtube or telegram there are many many solutions available. There is no such point in giving live contests on CodeChef as the ratings always drop. First, it was only in the long challenge but now it has started in the short contests as well. Please do something about it.

»
3 years ago, # |
  Vote: I like it +8 Vote: I do not like it

How to solve Problem :Polynomial Roots https://www.codechef.com/COOK130B/problems/POLYRT. I tried to factorize the expression but didn't came with anything useful.If someone did please share his/her approach

»
3 years ago, # |
  Vote: I like it +7 Vote: I do not like it

Thanks For the Contest Easy Logicwise (I only saw 1st 3 ) but not that simple to code . My Accepted Code for TOOXOR was submitted in the last 5 seconds after 4 back to back attempts . This was for me a perfect fight till end example to remember . Kudos to Codechef Server and And Problem Setters (I wish I will be one of them in future )

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

    I got AC in the last 3 mins after 12 wrong submissions :P.

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

      We were Lucky that the contest got extended by 15 min

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

When do Codechef ratings typically get released (like Codeforces ratings is ~4 hours post contest, what about Codechef)?

»
3 years ago, # |
  Vote: I like it +5 Vote: I do not like it

I just saw that Too Much Xor has just 111 submissions but why this question is not included in div 1???

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

    Too Much XOR is probably my favorite question I've attempted in the last month (aside from EGOI Day 2 P3).

    It was also in Div 3

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

    If only 111 people managed to solve it, does anybody knows why my rank came out to be around 1300 [After solving WAV2 and TOOXOR].

»
3 years ago, # |
  Vote: I like it +12 Vote: I do not like it

how to solve battle royale

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

Wow.. well done..! As a participant, I just want to give my feedback and suggestions abt this contest.

  1. There should be something in the sample test cases to call them sample test cases. If all the examples are just trivial cases like for n=1 or n=2, there's no need to even include any example at all. The input output format is enough to understand what I need to do.

  2. Just one test file in the verdict.. How should I know if I'm failing on some edge case or the whole logic is wrong.. I don't even get to see the test cases after the contest is done. At least 2 test files will be highly appreciated.

  3. I don't like problems with a lot of corner cases :)

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

    sample test cases provided by CodeChef are always very lame and sometimes they do not even explain them.

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

is there editorial of GRAND and CLAMPWAY? I have no idea besides centroid decomposition which takes O(nlog^2 n).

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

    I as I know it will be.

    CLAMPWAY hint in short: build following tree — iterate vertices in ascending order, connect vertex to neighboring components whom contains neighbors with less id. And second tree but in descending order.

    Now clamp way in origin tree is ancestor-predecessor pair in both builded trees.

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

    CLAMPWAY:

    Consider that we're adding the vertices in increasing order of their value and we start "activating" them. Now when we activate some vertex $$$v$$$, we can notice that if it was the endpoint of a path (the max one), the min endpoint would've been in the connected component of $$$v$$$ (connected component in terms of activated vertices). This forms a tree structure (we can use union find to build it), such that $$$u$$$ is an ancestor $$$v$$$ iff when $$$u$$$ is the max endpoint, $$$v$$$ is a valid choice as a min endpoint.

    We'll do the same but in reverse — i.e. build another tree but by adding vertices in decreasing order of their value. Now the answer is the number of pairs of vertices $$$(u, v)$$$ such that $$$u$$$ is a root of $$$v$$$ in the first tree, and $$$v$$$ is a root of $$$u$$$ in the second one. This can be easily solved in $$$O(n \log n)$$$ with a fenwick tree + DFS.

    Update:

    Easily solvable part with fenwick + DFS
    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it +28 Vote: I do not like it

      Not sure about "easily solved" part. I think it's nice even after the reduction.

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

        thanks for all!!! I'll try to upsolve it.

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

    For GRAND the solution we had goes along these lines:

    There is a trivial $$$O(n^2 k)$$$ DP solution — dp[position][number of decreases] with $$$O(n)$$$ transitions per state. The first part is some case analysis of the transitions. If the state is dp[ $$$i$$$ ][ $$$c$$$ ], then we don't need transitions from some $$$j < i$$$ when:

    • $$$a_j < a_i$$$ and there is some $$$p$$$ such that $$$j < p < i$$$ and $$$a_j < a_p < a_i$$$, because we can insert $$$p$$$ between $$$i$$$ and $$$j$$$.

    • $$$a_j > a_i$$$ and there is some $$$p$$$ such that $$$j < p < i$$$ and ($$$a_j < a_p$$$ or $$$a_p < a_i$$$), because we can again insert $$$p$$$.

    Because the input is random, this gives us a $$$O(\log n)$$$ transitions per state and $$$O(n k \log n)$$$ solution. To remove the $$$k$$$ from the complexity, we need to notice that you don't need to maintain the whole DP table. Instead, we can just maintain a wide diagonal — for some $$$i$$$ we will only maintain dp[ $$$i$$$ ][ $$$c$$$ ] where $$$\frac{ik}{n} - B \leq c \leq \frac{ik}{n} + B$$$. It was enough to choose $$$B = 140$$$.

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

      Or, at least, among thousands of tests we generated, we never encountered a test where $$$B=140$$$ is not enough. Since codechef had a very small number of tests, $$$B=70$$$ is enough to get AC, I think. $$$B=300$$$ passes easily.

»
3 years ago, # |
  Vote: I like it +23 Vote: I do not like it

Why the time limit in the problem "BNSONSTR" was 1 sec. It's not like O(n^2) solutions will pass if you keep it to 2 sec. Because of the strict time limit, I was getting tle using "#define int long long".