radoslav11's blog

Invitation to CodeChef July Lunchtime 2021 — Saturday, 31st July, 6 PM IST
By radoslav11, history, 3 years ago, In English

We invite you to participate in CodeChef’s July Lunchtime, this Saturday, 31st July.

Time: 6 PM — 9 PM IST.

The contest will be rated for all three Divisions. We also have a new prize structure for global & Indian participants. More details are given below.

Joining us on the problem setting panel are:

Prizes: Global Rank List: Top 10 global Division One users will get $100 each. Non-Indians will receive the prize via money transfer to their account. Indian users will receive Amazon vouchers for the amount converted in INR. Indian Rank List: Top ten Indian Division One coders to get Amazon Vouchers worth Rs. 3750 each. The rest in the top 100 get Amazon Vouchers worth Rs. 1500 each. First-time winners in Div 2 who make it to the top 200 for the first time get Amazon Vouchers worth Rs. 750 each. First-time winners in Div 3 players who make it to the top 200 for the first time get Amazon Vouchers worth Rs. 750 each. However, everything else about our previous Laddu system for Lunchtime will continue without any change. To call out specifically, the top 10 school students in Div 1 of Lunchtime will continue to get Laddus as well as the cash/Amazon vouchers as per the new system. 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.

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.

Hope to see you participating. Good Luck!

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

Comments Comments (31)
| Write comment?
»
3 years ago, # |
  Vote: I like it +2 Vote: I do not like it

ICPC Amritapuri Mock round also at 6 pm today. Why CodeChef always changes the time for its monthly contests.

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

    Unfortunately there is also a Topcoder Open contest today which was clashing with our usual time slot. After speaking with both TopCoder and Codedrills, we have decided to have the Lunchtime at 6pm. The clash with the ICPC Practice Contest is unfortunate and sadly unavoidable.

    The clash with ABC was not known till a few hours back, and we have reached out to them to see if they can reschedule it. But it is too late for us to reschedule the Lunchtime now.

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

Clashes with ABC :(

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

Please shift it to 8:30 pm or 9 pm .

It will benefit most people here.

As ICPC mock test is also from 6 PM.

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

Moni moni $$$‿$$$

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

Is nlogn DP intended for div2D? How to avoid map then? I kept receiving TLE on one test.

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

    changing to unordered_map worked for me

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

      Unfortunately, for me it didnt help. Can't wait to see official solution :)

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

      same

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

    One trick would have worked. use mp.count() to avoid adding unnecessary elements to map. Unfortunately realized this after contest :)), it passed. Kept getting TLE throughout the contest.

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

    After a lot of sub, adding 2 things worked for me:
    1) instead of a map for each bit, save 1 map only. For number i and bit j, store result in i*100+j.
    2) Use PBDS hashmap instead of unordered_map.

    I'm interested in knowing how these time limits got approved.

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

    Please tell your approach.

    For me, an array of size O(log(A[i])) is enough.

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

      Dp[i][j] <-> number of sequences in prefix [1...i] if we formed exactly j groups (and the end of the last one is at point i). To transition I need to ask about sum of previous DP's with particular XOR of prefix, or I need to get last index of particular prefix xor modulo $$$2^{j-1}$$$ for j <= 60. How is small array sufficient for you?

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

        The transitions become much harder this way.

        Instead of prefix,use suffix because : If group j starts from index i, then xor of suffix [i...n] is multiple of 2^j. and (j+1)th group can start from any index k > i without disturbing jth group.

        Then, DP[i][j] => Number of sequences in suffix [i...n] where $$$j_{th}$$$ group start from $$$i_{th}$$$ point.

        For transitions,

        1) suffix[i...n] is the last group : 1 way

        2) next group starts at index k > i : DP[k][j+1] ways.

        So we can just store sums of DP[i][j] for each j. Ideally we would have to maintain it for j <= n (when xor is 0,we can have many groups), but again all values after j >= log(A[i]) will be same.

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

I've always wanted to ask that CodeChef is based in India and in India, the time at which CodeChef Lunchtime happens is more like dinner time than lunchtime. So why this contest is named Lunchtime?

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

Btw for div1 are the prizes for all indian participants who are in global top 100 or top 100 indians? I mean there are not even 100 Indians who solved a single problem.

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

How to solve Ancient Magic ?

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

    There is 2 ways : a) Have a good graph and run max flow min cost on it. By good graph i mean, graph with not too many edges, not too many nodes. There s multiple ways to contruct such a graph with n logn nodes, n log n edges, one of them is described in the editorial on codechef. b) Use a modified version of the RSK algorithm to account for weights.

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

