adkroxx's blog

Invitation to CodeChef March Long Challenge 2018!
By adkroxx, 7 years ago, In English

Hello CodeForces Community!

To get the month of March off to a great start, I would like to invite you to Chef’s March Long Challenge 2018! With questions spread across ten days, this contest will let you have an active competitive programming routine.

I hope you will join your fellow programmers and enjoy the contest problems. Joining me on the problem setting panel are:

Please give your feedback on the problem set in the comments below, after the contest.

Contest Details:

Time: 2nd March 2018 (1500 hrs) to 12th March 2018 (1500 hrs). (Indian Standard Time — +5:30 GMT) — Check your timezone.

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

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 global and top 20 Indian winners get 300 Laddus each, 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!!
Happy Programming!!

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

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

What was the need for making separate divisions on Codechef? A more important feature would have been of enabling virtual participation in the previous contests.

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

The fourth easiest problem is not available to Div 1, but the third easiest problem is.

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

Today codechef has introduced division feature like codeforces. Partial scoring too should have been removed.

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

    No, the partial scoring is good to distinguish in between performances.

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

      Having partial scoring in contests , you do not try harder with your full potential, instead you apply brute-force on standard problems knowing that it will pass the subtask with smaller constraint . So zero learning.

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

        I don't think there should be subtasks which pass brute force, but there should be partial scoring for a problem, where say,

        There is O(n^2) DP solution.

        It becomes O(N log N) with a segment tree.

        And it's O(N) with greedy.

        In this case, a contestant who was able to come up with the DP solution should be distinguished from a contestant who couldn't come up with any solution.

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

I'm not really sure where I should write this, but I figured this is as good a place as any.

My CodeChef rating is about 1680. It's about 400 points higher than my CodeForces rating, and I believe it's inflated because I haven't participated in that many contests.

In this contest, I really enjoyed solving problem 5. It was quite difficult for me.

The problem is if I enter Div 1 as a result of this contest, then next month this will be Problem 2 and it would be severely demotivating for me if I can't do it.

I understand high rated users about 2300+ on CodeChef might not like to solve the easy problems, but I think most 1800's on CodeChef would like to see the 3 easy problems of the contest.

If the purpose is to save high rated user's time and not let them waste it on easy problems, I believe the threshold should be higher.

Also, it's understandable for Div 1 users to not have to waste time in solving the three easy problems.

But, the three hardest problems should still be in the Div 2 problemset. After all, there's no time constraint as it is a 10 day contest. No harm in putting it in the problem set. :)

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

I advice somebody in charge to take a look into the following case and check for plagiarism if possible.

So yesterday I received this message on Facebook, which translates to something like "Hi, could you give me some hint for that problem with triangles from Codechef?":

Here is the Bulgarian text, in case you want to convince yourself about its meaning using a translator: хей, здрасти, дали можеш да ми дадеш насока за тази задача с триъгълниците от codechef ?

Of course, I simply ignored it and forgot about it, since I had never heard of that guy. Today, though, I decided to check the standings and saw that he had solved accepted that problem and is currently on a not-so-bad spot in the standings:

I can't know if he has solved it himself or somebody gave him hints or even code, I just know that he is prone to cheating. So if there is some way for somebody to check that, it would be good, I think.

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

Can someone tell the solution of the CUTTREE and the CHEFKNN problem?

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

How to solve GCDCNT using BitSet? The contest had many of the successful AC's with the help of BitSet.

Can anybody explain me the approach with BitSet? Here is one AC solution (Java solution).

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

    It's a pretty cool solution ! It's like a optimized bruteforce.

    prime[i][j] is 1 if ith largest prime divides A[j]

    facts[i][j] is 1 if jth largest prime divides i (he could have had just a array of arraylist here)

    He is basically making note of the position of occurrence of each prime. For x and y to be coprime , they shouldn't have any prime divisors in common . Since computing that directly is hard , we take everything in range and subtract the ones with atleast 1 common prime factor. That's where you get this

    while (next != -1) {
    ChefAndGcdQueries.Prime p = primes[next];
    b.or(p.div);
    next = facts[G].nextSetBit(next + 1);
}
int ans = count - b.get(L, R + 1).cardinality();

    But if the constraints where larger N, Q < 105, Ai < 106 (primes count =  78498) then it could have failed

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

In PSHTRG, we need to create a seg-tree for the array of size N.

Since, N is 10e5, the seg-tree of size 2^N will not fit into memory. Am I missing something?

Edit : Sorry, there were misleading blog posts indicating the size of seg-tree size to be 2^N.

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

    To create a segment tree for an array of size N(N <= 100000), it would be safe for you to allocate around 5*N memory. 2^N does not sound right. Perhaps the concept isnt clear to you.

    Check out this video by Tushar Roy:

    Click

    Cheers and Happy Learning :)

    → Reply