Feedback regarding March long challenge

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

My feedback/ views on March Challenge 2015 :

Chef and Notebooks :

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

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

Devu and his Class :

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 :cry: ).

Count Substrings :

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 ).

Sereja and Random Array :

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.

Chef and Problems :

This problem seemed query based and I thought of implementing segment tree, but again was able to solve it only partially.

Counting on a Tree :

Well I am only a beginner/ advance-beginner and this problem was clearly out of my league.

Random Number Generator :

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.

Embedding :

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 :diamonds::diamonds: , 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 ).

7 Likes

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

1 Like

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 :slight_smile: 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).

5 Likes

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

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!

1 Like

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.

1 Like

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

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.

4 Likes

@fool_for_cs: Can you give me a use case where this is happening ?

This has been fixed now. We were not sorting subtask submissions correctly. Execution time of submission was not considered while sorting.