ABC and Lunchtime clash

Tourist: Let me quickly AK ABC fast so I can make it in time to win Codechef Lunchtime

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

Can someone clarify rest top 100 refers to the Indian ranklist or Global? As of today, less than 80 Indian participants were there. So, will everyone be getting amazon vouchers?

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

Very subtask, much wow

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

In problem BADLUCK, I lost 15 points because of an interesting TLE, and need help understanding why it happened.

AC: 20pts solution
TLE: 5pts solution

The difference between them: in the TLE code, I am maintaing a separate permutation vector and indexing into the original vector using the permutation indices. And in the AC code, I am directly permuting the input array.

The AC code passes in 0.4sec whereas TLE code fails in 1.01 sec, so I think the difference is huge. I would expect TLE code to be slower but not by a factor of 2.5.

I know that this might have something to do with locality of reference while caching, but the vector size is only 11 or less. Why would caching effects be so pronounced in such a tiny vector?

Or is there some other issue here? I've used permutation arrays frequently in the past in such situations so I'm sad and surprised that it failed today :(

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

    Ah.. that was BADLUCK for sure :(

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

    Testcases might be weak where array might contain duplicates. In that case, your AC will cover only distinct permutations while your TLE code generates all permutations.

    Example — array is [5,5,5,5,5,5,5] then your AC code generates only 1 permutation while your TLE code generates 7! permutations.

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

      Thanks, it seems tests are indeed weak. I ran my 20 points code for this test:

      5
11 10 20
15 25 40 60 85 115 150 190 235 285 340
5 10 20
15 25 40 60 85
5 10 20
115 150 190 235 285
5 10 20
15 25 235 285 340
5 10 20
15 25 40 285 340

      and it ran in 6seconds on my machine. So during contest it should have clearly failed and gotten 5 points only.

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

My solution to Matrix Permutations was quite different from editorial.

The idea is similar to GCJ2017 Round 3 problem D. First observations are the same as in editorial: we only need to find array $$$cnt$$$ such that $$$cnt[i]$$$ is the number of cells with distance to closest cannon being exactly $$$i$$$. Let's fix some cannon $$$A$$$ and calculate $$$cnt$$$ for all cells such that the closest cannon to them is $$$A$$$. And to make it easier, let's split plane around cannon $$$A$$$ into four quarters and process each one independently. Without loss of generality I will assume it's upper right quarter.

Let's choose some cannon $$$B$$$ and find all cells in this quarter such that they are closer to the $$$A$$$ than to the $$$B$$$. There are 4 possible cases (I will not consider equal coordinates):

1) $$$x_B < x_A$$$, $$$y_B < y_A$$$, then all points are closer to $$$A$$$
2) $$$x_B < x_A$$$, $$$y_B > y_A$$$, then either all points are closer to $$$A$$$, or there exists some $$$y$$$ such that points below $$$y$$$ are closer to $$$A$$$ and others are closer to $$$B$$$
3) $$$x_B > x_A$$$, $$$y_B < y_A$$$, this is similar to previous case, only now we have vertical border
4) $$$x_B > x_A$$$, $$$y_B > y_A$$$, this is the most interesting case, and there are two possibilities

One
Two

And we need to find this blue area for each cannon $$$B$$$ and then find intersection of all of this. I won't go much into details, but if you look at the border as a function $$$f(x)$$$, then you have some horizontal segments and some diagonal segments. Then there are at most $$$2k$$$ interesting points and between each consecutive pair you can find lowest diagonal segment and lowest horizontal segment and then intersect them again if needed. This all can be done in $$$O(k \log k)$$$

After that you end up with pieces of two types:

One
Two

Each one you can split into two or three more parts as shown above. And then for each part you have to add some linear function to a segment of array $$$cnt$$$, which can be done offline in $$$O(1)$$$.

The total complexity is $$$O(K^2 \log K + N + M)$$$

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

    thanks Maksim1744 for sharing your approach. It will help a lot of people see the problem from a different perspective. Congratulations on being the only person to solve this problem.

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

    Thanks for sharing your approach. I also tried to approach it the same way. I considered all cannons at the same time and marking cells nearest to one particular cannon, trying to build Voronoi diagram with Manhattan distance as distance function instead of euclid distance.

    Didn't manage to solve it.

    → Reply