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

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

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://codeforces.net/blog/entry/15866

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

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

more contests for div2/div1 please....

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

vishesh312 setter orz

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

omg vishesh312 setter orz

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

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

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

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

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

When will be July Lunchtime prizes distributed ?

»
3 года назад, # |
  Проголосовать: нравится +53 Проголосовать: не нравится
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 года назад, # |
  Проголосовать: нравится +10 Проголосовать: не нравится

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

Why does the solution get -1.00 time?

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

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

»
3 года назад, # |
  Проголосовать: нравится +16 Проголосовать: не нравится
  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 года назад, # |
  Проголосовать: нравится +19 Проголосовать: не нравится

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

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

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

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

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

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

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

How to solve Chef 2 Chef?

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

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

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

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 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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 года назад, # ^ |
    Rev. 3   Проголосовать: нравится +1 Проголосовать: не нравится
    Hint 1
    Hint 2
    Solution
    • »
      »
      »
      3 года назад, # ^ |
      Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

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

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

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

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

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

      Actually I wrote best solution for small N and did OEIS

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

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

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

Editorials are out on Codechef Discuss!

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

C2C is similar to 1359D - Yet Another Yet Another Task, isn't it?

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

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

    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 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

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

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

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

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

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

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

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