The contest was better than the previous ones and it had various problems which required very keen observation and logical thinking, managing the time limit and memory limit played the major roles ! I had fun solving them.
My feedback/ views on March Challenge 2015 :
The easiest of this monthâs long challenge, solved it at first attempt. Just went through the question and 5-7 minutes thinking and started coding.
Signwave :
What are those humongous graphs !!! Scared and left it for some later time. After some long thinking I resorted to the old class 11 trigonometry book and found it to be quite a simple problem. Got busy coding and solved it on 15th March, full points in first attempt.
Read it on the first day, seemed to be a problem belonging to easy-medium difficulty, could not solved it. The problem technique seemed somewhat familiar ( now after seeing the editorial I see it is somewhat related to PRLADDU. Didnât try much as internal/mid semester exam was going on from 04-13 ( bad excuse, others did it, Iâm ashamed of my self ).
Partially-solved, again seemed easy-medium problem but unfortunately I was unable to pass last three sub-subtask of the last subtask ( task 12, 13, 14 ).
At first this problem seemed quite easy, they have already provided the two generator functions with code ( this made me happy, less work in typing and just copy-paste the given functions ). The given generator with some modification and tweaking for faster execution, my solution was accepted with full points.
Matrix :
Started reading and had no idea what to do. finished reading and still no idea what to do !!! Went to the explanation section and saw are those pictures, the problem became more difficult to comprehend. Left it and going through the editorial now.
This problem seemed query based and I thought of implementing segment tree, but again was able to solve it only partially.
Well I am only a beginner/ advance-beginner and this problem was clearly out of my league.
Seemed quite straight forward and I submitted a brute force approach which gave TLE. Disappointed, I googled around for a few hours for matrix exponentiation and FFT but still TLE, so I left the problem.
I did not try this, just went through it and tried to grasp the approach/logic required to solve it.
What I like about March15 :
A few of the question were based on observations,tricks and mathematics. Ohh I loved the problem âsignwaveâ, so easy but seemed quite hard, requires only +2 level trigonometry ). âCounting on a treeâ has a very nice solution ( came to know quite a few things after reading the editorial ). âSereja and random arrayâ problem was also very nice based on tricks and maths. âRandom number generatorâ involves some nice mathematical theories into a single problem ( great work by the problem author ).
What I dislike about March15 :
Most of the question were based on tricks,mathematics and keen observations. âMatrixâ was difficult to grasp, âRandom number generatorâ involves a lot of advanced mathematical manipulation ( Generating functions, FFT, number theoretic transform, polynomial mod, polynomial division, thatâs 5 medium/advanced topics into a single problem ).
I agree with @dpraveen , March15 was comparatively tougher than the last few long challenges. Except CNOTE ( and probably SIGNWAVE ) the average difficulty level of the problems were higher compared to other long contests. In the past few long challenges, the difficulty level increased gradually from cakewalk (very easy), easy, easy-medium, medium then medium-difficult, advanced, hard. For three/four problems, some tricks were required. But this month almost all the problems ( except CNOTE ) required some level of observations and tweaks. The difficulty level jumped from cakewalk (CNOTE) to medium ( SIGNWAVE is based on observation, QCHEF ) and then jumped directly to hard category( SEAPROAR, TREECNT2, MATRIX, RNG, EMBED ).
The The best thing about March 15 long challenge is probably the editorials. It has been a while since we had such elaborate, well written, designed with examples editorials for Long contests. Awesome work by the editorialist @kevinsogo .
EDIT 1 : I agree with @lebron, upper bound of difficulty should not be decreased but intermediate difficulty level was quite high in March15 ( most of us are not familiar with ACM ICPC or any other training as mentioned by @lebron ).
The contest was good. I just loved solving the questions MTRWY and STRSUB and though I could not solve QCHEF even after endless attempts, I learnt a lot on the way!
However, I have a suggestion: there should be less of Mathematics & Number theory and more of Programming. SEAPROAR, SIGNWAVE and RNG all were based on Mathematics, though SIGNWAVE was one very innovative problem. Instead, I would like to see more problems on a variety of topics like Strings, Computational Geometry, DP, Data Structures like BIT, Segment Tree etc.
Tests for TREECNT2 were weak.
questions were good and more tough problem should be added in coming contests
I didnât get to try the other questions because I got stuck at Signwave. I found only a 30 points solution based on observations about how the sin function behaved.
I donât agree that upper bound of difficulty should be decreased. Problemset this time wasnât hard, for people used to ACM ICPC trainings it takes no more than an hour to get lineups of solutions (and then it turns out just into finding time for coding), and giving easier problemset will switch all leaderboad competing just to challenge problem. This idea is good only if you are sure that you have a good challenge problem This time it seems to be good, but often they are really awful - like when question was about factorization:) When that problem isnât very good, and all top50 solved other 9 problems, then board isnât informative.
And about problems from this contest - it is strange idea to give problems like SEAPROAR, which requires only 10 minutes of using Google to solve it) about last 2 tasks - TREECNT2 is pretty standard ACM task; and RNG is also generally well-known, it also takes not a long time to google details of solution (even if writing the solution itself isnât that fast&easy), this way of creating problem (take standard task and increase constants) does not look good for long contests where one can simply google a solution for original standard task (and ways to make it run fast).
Difficulty level of challenge can vary like this monthâs challenge and previous monthâs challenge. Both has its own benefit for different kinds of contestants.
Meanwhile my discussion on three easy problems in march challenge: https://shadekcse.wordpress.com/2015/03/16/codechef-march15-challenge/
It was probably the best long challenge in 2-3 months.
The questions were great. I especially liked MTRWY and STRSUB. Didnât like SEAPROAR since the solution was just a Google search away.
Also, the challenge problem should be easy to attempt, but hard to optimize. This question was hard (for me, at least) to even attempt.
devu nd class and sereja and ramdom array can be run just only by luck this type of question which can be run by luck must not be there ,
The March Challenge was undoubtedly one of the best Long Challenges I have participated in.
The problems covered a vast spectrum of algorithms from various topics and was very well balanced.
Problem One â Chef and Notebooks - A typical Ad-Hoc Cakewalk problem of the March Challenge. As expected , Most users got 100 points in this.
Problem Two â SignWave -A trigonometry problem that involved making observations for various cases and designing the code according to the observations made. I did not personally like this problem as it was too math-oriented.
Problem Three â Devu and his Class - A well formulated problem with a greedy approach that wasnât very intuitive but was easily derivable. The âtypeâ factor was a nice addition to the problem and made it interesting. Still , difficulty was not very hard so many users got AC for 100 points. Only downfall of this problem was its striking similarity to the February Lunchtime Problem âThe Warehouseâ . Both involved counting âinversionsâ in an array . I understand that there were better approaches to this problem but a O(N log N) inversion count algorithm was also acceptable .
Problem Four â Count Substrings - Undoubtedly one of the best problems in the March Challenge
What surprised me was the large number of 100 point ACs for this relatively difficult problem .
The solution involved some amount of preprocessing and Binary Search to pass for 100 points.
I spent nearly 4 days on this problem before I finally got it accepted for 100 points.
The problem was really well formulated and had a simple yet tough to implement algorithm.
Problem Five â> Sereja and Random Array â I thought this was a âWikiPediaâ problem . Anyone who knew about LCG and the number of distinct sequences could write up a clever brute force solution with some optimizations and get it passed easily. I wasnât such a huge fan of this question.
Problem Six â> Matrix â Another Brilliant Problem in the March Challenge. Solution was very clever and involved offline processing accompanied by fast union-find algorithm.
The only Downfall â Similarity to the problem Anansi Cobwebs on the TIMUS Server. I had solved this problem a week before the March Challenge and the similarity in algorithm was striking. The addition of âLargestâ Connected Components wasnât a huge issue either.
Problem Seven â> Chef and Problemsâ A really nice problem involving Moâs Algorithm . The simplicity of the problem statement attracted attention and the well thought time constraints made it really difficult to get a 100 in the problem . It was also one of the better questions of the Challenge .
Problem Eight â Counting On A Tree â Interesting Problem having a simple 27 point Brute force solution . 100 points involved a lot of Math and Mobius Function which I didnât know much about.
I did not go through the Last Two Problems of the Challenge and finished on 647 points.
I would like to suggest that the problems should not involve so much of Math as in the SignWave problem.Also, problems like Sereja and Random Array arenât appropriate for Long Challenges as they donât require any coding ability or knowledge of algorithms. The code for the generators were provided and some info about LCGs were sufficient to get 100 points.
Overall, The contest standard was very high and the questions were also of high quality . It was a fun 10 days for me!
The march challenge reminded of ICPC amritapuri round. All the questions were hard. It is a good thing for advanced programmers or the guys supposed to participate in World Finals, but for regular newbies and intermediate programmers, it was frustrating not getting anything done. Please make the long challenge as learning friendly as possible. Give new twisted algorithmic problems instead of hard math problems. Keep these questions for cook offs where speed matters, not learning new things.
I think the difficulty of the problems should be increased a little. The set of 10 problems should be such that they cover a range of different algorithms and data-structures. I see that the first few problems ( 4-5 problems) of Codechef Long are solely implementation/math/greedy.
Also, problems should not be very heavy on implementation, as sometimes is the case. Rather, problem should test the analytical skills and knowledge of algorithms of the contestant, but should not be hard to implement after coming up with a solution.
Another point i would like to make is that subtasks should be removed from the easier problems (easy to easy-medium level problems), since the contestant gains nothing on solving these subtasks. Rather, some users get distracted from the full 100pt solution, and just code to get the âeasyâ points from the smaller subtask and give up on the question, while they could have easily solved the full problem, had they given some more thought to it. This is the sole purpose of Long challenge, improving by pushing yourself beyond your current limits.
Overall, I found March Long Challenge to be good one when compared to previous few long challenges
I like Sine wave questionâŚBecause It has real fun for beginnerâŚ
first I made bruteforce solution try to make all possible solution and just merge all solution and find frequency of all solution and which frequency asked I have answered by simple iterative searchâŚbut pass only 1 subtaskâŚ
after doing some graph ploting on paper i go some idea than I generalize my solution with help of some trivial inputâŚ
after that I got know what exactly is going on here actually solution merging to each no need to do all previous stuffâŚthen I went little deep and then I found some mathematical Relation which very easyâŚfirst time I had done question which looks to me very tough question in live contestâŚFeeling great after getting 100ptsâŚ
Make your myFind() function inline and submit.
If it doesnât work, make the function iterative.
Try it once.
thanx! rsahaâŚ
My code got 100 points after making myFind() function inline
it wasnât waste of time. You have to find that pattern and formula. It was fun.
This has been fixed now. We were not sorting subtask submissions correctly. Execution time of submission was not considered while sorting.