May Long Challenge 2019 sponsored By ShareChat

Greetings CodeChef community!

Programmers all over the world are invited to participate in CodeChef’s May Long Challenge sponsored by ShareChat. This is a long contest which is spread over 10 days and offers 7 binary/subtask problems and 1 tie-breaker problem for you to solve. The Long Challenge offers great practice and learning opportunities and a chance to improve your rating.

The problem statements will be available in English, Hindi, Bengali, Russian, Mandarin and Vietnamese.

CodeChef’s contest sponsor, ShareChat, is seeking both interns and full-time employees to join their team. Job opportunities are open to programmers across the world and internship opportunities are exclusively aimed at final year B.Tech students who have already been placed and looking to gain startup experience. Visit the contest page for more details.

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

I hope you will enjoy solving them. Please give your feedback on the problem set in the comments below, after the contest.

Contest Details:

Time: 3rd May 2019 (1500 hrs) to 13th May 2019 (1500 hrs). (Indian Standard Time — +5:30 GMT) — Check your timezone.

Contest link:

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.


Top 20 performers in Indian category and top 10 performers in Global category will get CodeChef laddus, with which the winners can claim cool CodeChef goodies. First to solve each problem except challenge - 100 laddus. Know more here: (For those who have not yet got their previous winning, please send an email to

Good Luck!

Hope to see you participating!!

Happy Programming !!

The contest is over
Congrats to the winners!

Div 1

  1. kut_hbi1998

  2. andersk

  3. abdullah768

Div 2 (dominated by China)

  1. lihao888

  2. heltion

  3. minamoto

Sketches of solutions in my blog:


Hello! What should do, if the example cases explanation is not clear? Can I post a comment to problem asking to clarify the given explanation? Few days ago I posted a couple of comments to the following problem but didn’t get any reply
TREDEG (problem setter: vivek_1998299 )
I saw a couple of times that such questions were responded.

I checked the comments, and I can’t see your question.

Very strange, because I can see all my three comments…
Anyway, let me duplicate it here:
“I do not understand neither the problem nor its explanation. In case 1 where this expression ((1⋅2⋅1)^1+(1⋅1⋅2)^1+(2⋅1⋅1)^1)/3 came from?”

Thanks you for the reply!

Overall this long was interesting. Expecting longs with this difficulty in future as well :stuck_out_tongue:
But I really hate tight tl of Pklves.
Idk If I should hate SONGIF. I didnt knew there exists something known as Fast Hull.

Can someone explain how to solve TREDEG ?

1 Like

The questions were really nice. Kudos to all the authors. TreeDeg being my favourite(took me 3 days to solve the third subtask). Sonia and gifts was an another heavy implementation problem, unfortunately I could not find my bug till the last moment. :frowning: Expecting Codechef to be back with such questions next Long also :pray:t2:


@alei Please post hints for curek.

1 Like

According to Lewin: Your first step is correct to just get the cost. To get the order, you can do something like finding the ear decomposition of each component. It’s also called a bipolar orientation, so you can find some stuff online on how to do it also


Codechef Long Challenge never consists of problems related to dynamic-programming,there was one this time, but it was for div-2,please try to put some dp in long challenges rather than just heavy implementation(as dp is a very imp part of cp and long challenges neglect it), or else the challenge was very good :slight_smile: Keep it up :slight_smile:

For the first part of CureK, where the graph is a tree, I found a simple solution. The key point is that the graph must remain connected as cities are treated.

First find how many leaves there are, these being nodes linked to only one other node. Choose the leaf with the maximum weight to be the root of the tree. Then set all the other leaves to be the initially chosen cities. Navigate the tree from the chosen root by DFS, recording the cities visited in order. Then if we visit these cities in this sequence reversed, the problem is solved.

You can find my solution at

For the case where we have a general graph, this method will not produce the right answer. I was unable to think up a suitable strategy for the general case.

He has already solved for 50 points days ago,he asked for the solution of last 50 points.

Please don’t say that… DP takes all of my ratings away… :joy::sob:

1 Like

6 star coders enjoy… I still don’t know what people are talking about… Decomposition and what not… :sweat_smile::sweat_smile::sweat_smile:
Will learn from this long though :grinning:

1 Like

Same situation here​:joy::joy::joy:
Nope,hard dp problems help me, for example,Chefsoc(dp problem) In March made me yellow, and adarooks(weird-problem) kept me yellow in may… Kab tak chalega aisa?:joy::grin::grin::joy::grin::grin:

1 Like

Ye to cheating hai !! :joy::joy:

1 Like