About June Long Challenge - Math-Contest

raydioactive_9 · June 17, 2019, 1:40pm

Solution as in editorial or code ?

anon55659401 · June 17, 2019, 1:43pm

No code. Just the approaches. Thats enough though.

nuttela · June 17, 2019, 1:45pm

Yes. As a matter of fact, admins should check out cplusplus forums. People literally have such wonderful group discussions there. wtf !

himanshuraj18 · June 17, 2019, 2:00pm

Yeah. I agree with you. 6 questions in Div 2 are purely based on pattern observation. Where LENTMO seemed tough initially but then doing subtask 2 first helped me understand how to go about it and got to know that even this question is pure maths and pattern observation based.
Also, COOLCHEF was all about using Dictionary and its proper implementation.

aman_robotics · June 17, 2019, 2:03pm

Can you provide the link for INTRPATH ?

anon55659401 · June 17, 2019, 2:08pm

Not here. Can you give me your cf handle or fb id? I’ll message you there

anon55659401 · June 17, 2019, 2:09pm

Nopes. Coolchef’s intended solution is not using dictionary. Many brute force-python solutions also got AC cuz of weak cases and a very big Time Limit.

aman_robotics · June 17, 2019, 2:17pm

The contest is over. What is the problem posting it here

himanshuraj18 · June 17, 2019, 2:21pm

What I did was storing values of only repeated element on every index. For e.g. l=[1,1,1,3,2,2] my list of dictionary was [{1:1},{1:2},{1:3},{1:3},{1:3,2:1},{1:3,2:2}]. Not including 3 as it’s frequency was 1 (reason- while calculating permutations, we only need count of repeating elements). Even I tried the brute force firstly but only subtask 1 got correct, others were getting TLE. And the time given for Python submissions is 10 seconds/file (I think) which is double of what is usually given for Python (5 seconds/file). C/C++ is given 5 seconds/file.

himanshuraj18 · June 17, 2019, 2:24pm

He is the author of INTRPATH. Give him the link. He can help out to stop these things. Cheating is clearly not acceptable.

anon55659401 · June 17, 2019, 2:27pm

Well, I realized that I don’t have the link as I did not save it, it is from c-plus-plus.com .
I’ll post it here when I find it.

aman_robotics · June 17, 2019, 2:33pm

Yeah please do !!!

anujsingh14 · June 17, 2019, 2:38pm

http://www.cplusplus.com/forum/beginner/255391/

I think this is the thread as mentioned by @anon55659401

samarthtandon · June 17, 2019, 4:57pm

LCA and also about the proper concepts of tree…

l_returns · June 17, 2019, 5:26pm

I think you Google long challenge instead of solving it

l_returns · June 17, 2019, 5:27pm

Your solution for FGTREE ?

anon13835146 · June 17, 2019, 5:52pm

I did not submit it but have an idea. For n less than 20 we can find the root and then devide the array into two parts and continue doing it until leaf is reached ( a recursive way).
For n less than 100 I think we can find the leaf nodes and then join them to find their parent and then join them until root is found out .

l_returns · June 17, 2019, 6:04pm

Oops is it that simple !!
I regret not thinking much

samarthtandon · June 17, 2019, 6:23pm

what ??..but why my solution gives TLE…it is also O(nq) its just annoying me

anujsingh14 · June 17, 2019, 6:34pm

Just O(nq) will not work, you have to do some optimizations too.