Ashishgup's blog

By Ashishgup, 3 years ago, In English

We invite you to participate in CodeChef’s August Cookoff, today — 22nd August, from 9:30 PM — 12:30AM IST.

The contest will be 3 hours long. There will be 7 problems in Div 1/2 and 8 problems in Div 3.

The contest will be rated for all three Divisions. The July Cook-Off also marks the launch of our new prize structure for global & Indian participants. More details are given below.

Joining us on the problem setting panel are:

Problem Submission: If you have original problem ideas, and you’re interested in them being used in CodeChef's contests, you can share them here.

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 will get Amazon Vouchers worth Rs. 3750 each.
  • The rest in the top 100 will get Amazon Vouchers worth Rs. 1500 each.
  • First-time winners in Div 2 who make it to the top 200 for the first time will 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 will get Amazon Vouchers worth Rs. 750 each.

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.

Good luck and have fun!

Edit 1: Usually, there is no bound on the stack limit, and is equal to the total memory limit of 1.5 GB. But due to a system configuration issue, the stack limit for C++ is temporarily set to 8MB. So, if you believe that your code requires larger stack limit, please include this in your code — https://mirror.codeforces.com/blog/entry/15866

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

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

more contests for div2/div1 please....

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

    Next week's starters will be rated for Div2 as well :D

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

      Yeah! I was waiting for that.

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

      It still says Rated for Div.3 on website? And if it is rated for Div 2, please shift it as it is currently ends just one hour before Codeforces Deltix Round.

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

vishesh312 setter orz

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

omg vishesh312 setter orz

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

I have a question. Why is there always one or two testers in CookOffs/Lunchtimes, whereas there's so many testers in regular CF contests?

The last Lunchtime had — I think — slightly weak tests for a subtask (relevant discussion link). Having more testers would not necessarily fix that, but it would definitely increase the chances of fixing that I believe.

Of course, the problem quality is great, and I look forward to another contest with great problems!

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

    My simplest guess would be that Codechef has to pay their testers while Codeforces doesn't. Also in my experience, in addition to the tester, the contest admin usually tries a few solutions for the tougher problems and sometimes the setters try to submit bad heuristics as well so most of the time the most common incorrect solutions are covered during testing.

    In my opinion the biggest problem with having only one tester is that they must be skilled enough to solve the medium / medium-hard (maybe with some hints). So the easier problems (or easier subtasks) are often trivial for them. This usually makes it difficult to construct natural incorrect heuristics when the first thing that comes to your head is the correct approach. Also with the number of problems and subtasks I suspect quite often the easiest subtasks not even tested by anyone except the problem setter beyond asserting constraints.

    The same problem often arises with the problem setters who are familiar with the incorrect ideas they might have tried at first, but might miss some other extremely obvious incorrect solutions.

    However one more thing to be noted is that on Codechef you're often limited to an extremely small number of test cases, so its tough to cut off a lot of incorrect solutions.

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

    [more testers] would definitely increase the chances of fixing that I believe.

    Not necessarily. When there are so many testers, none of them feels pressure to find various issues. Each of them does a worse job than if he was the only one.

    More testers are good for finding multiple solutions and noticing that a problem already appeared somewhere.

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

      Just asking, if the testers themself dont know how many testers participate in the problem but only the coordinator know then will it increase even more the chance of making very strong testcases and block more heuristic code ?

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

When will be July Lunchtime prizes distributed ?

»
3 years ago, # |
  Vote: I like it +53 Vote: I do not like it
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.

Is it only me or does it seems like the Indian users are getting a considerably worse deal? This is especially strange from an Indian company.

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

Please read this announcement before the contest.

20:45 Aug 22nd: Usually, there is no bound on the stack memory, and is equal to the total memory limit of 1.5 GB. But due to a system configuration issue, the stack limit for C++ is temporarily set to 8MB. So, if you believe that your code requires larger stack limit, please include this in your code.
»
3 years ago, # |
  Vote: I like it +16 Vote: I do not like it

Why does the solution get -1.00 time?

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

    It might be because the interactor is getting TLEd, or waiting for input for a long time.

