Alpha_Q's blog

Invitation to CodeChef June Cook-Off 2020
By Alpha_Q, history, 5 years ago, In English

We invite you to participate in CodeChef’s June Cook-Off, this Sunday, 21st June, from 9:30 pm to 12:00 am IST. 2.5 hours, 5 problems.

We will also be hosting a live problems discussion session for Cook-Off problems with our panelist Rajarshi RestingRajarshi Basu on 23rd June, 4 pm IST. You can register by clicking on the GOING button at the top right corner 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 us on the problem setting panel are:

Prizes: Top 10 Indian and top 10 Global participants will receive CodeChef laddus, with which the winners can claim cool CodeChef goodies. Know more here.

Good luck and have fun!

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

Comments Comments (35)
| Write comment?
»
5 years ago, # |
  Vote: I like it +18 Vote: I do not like it

It would be great if we get CF rounds also from this trio.

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

Overlaps with SRM :(

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

Bump: who wants a ___ contest? Starts in ~699s ( ͡o ͜ʖ ͡o)

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

how to solve per capita?

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

    DSU and some implementation stuffs , note that we will take maximum value of fraction among the nodes and all nodes with maximum fractional value can be our answer.

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

    Just run DFS across nodes with same ratio from each node with maximal ratio and return the largest found connected component.

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

Editorials for all problems posted here. Hope you guys had fun!

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

Did anyone solve the last problem using suffix automata? If so, can anyone tell me why this code is giving tle? My solution has a complexity of O(N * K * 4).

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

    Have shared it with tester (I'm not good in cpp). He'll have a look.

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

    You should read the guide to auto-vectorization. Trying to vectorize/unrolling a code that isn't vectorizable will actually slow down your code.
    You code gets AC in 2.17 sec without those pragmas.

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

      Oh. I actually coded another solution without pragma, and that had an even more bad constant factor, so I added the pragma at that time. Didn't think it would slow down the code to the point of not getting AC. Nvm, thanks for informing!

      Btw, I ended up not solving any problem because of this xD.

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

How much time does it take to receive Laddus from CodeChef? I got top10 a month ago and I still dont have it.

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

Applied the Same Approach as in editorial for PERCAPTA, But getting TLE Please help https://www.codechef.com/viewsolution/34621506

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

    I think it's because of recursive dfs. I did it with while loop and got AC. My submission

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

      I was talking about PERCAPTA problem, not about CHKPTS

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

        Check now

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

          You've applied BFS, whereas I have applied DFS.

          Other than that the logic is same

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

            Got Accepted when changed your dfs to my bfs. Recursion works slow and I think if you had changed it to bfs or non-recursive dfs you would get AC.

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

              Yeah, I changed it to BFS and got AC.

              But Shouldnt the time complexity of BFS and DFS be the same?

              Here is my solution that I have implemented using BFS. https://www.codechef.com/viewsolution/34623172 This got AC.

              I implemented the same thing using DFS, but it got TLE. https://www.codechef.com/viewsolution/34621844

              Can anyone please explain why? Thanks

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

                I saw your code and I don't think its a dfs problem. You are recursively returning a vector.

                In the case where all nodes have max per capita income you will end up returning an ~ n vector from each of the n function calls, which will give you a quadratic complexity.

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

    Your DFS is $$$O(N^2)$$$ because of returning vector with current answer on each step. Just make this function void and it should pass, I think.

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

Could you please help. I got AC, here https://www.codechef.com/viewsolution/34623614 but WA https://www.codechef.com/viewsolution/34623659 here. The only difference is the vector sort of the key vector. Can anyone please tell me what is wrong with the second code.

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

    By default auto makes copy of elements across iteration. If you need to change content of the container you should use auto& which makes reference to element, not a copy.

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

Thanks for this contest, it was amazing and it went amazing, I became a 4 star :)

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

Easter egg: carry bed —> barrycade

→ Reply
»
5 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

In problem Per Capita Income I was getting tle when i used comparator function as 

bool com (pair p1, pair p2 ) {
  return (p1.F * p2.S >= p2.F * p1.s )
}

an got AC when i changed >= to >.

→ Reply
»
5 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

Help needed again, I am confused with how the C++ pow function works. I got AC in this https://www.codechef.com/viewsolution/34635562 (line 147) and WA https://www.codechef.com/viewsolution/34626034 (line 142). The difference between the two is only in the respective lines.

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

    The use of pow() implies a cast to double. Double used less than 64 bytes for precission, you get precission loss.

    You can instead use self written integer version of pow. Also, there is a good chance of making it work by casting the pow arguments to long double, since that uses more bits for precission, and the long double version of pow().

    → Reply