radoslav11's blog

Invitation to ‘CRED’ CodeChef March Lunchtime (Rated for all) — 19th March
By radoslav11, history, 3 years ago, In English

We invite you to participate in CodeChef’s March Lunchtime, this Saturday, 19th March, rated for all.

Time: 8:00 PM — 11:00 PM IST

Bangalore-based credit management app giant CRED is on board to hire candidates from the Chef's pool.

Who can apply?

Anyone with 1-3 years of experience in product development, architecture, and design. In short, 2019/2020/2021 graduates are eligible to apply.

Where is the application form?

Visit the March Lunchtime contest page to check the JD & application form.

Joining me on the problem setting panel are:

Prizes:

  • Top 10 global Division One users will get $100 each.

  • Top 25 Indian Division One coders to get Amazon Vouchers worth Rs. 1500 each.

Also, announcing Scholarship for CodeChef Certification in Data Structure & Algorithms — More than 100 Indian participants in Divisions 1, 2, and 3 will win scholarships for the CodeChef Certification exam (discounted prices). Scholarship criteria can be found in the respective contest pages.

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.

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. Hope to see you participating.

Good Luck!

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

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

How to solve Mathology for full points? I was able to solve only 2 subtasks (5+10 score).

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

    Same..

    I tried square root decomposition and segment tree ideas but they didn't work within TL.

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

      Were you using MO's algorithm ?

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

      What was your idea?

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

      You can solve it using sweep-line on an array by noting that there can be at most $$$d$$$ divisors of a number where $$$d \approx 200$$$.

      I was able to cheese an $$$O(Q d \sqrt{N} \log \max_{i} a_i)$$$ solution that used Mo's algorithm and Fenwick tree, so tests were probably weak. The complexity might be better though, since I took some care to avoid adding an element to the set of possible GCDs more than once.

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

        My solution was $$$O(dn\log(dn + Q) + Q\sqrt{N})$$$ without Mo and Fenwick, thanks to some recently published trick of -is-this-fft- (point remax in $$$O(1)$$$ and prefix max in $$$O(\sqrt{n})$$$ as there are a lot more operations of the first type than that of the second). However, it still took 1.48s.

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

        I solved it with offline solution using sweep line using segment tree to find range maximum queries — the complexity was O(N * d * log n + q * log n) but I got TLE so I noticed that number of updates in the range maximum queries is O(N * d) while number of queries is only O(Q) so I replaced segment tree with standard sqrt decomposition which is faster to update slower to query, the complexity became O(N* d + Q sqrt N) which passed the tests.

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

    My solution was like this:

    Initialize an array $$$mx[n]$$$ with all values equal to $$$1$$$.

    Iterate over the array $$$a$$$. While iterating at index $$$i$$$, iterate over all the divisors of $$$a_i$$$. Let the divisor we are iterating currently be $$$d$$$. Find the maximum index $$$j$$$ such that $$$j<i$$$ and $$$d$$$ is a divisor of $$$a_j$$$. Now, update $$$mx_j := max(mx_j, d)$$$. After processing all the divisors of $$$a_i$$$, we can process all the queries having $$$r = i$$$. The answer of each query having $$$r = i$$$ is $$$max(mx_l, mx_{l+1}, mx_{l+2}, ..., mx_r)$$$ which can be solved using segment tree.

    The complexity is $$$O(n\times k \times \log{n})$$$ where $$$k$$$ is the maximum number of divisors of a number which is $$$128$$$ for $$$a_i \leq 10^5$$$.

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

      Just use sqrt decomposition instead of segment tree to find the max, you will get better complexity, using segment tree I got TLE.

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

        I got TLE for the first time. But, by using the bitwise operator inside the segment tree and iterating over the divisors in descending order got accepted. Iterating in ascending order over the divisors was re-updating the value of $$$mx_j$$$ for different divisors.

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

In Mathology, after a trivial observation, that it is optimal to choose a subsequence of size 2, the problem becomes the same as this problem

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

    But, it's editorial is not available there ig!

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

I missed 100 points and 27 rank because of that :/ 

for (int i = 0; i <= n; i++) adj[i].clear();

SPRALL has multi-testcases and i forget to clear the array :/ I only remembered 1 second after the contest

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

Should Have Solved SUBSEQ first :-(

→ Reply