»
3 years ago, # |
  Vote: I like it +16 Vote: I do not like it
  1. I missed today's leetcode weekly contest, so I vced it later and solved https://leetcode.com/contest/weekly-contest-255/problems/find-unique-binary-string/
  2. Pressed button on my time travel machine and went to sleep.
  3. Woke up and solved https://www.codechef.com/COOK132A/problems/DIFSTR. Voila, my time machine works!
»
3 years ago, # |
  Vote: I like it +19 Vote: I do not like it

realized today why um nik always tells us to practice binary search (ref-INTEREQ)

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

How to solve Interactive Equality? Only thing I could think of is if I have a set of indices of size $$$x$$$ with answer $$$y < x$$$, then find the $$$1 \leq k \leq x - y$$$ such that randomly trying to remove k elements provides the minimum expected number of steps to identifying the set (can be initially precalculated with dp in $$$O(n ^ 3)$$$) but it got WA.

Is this along the lines of an AC solution or not?

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

    just binary search , feeling really amazed and enjoyed solving this problem

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

    You can binary search. Keep a maximal set of unique indices (1.. i) such that no two indices have A[i] = A[j] , when trying for i+1 if answer is 2, binary search for the index it is equal to, otherwise add it to the set.

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

    keep a track of indices of unique elements already found so far
    whenever u reach a new index, check if its value is already present in the set of unique elements
    if there isn't, we have another unique element
    otherwise we will binary search on the current set and see for which value freq is 2 ie
    mid=(l+r)/2
    if(query_for_subset(mid,cur)==2) {ans=mid; l=mid+1}
    else r=mid-1
    now finally we have the index with which current value matches

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

How to solve Chef 2 Chef?

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

    This was my solution, but I suspect there was an easier way.

    • Find all pairs of best / second best for each subarray (each second best can only have two possibly bests, the first larger (or equal) element in either direction, so precalc these in $$$O(n)$$$ using a stack, see this for more detail)

    • Now for each pair, we fix these as the elements chef will take (lets call them $$$l_{take}$$$ and $$$r_{take}$$$), now find the max we can extend outwards from these two without changing the best or second best ($$$l'$$$ and $$$r'$$$, where $$$l' \leq l_{take} \leq r_{take} \leq r'$$$, and all elements in the range $$$[l', l_{take})$$$ and $$$(r_{take}, r']$$$ are $$$\leq min(a_{l_{take}}, a_{r_{take}})$$$. This can be found using binary search + range max query using something like sparse table).

    • Then find best l where $$$l' \leq l \leq l_{take}$$$ which maximizes sum of elements in $$$[a_{l}, a_{l_{take}})$$$ using prefix sum + range max query. Do the same for the right hand side. The optimal segment for this pair is now $$$[l, r]$$$.

    • This takes $$$O(log n)$$$ per pair and checks all candidate answers in a total of $$$O(n logn)$$$.

    RMQ + Binary Search + Stack idea seems a bit convoluted for the solve count, is there an easier way?

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

      Nice Solution! But yep, we don't need the binary search at all. Jbtw, while testing the round too, we did observe the binary search a lot, but my original solution didn't plan to incorporate it :).

      Regarding your second point (where binary search is used) for extending outwards without changing the second best and the best, You could simply find the limit up to where you have to extend, by a further refinement on the conventional stack idea used in finding the next greater element.

      For reference, this is from the editorial.

      Spoiler

      Thanks for participating :)!

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

The rest in the top 100 will get Amazon Vouchers worth Rs. 1500 each

does this mean only top 100 in ranklist or top 100 excluding top 10 , or only top 100 indians ???

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

    Top 100 Indian participants excluding top 10 Indian participants. (Div1)

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

