I made a short editorial (not complete, i’ll complete it later). The contest was very nice (especially Chef and Gorden Ramsey) and this was my first long challenge.
I updated my blog. I will try to solve Encoding.
It seems like first you tried to include and explain whole code but soon got bored and just added link to your solution
I’ll try to explain a bit more in details. I will update my blog soon enough. Thanks for the feedback.
that’s is actually great thanks for Chgoram solution
Encoding can also be done by this approach :
If you are given a number N, calculate total plane sum from 0 to N and then calculate the loss (Ex : N = 1100 , loss = 100 because 1000 will be included) and then plane sum - loss will be the sum from 0 to N with given conditions. Now answer will be this sum for R - this sum for L-1.
Here is my solution : https://www.codechef.com/viewsolution/25870951
If you want to get add this approach in your blog, Let me know, I will prepare the editorial in detail.
That’s very nice. It would be great to have a editorial for encoding. (I’ll add to the blog if it’s well written and I will mention that you wrote it)
Great then, Send me your email id, I will send the editorial to you soon.
Prefer to exchange mails in a private manner. Ideally one shouldn’t expose his email in public for security reasons.
Ok, Sorry for that…
you can post on code chef discussion and then i’ll add it into the blog.
I solved CHGORAM using euler tour and BIT (segment tree should also work fine)
Please provide explanation of CHGORAM.
What part of the algorithm didn’t you understand ?
Can you please explain your approach? i.e. why did you do what you did?
Here’s my solution for CHGORAM: https://www.codechef.com/viewsolution/25925347
Contains heavily-commented code, plus a high-level overview of the approach used and why it works.
It’s probably about the most detailed resource on this question until the official Editorial comes out
Let’s take the exemple of the question :
1 4 2 1 3 1 2 2 3 2 4
My algorithm for this exemple :
Take a node (let’s say 2). Add 2 to the indexed set.
Then, I will go through all of the unvisited neighbours of 2. Add them (node 1,3 and 4) to the indexed set and calculate* the number of answers for them. After this we can calculate* the number of answers for 2.
(*) We can see that we can calculate the number of solutions for a current node (taking it as the middle), knowing the number of nodes bigger than the current node and smaller than the current node.
My solution https://www.codechef.com/viewsolution/25691825
(functions : function isStar is for checking if the graph is a star and function star is to calculate the star case in O(n))
Did the setter’s notes not help?
Ah - I didn’t realise there were any (yet) for CHGORAM - whereabouts are they?