Hello Fellow Coders!
The month of April held a special significance in the programming world, with the ACM-ICPC World Finals crowning a new world champion. So how about you cap off this brilliant month with Chef’s next contest, the April Lunchtime 2018 and join your fellow programmers and enjoy the contest problems.
Joining me on the problem setting panel are:
- Problem Setters, Editorialists and Russian Translators: gainullinildar (Ildar Gainullin), altruist_ (Denis Anischenko)
- Problem Tester: kingofnumbers (Hasan Jaddouh)
- Statement Verifier: xellos0 (Jakub Safin)
- Mandarin Translator: huzecong (Hu Zecong)
- Vietnamese Translator: VNOI Team
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: 28th April 2018 (1930 hrs) to 28th April 2018 (2230 hrs). (Indian Standard Time — +5:30 GMT) — Check your timezone.
Contest link: https://www.codechef.com/LTIME59
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 performers in Global and Indian category will get CodeChef laddus, 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 [email protected])
Good Luck!
Hope to see you participating!!
Happy Programming!!
3 Likes
Editorial - Expected Time ??
For me, understanding Triple Tree Decomposition proved really difficult. IDK, the meaning just didnt strike me- to that extent, that I dont know WHY I got 80 points. I could just vaguely get that setter wants us to check if each node has 3*k edges to divide into sets…? Can anyone elaborate?
This is one of the question where explanation of sample Input Output would be a great convenience. If its not really necessary, please dont skip that section.
EDIT- Also please explain what should be the output for cases when N\le 3. I was assuming that its “Yes” because of vacuous truth, but solutions printing “No” for these are accepted.
2 Likes
How to solve TREE3?
My approach
Find any node having number of adjacent nodes divisible by 3. Then check if it’s Triple-tree decomposition using this as root.
My WA Code
Same with me. Testcases are definitely weak for last 2 substasks.
I can confirm that. My solution had a really pathetic bug- if root has only 1 child, it would mistake it as a leaf and return back, doing nothing XD
gcddiv was easy peasy,fft was nice problem,tree3 was confusing and last 2 were unapproachable for me atleast:)
Try this case-
1
7
1 2
1 3
1 4
5 4
5 6
5 7
If you draw this one, you can find that the special thing here is that node 4 is shared. Anyone terminating search at node 4 (on getting condition like number of edges from this node is not a multiple of 3) will suffer a WA here. Didnt check your solution, but I will say try for yourself once for smaller cases. 
1 Like
I was not getting any idea for GCDDIV. How did you guys got the idea to solve it.
@admin is this contest unrated? i see that the ratings are reverted.
2 Likes
if N<=3 , the number of edges would be less than 3 and you can’t partition the edges into groups of 3, so the answer would obviously be ‘NO’
2 Likes
They will be calculated after LoC.
2 Likes
The goal was to make the GCD of the array 1, to do that, just find the GCD of the array and divide it with each element and thats it,but now if the GCD is greater than K you can’t divide it directly so divide with the prime factors of GCD, if its not possible then its “NO”.
1 Like
I have no karma points and I want to ask a question that Question is related to April Lunchtime 2018 The problem code is GCDDIV I found two submissions which got 100 points One is https://www.codechef.com/viewsolution/18380850 and the second is https://www.codechef.com/viewsolution/18375921 The first submission got 100 points event thought It does not deserve 100 points because that fails for the test cases like
1
3 6
101 10201 1030301
For this the solution 18380850 gives its answer as “YES” but the right answer is “NO” solution 18375921 gives correct answer as “NO” for the above test case
Now I want this to be looked upon by the codechef
1 Like
Wrong judgement for GCDDIV
For Example test case:
1
3 10
18 36 72
Returns ‘YES’ for some submissions and ‘NO’ for other but both are marked as correct by the judge.
From my point of view, ‘YES’ will be correct answer as gcd of above number will be 18 which can be represented as 2*9 (both 9 and 2 being less than 10).
Link to both solution are:
my solution: https://www.codechef.com/viewsolution/18376253
other solution: https://www.codechef.com/viewsolution/18386278
2 Likes
I used topological sort approach. I modified this algorithm( https://www.geeksforgeeks.org/topological-sorting-indegree-based-solution/ ) such that all the sources are those nodes which have degrees in multiple of 3. Afterward, I used the above algorithm to propagate further.
My AC Java solution https://www.codechef.com/viewsolution/18379506
3rd problem was quite confusing, so i started doing it on paper. Since it was written that we’re required to print (N-1)/3 lines of output for each testcase, and later i found out why is it so.
So, for 1st subtask, i.e. N<=10 answer is YES for N=4,7,10 and that is also in some cases. I figured that out and wrote code for these special cases to get Partial Score. I know this is not how we should deal with the questions, but just for the sake of my curiosity, i am asking this here.
However, I found out that for 1st subtask the input value of N in TestFile is just 10.
If anyone of you have some time, plz give my solution a glance, i don’t know why i got WA.
My WA
Editorials for the contest?