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:

- Problem Setter: bciobanu(Bogdan Ciobanu), Fekete(Ivan Fekete), jtnydv25(Jatin Yadav), vipsharmavip(Vipul Sharma), kingofbugs(Hrudai Pabbisetty), avada__kedavra(Shivangi Gupta), PraveenDhinwa(Praveen Dhinwa)
- Problem Tester: triveni (Triveni Mahatha)
- Problem Editorialist: adkroxx (Adarsh Kumar)
- Statement verifier: Xellos ( Jakub Safin) and arjunarul(Arjun Arul)
- Russian Translator: CherryTree (Sergey Kulik)
- Mandarin Translator: huzecong (Hu Zecong)
- Vietnamese Translator: VNOI Team

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!!

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.

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

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

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

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.

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.

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. :)

My score is not getting updated Its updated thank you

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.

PraveenDhinwa Is there a policy for this kind of "potential" cheating scenario ?

this happens on a large scale specially in long challenges .. if one submits from his college his solutions the number of submissions drastically increased and nothing has done yet to stop this by cc

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

Editorials have been published at Codechef Discuss.

The link is not working UPD — It started working thanks!!

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).

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

`prime[i][j]`

is 1 ifi^{th}largest prime dividesA[j]`facts[i][j]`

is 1 ifj^{th}largest prime dividesi(he could have had just a array of arraylist here)He is basically making note of the position of occurrence of each prime. For

xandyto 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 thisBut if the constraints where larger

N,Q< 10^{5},A_{i}< 10^{6}(primescount= 78498) then it could have failedIn 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.

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 :)

Thank you :)

Just wanted to say, it's actually 4

N.