Kinda surprised CLEARARR was before ODDARY. Solved ODDARY within 20 mins while couldn't get a complexity of CLEARARR of less than O(k^2) for the rest of the 2 hours. Any hints for it?

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

      What if X is greater than, say only sum of the largest 2 elements of the array. How is doing the operation for other k-1 pairs optimal then? In case we are skipping some pairs, then how can we be sure that skipping the entire pair will always give better answer than skipping only one the two elements of the pair?

      Nvm, i got it. feeling stupid now :(

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

    I think you also didn't understood the problem statement. It was confusing for me. They have written "left most" and "right most"(which generally we consider as beginning or end of the array) but since they are telling left most for any index $$$l$$$ and right most for any index $$$r$$$ problem becomes the easiest one. just sort it and pick pair wise from the end satisfying the condition.

    By the way can we solve it in $$$O(NlogN)$$$ or in linear if we say we have to pick from the beginning or from the end only? (like Edit distance?) This version I was trying to solve during whole contest :/

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

Alternate solution for Odd Array:

  1. Brute force for small $$$N$$$
  2. Notice the pattern $$$1,2,1,3,1,2,1$$$
  3. Profit
  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Hmm..can you elaborate? My solution was with Grey's code.

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

      Actually I wrote best solution for small N and did OEIS

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

      I initialized the array with 0 Then for each k 1 to N, i brute forced each time from beginning and checked for a[i]=0 elements for each even positioned a[i] =0 set value to k This way i precomputed the array in O ( n²)

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

      You just notice that the pattern of repeating a prefix when you hit current maximum just works, so the final answer will be of form:

      1 2 1 3 1 2 1 4 1 2 1 3 1 2 1 5 1 ...

      So it's an easy, guessable solution. :P

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

Editorials are out on Codechef Discuss!

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

C2C is similar to 1359D - Очередная очередная задача, isn't it?

I think that the solution mentioned here can be extended to handle two maximums instead of one.

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

    Hahaha yes! This problem was my motivation behind C2C. But it's way toned down like you also can easily exploit the range of array elements in the CF problem.

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

I have another solution for Chef and Closure, simply sort array a, check if a[0] * [1], a[n - 1] * a[n - 2], a[0] * a[n - 1] are all in array a. I don't know why it works though :v

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

    mine method : you can use max and min product of subset and then compare both max and min element of array example : int m = max product of subset , int mn = min product of subset

    this concept...

    then simple use:

    sort(arr,arr+n);
      int  x=arr[n-1];
      int  y=arr[0];
      if(m<y || mn>x){
          cout<<0<<endl;
      }else{
          cout<<1<<endl;
      }
»
3 years ago, # |
  Vote: I like it +130 Vote: I do not like it

Here is some feedback on the contest:

  • DIFSTR: Nice easy problem.
  • CLEARARR: Very nice easy problem.
  • ODDARY: I enjoyed this one. At first, I thought the answer had to be always $$$\le 3$$$. I like that this is not about some tricky uninteresting construction, but it is about having the right insight. It is cool when the problem seems "open-ended" but it is not.
  • INTEREQ: Ok problem, not particularly original (after all, it is a binary search). I would say that the problem poses an interesting question, but the solution is not that interesting. I was annoyed by the interaction format. There is no need to give $$$Q$$$ ($$$=6N$$$) in the input, and there is no need to answer $$$1$$$ or $$$-1$$$ depending on the correctness.
  • C2C: A bit boring. After reading it I immediately thought "with a divide-and-conquer approach and some coding I will solve this in 1 hour" and it was true (my solution is $$$O(n\log(n)^2)$$$).
  • MAXJMP: The statement is clean and interesting (after all, it's a natural question), the solution is standard (I had to stop competing 1h30m into the contest, otherwise I would have had a good chance of solving this one). I thought about this one while on public transport and I enjoyed thinking about it, cute problem.
  • CONSSTR: Did not read the statement.

Thanks to the authors for the contest.

By the way, the overall quality of Codechef contests really improved compared to some years ago.

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

    Thanks for the feedback! Btw, I think your opinion on C2C might be coloured by your solution — the editorials are out, and the editorial solution is clean enough to be implemented in a few minutes (in my opinion)

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

    Thanks for the feedback! We are working on improving all parts of making contests, not everything is there yet, but we are getting better.

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

If you are interested in writing checker for ODDARY, try this problem.

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

When will the prizes for this contest be distributed and how to claim them? Will we be getting any confirmation email regarding this?