SAeed's blog

Invitation to CodeChef October Mega Warm Up Cook-Off 2017!
By SAeed, history, 7 years ago, In English

Hello CodeForces Community!

Gear up this October and accelerate your programming minds for this month's Mega Cook-Off. This is the last mega warm up which will help you win the final race in the upcoming ACM ICPC 2018. So hurry up, note down the details and be there. Joining me on the problem setting panel are:

  • Problem Setters and Editorialists: SAeed (Saeed Sryhini) & Mhammad1 (Mohammad Shahhoud)
  • Problem Tester: kingofnumbers (Hasan Jaddouh)
  • Russian Translator: CherryTree (Sergey Kulik)
  • Mandarin Translator: huzecong (Hu Zecong)
  • Vietnamese Translator: VNOI Team

Note: Top 25 Indian students will be eligible for ACM ICPC regional travel reimbursement. Each of them shall be reimbursed an amount of upto INR 1500 upon producing the travel bills. For more details visit: https://www.codechef.com/icpc/2018.

I hope you will enjoy solving them. Please give your feedback on the problem set in the comments below, after the contest.

Contest Details:

Time: 22nd October 2017 (2130 hrs) to 23rd October 2017 (0000 hrs). (Indian Standard Time — +5:30 GMT) — Check your timezone.

Contest link: https://www.codechef.com/COOK87

Registration: You just need to have a CodeChef handle to participate. For all those, who are interested and do not have a CodeChef handle, are requested to register in order to participate.

Prizes:

  • Top 10 performers in Global and Indian category will get CodeChef laddus, with which the winners can claim cool CodeChef goodies. Know more here: https://www.codechef.com/laddu. (For those who have not yet got their previous winning, please send an email to winners@codechef.com)

Good Luck! Hope to see you participating!!

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

Comments Comments (25)
| Write comment?
»
7 years ago, # |
  Vote: I like it +17 Vote: I do not like it

It's great to see a contest prepared by my teammates. I think it will be awesome :D

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

How to solve Chef and Dancing Steps?

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

    For each index i, find the rightmost index j such that XOR(j...i) >= m. You can do it by inserting prefix XORs into a trie and processing from left to right.

    Now the problem reduces to -
    For a given subarray [L, R], find the minimum value of i-rightmost[i]+1, such that rightmost[i] >= L. This can be done offline using segment tree or online using persistent segtree.

    Code

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

    First assign . Now a query [qL;qR] becomes:

    Find such i and j (qL - 1 ≤ i < j ≤ qR) such that and j - i is minimum.

    Well for every position i we will find the closest position Li to its left, such that . This can be done with a trie in time. We notice that for every query we are interested in only such pairs (Li, i).

    Well now the query [qL;qR] becomes:

    Find the minimum i - Li, such that qL ≤ Li and i ≤ qR. This is a well known problem which can be solved offline in time. Lets consider all queries and pairs (Li, i) as events. We sort all events by their right end and start iterating them from left to right. We will have a segment tree for minimum. Now if the current event is an update (one of the (Li, i) pairs), we update position Li with i - Li. If the event is a query, the answer will be the minimum in [qL - 1;qR].

    There is also another online solution using binary search on the answer. The complexity after the trie part will be using a segment tree or using a sparse table.

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

      I got the idea for this question but I was unable to implement the trie properly?? Can you tell me how to find the largest Li using trie ??

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

        Maintain a max_index property for each node of the trie, which stores the maximum index of the array whose value was inserted into the trie and whose leaf is in this subtree. Now, suppose you want to find max index for given value val. Iterate through the bits from MSB to LSB.

        If ith bit of val is 0 and ith bit of M is 1, go along direction 1.
        If ith bit of val is 0 and ith bit of M is 0, compare global ans with max_index of 1-subtree and go along direction 0.
        If ith bit of val is 1 and ith bit of M is 1, go along direction 0.
        If ith bit of val is 1 and ith bit of M is 0, compare global ans with max_index of 0-subtree and go along direction 1.

        You can see the code I linked in my comment above for this.

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

especially when Joud says: We're coming, We're back!

We're coming, We're back... Next Year. :P

Nice problems :)

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

    Thanks. Hope to see ACM back... Next Year :P

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

      Thanks for making me lose my job with that problem...

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

        No, I'll give you another chance, but don't study again at work xD

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

        You didn't lose your job. We gave you a fair chance. Actually 4 people managed to use that chance and got the problem accepted xD.

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

For Chef and Dancing Steps, can someone please point out a mistake in this algorithm-- Calculate the latest index i for each array index j such a(i)^a(i+1)...a(j) >=M Answer the queries offline, while moving left to right in the array, update at index last[i], the value i-last[i]+1. For each query ending at r, calculate the minimum value in the range(l,r) and that is the answer for that query.

I could not find any mistake in my solution. Any help would be really appreciated Code

UPD: Found the bug.One of the array size was 1e6 instead of 1e7

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

How to solve 5th problem?

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

    Centroid decomposition

    If you subtract the mean Y from all values of the array, you need to count the number of paths such that the sum of new values on the path is >= 0 and the number of values <= X on the path is <= (L+1)/2 where L is length of the path.

    I could not finish coding this on time during contest. After I submit in practice, I will link the code here for reference.

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

      Now i finished to code last problem. Here is my code. Now i tested with random samples, unfortunately my code works in 4sec (the problem's time limit is 3sec). My solution uses Centroid Decomposition with Fenwick and Ordered set. How can i optimize my code? I used Fenwick and Ordered set to find the number of pairs(C,D) bigger than another pair (A,B) such that C>=A and D>=B. Can i use another data structure to decrease time?

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

        What's your code complexity?

        The intended complexity is: O(N.Log2(N))

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

        Ordered set has a very high constant factor. Why do you need ordered set? Just sort the given points in increasing order of sum of new_values. Then process from right to left and use 1-D Fenwick tree to maintain the condition of the count of values <= X. At any point in time, the Fenwick tree only contains those values which already satisfy the "sum" condition for the current index you are processing.

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

          Thanks for your help. Finally got AC, works in 0.46 sec. Here is my submission.
          Btw Thanks for contest.

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

When the rating may get updated? I have participated for the first time.

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

    Search your username here : codechef-rating-predictor.7e14.starter-us-west-2.openshiftapps.com/contest/COOK87/all/

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

How to sleep at night after your solution gets WA because you missed long long in assigning value to a single variable :/ ?
Nice problems btw :)

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

Please point out some common silly mistakes that can be made in Chef and Dancing Steps. I got WA during contest, not able to find any error till now.

Code

UPD: nvm, Found it

→ Reply