Unofficial Editorial - August Challenge 2019 Div 2

editorial
1

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

Link to my blog : Algo corner: Unofficial Editorial - August Challenge 2019 Div 2 - CodeChef

9 Likes
2

I updated my blog. :smile: I will try to solve Encoding.

3

It seems like first you tried to include and explain whole code but soon got bored and just added link to your solution :wink:

4

I’ll try to explain a bit more in details. I will update my blog soon enough. Thanks for the feedback.

5

that’s is actually great :blush: thanks for Chgoram solution

6

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

7

If you want to get add this approach in your blog, Let me know, I will prepare the editorial in detail.

8

That’s very nice. It would be great to have a editorial for encoding. :grinning: (I’ll add to the blog if it’s well written and I will mention that you wrote it)

1 Like
9

Great then, Send me your email id, I will send the editorial to you soon.

10

Prefer to exchange mails in a private manner. Ideally one shouldn’t expose his email in public for security reasons.

11

Ok, Sorry for that…

1 Like
12

you can post on code chef discussion and then i’ll add it into the blog. :grinning:

3 Likes
13

I solved CHGORAM using euler tour and BIT (segment tree should also work fine)

14

Please provide explanation of CHGORAM.

15

What part of the algorithm didn’t you understand ?

16

Can you please explain your approach? i.e. why did you do what you did?

17

Here’s my solution for CHGORAM: CodeChef: Practical coding for everyone

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

18

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 CodeChef: Practical coding for everyone
(functions : function isStar is for checking if the graph is a star and function star is to calculate the star case in O(n))

19

Did the setter’s notes not help?

20

Ah - I didn’t realise there were any (yet) for CHGORAM - whereabouts are they? :slight_smile:

1 Like