Tachyon's blog

Manthan 2011
By Tachyon, 14 years ago, In English
CodeFest'11, the annual online international coding festival of Computer Engineering Society IT-BHU, presents Manthan - the algorithm intensive programming contest. The name Manthan or मंथन has been taken from the Hindi language and means Brainstorming. Google Logo CodeFest Logo

The contest aims to provide a platform for programmers round the globe to showcase their problem-solving and programming skills. Most problems of the event will be real life computing problems where coders will be required to prune existing standard algorithms to find the solution for the domain specific application of the algorithm.

We are proud to have Codeforces as our partner for Manthan 2011. The Contest will be hosted on Codeforces and will follow the rules similar to that of Codeforces Beta Round.

Google Sponsored event with Prizes worth 50,000 INR. Besides, Certificates to top 50 participants. 

You need to follow the registration procedure in order to be eligible for prizes.

Event Details:
  • The main event is scheduled on March 13 at 2200 Hrs IST (UTC+5:30)
  • Rules of contest similar to Codeforces Beta Rounds.
  • The Contest will be of 3 hours consisting of 5-6 problems.
  • Programing languages allowed: C, C++ , Pascal, Java, C#, Python, Ruby, PHP, F# and Haskell.
  • Open to all, students as well as professionals.
  • Declaration of Results on March 16 at 1800 Hrs IST.
Note: Contest duration has been reduced from 4 to 3 hours.

Visit the Manthan event page for further details of the contest.

Registration for the competition will occur automatically on the fact of your registration on the official CodeFest site. If you have been properly registered there, then your Codeforces handle should appear in the list on http://codefest.org.in/codeforces-handles.php, and registration for the contest will take place
automatically.

The contest duration changed to be 3 hours. Good luck!

Announcement of Manthan 2011
  • Vote: I like it
  • +75
  • Vote: I do not like it

Comments Comments (80)
| Write comment?
14 years ago, # |
  Vote: I like it +4 Vote: I do not like it
Excuse me.

How can we read 'Manthan'?
→ Reply
  • 14 years ago, # ^ |
    ← Rev. 2   Vote: I like it +6 Vote: I do not like it
    Well its Man ('Mon'day) + th ('th'ought) + an (S'un'). word in quotes describe pronunciation. Hope it helps :)
    → Reply
14 years ago, # |
  Vote: I like it 0 Vote: I do not like it
I have registered on the codefest website but i did not receive a confirmation e-mail. Thus i can not login and i cannot also use my e-mail account to register what can i do?
→ Reply
14 years ago, # |
  Vote: I like it 0 Vote: I do not like it
Hello. I want to be an official participant. I have registered on the codefest website but when I try to register for the manthan the form is shown to register on the codeforces website, but I am already registered. I can not enter my password because I use google id to enter here. Maybe someone have any suggestions about that?
→ Reply
  • 14 years ago, # ^ |
      Vote: I like it +1 Vote: I do not like it
    This happens because the email id used for registering on codefest website and codeforces website are different. You have two options to become an official participant.

    1)For the registration form that pops up on clicking 'Register for Manthan', provide a new codeforces handle and new password.

    2) Re-register on codefest website using the same email id as in codeforces. Then when you login and click on 'Register for Manthan' no extra form pops up.
    → Reply
    • 14 years ago, # ^ |
        Vote: I like it +1 Vote: I do not like it
      Also it is possible to change e-mail here, then after Manthan change it again.
      → Reply
    • 14 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it
      Thank you. It was really helpful!
      → Reply
14 years ago, # |
  Vote: I like it 0 Vote: I do not like it
It is clear that official results will be published at the 16th of March. But will there be any preliminary system test results right after the contest?
→ Reply
14 years ago, # |
  Vote: I like it 0 Vote: I do not like it
How to : 
register on the official CodeFest site to be official participants.

???
→ Reply
14 years ago, # |
  Vote: I like it +6 Vote: I do not like it
Will this contest be rated in Codeforces?
→ Reply
14 years ago, # |
← Rev. 3   Vote: I like it +5 Vote: I do not like it
"Rules of the contest is similiar to Codeforces Beta Rounds"
What are the differences between the rules?
→ Reply
  • 14 years ago, # ^ |
      Vote: I like it +11 Vote: I do not like it
    The differences are:
    1. There will be 40 participants in each room.
    2. Distribution in rooms will be done randomly
    3. Difference in number of problems
    More detailed rules are here: http://codefest.org.in/event.php?name=manthan#rules
    → Reply
    • 14 years ago, # ^ |
        Vote: I like it +6 Vote: I do not like it
      Does this mean that usual distribution in rooms is not random?
      → Reply
14 years ago, # |
  Vote: I like it +1 Vote: I do not like it
I think the Time of Contest is difficult for the Chinese Competitors. It's on 0:30.am-4:30.am.=,=
Could it be possible to pull the follow-up Contest a little earlier?
→ Reply
14 years ago, # |
  Vote: I like it +19 Vote: I do not like it
We have a new record of registered users!) Cool!
→ Reply
14 years ago, # |
  Vote: I like it +12 Vote: I do not like it
Because of unusual registration process we have some small issue that some users registered twice on the contest. If you see such cases, please, write here I'll fix them. Thank you.
===
По причине нетипичной регистрации есть какие-то баги, которые проявляются так, что некоторые пользователи зарегистрировались на контест более одного раза. Если вы увидите такие случаи, напишите сюда. Спасибо.
→ Reply
  • 14 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    I registered twice in manthan site : amzmohammad  & mathscholar !
    the second one email address is same to my email on codeforces :"mohammad.mahmoodi"
    but any ID is not in the list! 
    whats the problem ?

    → Reply
    • 14 years ago, # ^ |
        Vote: I like it +1 Vote: I do not like it
      Possibly, you didn't click on 'Register for Manthan' on the right pane of the event page http://codefest.org.in/event.php?name=manthan . Check out the "how to participate?" section of the event page.
      → Reply
14 years ago, # |
  Vote: I like it +3 Vote: I do not like it
Good luck!
→ Reply
14 years ago, # |
  Vote: I like it +4 Vote: I do not like it
I loved the tasks. They were extremely nice :D
→ Reply
14 years ago, # |
← Rev. 2   Vote: I like it +28 Vote: I do not like it
I so hate when problem A has tricky cases.
Hope sooner or later problem writers will realize that this is not cool.

Some people earned 3000 points by hacking problem A. It is more than average person could achieve by solving C and D together. I don't know what it proves.
→ Reply
  • 14 years ago, # ^ |
      Vote: I like it +8 Vote: I do not like it
    What was the tricky case ?
    → Reply
    • 14 years ago, # ^ |
        Vote: I like it +6 Vote: I do not like it
      LLLLLR for instance.
      This is one on which I failed, and then I saw several people doing the same mistake.
      → Reply
      • 14 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it
        What's the answer for this case ..  My answer is 6 5 4 3 2 1 2 is this right?
        And I still wrong answer on test 7 ...

        → Reply
        • 14 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          My bad. I meant RRRRRL

          You can see on which test your solution failed. Click on the submission ID on the status page.

          → Reply
          • 14 years ago, # ^ |
              Vote: I like it 0 Vote: I do not like it
            but the #7 data is so long that I can't see it completely....so I still don't know where I am wrong ....
            → Reply
  • 14 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    Devasting Result on Problem A , Almost everyone failed systest in my room .
    → Reply
  • 14 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    yeah. IMHO hacks are very expensive. I think that most people that miss tricky cases are from div2 and because at codeforces div1 and div2 users can be in the same rooms, there is good chance for someone to make big scores on hacking.
    → Reply
14 years ago, # |
  Vote: I like it 0 Vote: I do not like it
I solved 4th using LIS ...Is it correct ?
→ Reply
14 years ago, # |
  Vote: I like it +4 Vote: I do not like it
Manthan 2011 is now over.

Please do provide us your feedback!
→ Reply
  • 14 years ago, # ^ |
      Vote: I like it +8 Vote: I do not like it
    Besides the fact that problem A should have had better pretests, I would also swap problem C and D.
    Problems themselves are very good overall. I pretty much enjoyed solving all of them.
    → Reply
14 years ago, # |
  Vote: I like it +1 Vote: I do not like it
maybe points for hacking should be decreased?
→ Reply
14 years ago, # |
  Vote: I like it 0 Vote: I do not like it
Test #7 , It caused many Systest Fail on A.
→ Reply
14 years ago, # |
  Vote: I like it -6 Vote: I do not like it
Argh, I missed top 50 by 7 positions :(
→ Reply
14 years ago, # |
  Vote: I like it +3 Vote: I do not like it
Will the rating change or will it remain the same?
→ Reply
  • 14 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    This round is rated.
    http://mirror.codeforces.com/blog/entry/1473#comments

    but i'm not sure when the ratings will be updated.
    → Reply
14 years ago, # |
  Vote: I like it 0 Vote: I do not like it
What was the Test #7 in A. (Full Test)
→ Reply
14 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

→ Reply
14 years ago, # |
  Vote: I like it 0 Vote: I do not like it
Why the hardest problem was given 1500 point value? I do trust organizers and thought that all these people that passed pretests for fourth problem had overlooked something and surely had wrong solutions and I started to work on third problem...
→ Reply
14 years ago, # |
  Vote: I like it -16 Vote: I do not like it

2
1 2
1 2
Output
0
Answer
1
Checker Log
wrong answer 1st numbers differ - expected: '1', found: '0'

I'm not agree with this.

A ray doesn't intersect itself.
And from the sentence:

"Sir, there are some groups of rays such that all rays in that group intersect every other ray in that group. 

We can conclude that there is at least one group with at least two intersecting rays,since "every other" is at least one ray.

I want to be rejudged:)


→ Reply
  • 14 years ago, # ^ |
      Vote: I like it +7 Vote: I do not like it
    Every OTHER.
    → Reply
  • 14 years ago, # ^ |
      Vote: I like it +12 Vote: I do not like it
    every 0 others.
    Any statement about elements of empty set is right
    → Reply
  • 14 years ago, # ^ |
    ← Rev. 2   Vote: I like it +1 Vote: I do not like it
    There is no reason that "every other" contains at least one ray.
    A ray doesn't intersect itself , but we are looking for groups where each ray intersects "every other" ray :D
    → Reply
    • 14 years ago, # ^ |
        Vote: I like it +1 Vote: I do not like it
      It did intersect every other ray , which in this case is no ray.
      → Reply
    • 14 years ago, # ^ |
      ← Rev. 3   Vote: I like it -7 Vote: I do not like it

      It seems nobody understands me:)

      We have:

      Statement says:

      there are some groups (at least one SUCH group exists,do you agree?some>0) of rays such that all rays in that group intersect every other (THEY DO INTERSECT).

      If we have only groups with 1 ray there are no intersections.

      → Reply
      • 14 years ago, # ^ |
          Vote: I like it +1 Vote: I do not like it
        No intersections = intersecting the 0 other rays

        → Reply
      • 14 years ago, # ^ |
          Vote: I like it +3 Vote: I do not like it
        So what?
        Empty set contains only even numbers, but it dosen't contains any even number
        → Reply
      • 14 years ago, # ^ |
          Vote: I like it +1 Vote: I do not like it

        For every pair of rays from that group, thay are intersecting.

        If there are no pairs, this statement is correct in any case.

        If I have no friends than statement "all my friends are girls" is correct:)

        → Reply
      • 14 years ago, # ^ |
          Vote: I like it +7 Vote: I do not like it
        So, there's a group with one ray. If we take this ray, then "every other" in this case is none, and it indeed does intersect every other ray in the set since there is no ray that is not intersected by it.
        → Reply
  • 14 years ago, # ^ |
    ← Rev. 2   Vote: I like it +3 Vote: I do not like it
    Mathematically speaking, a set with only one ray satisfies the condition “all rays in the set intersect every other ray in the set” because there is no “other ray in the set.”  This kind of logic is called vacuous truth.

    This is different from the ordinary way we use words.  In the ordinary sense, if we say “all the children playing in the park are boys,” it usually implicitly means that there is at least one child playing in the park (and he is a boy).  But in mathematics, we use the terms in a slightly different way.

    One may argue that it is unrealistic to assume that the student used the terms in the mathematical sense.  But then what would be the correct answer?  If you do not think that a set of one ray satisfies the condition, I cannot see why you think that the set of zero rays satisfies the condition, either.
    → Reply
    • 14 years ago, # ^ |
      ← Rev. 2   Vote: I like it +1 Vote: I do not like it

      Thanks.Your answer is the best for me.Vacous truth is not a new thing for me.And the problem here for me was really that the statement was written in ordinary language and i didn't think that the student could have used some math approaches to express his thoughts. 

      Really,the set of 0 rays also makes us believe that the student told a lie in the case of ordinary reasoning.There are no intersections in this case too.You 've almost convinced me that it was my fault too that i made this bug:)

      → Reply
      • 14 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it
        In my honest opinion, this is a glitch in the problem statement, and a clarification by the organizers during the competition would have been desired.  I would have probably asked for a clarification if I were familiar with the system.  Just my two cents.
        → Reply
14 years ago, # |
  Vote: I like it +11 Vote: I do not like it
Solutions are here http://codefest.org.in/event.php?name=manthan
→ Reply
14 years ago, # |
  Vote: I like it +4 Vote: I do not like it
Now after this contest is over I'm quite sure that problem A is not supposed to be very easy anymore.... There must be some tricky cases I'll simply overlook.

Anyway, great contest with great problems. Thanks!
→ Reply
14 years ago, # |
  Vote: I like it 0 Vote: I do not like it
what's the hole data in test 7 in problem A ?


→ Reply
14 years ago, # |
  Vote: I like it 0 Vote: I do not like it
In problem B.
I don't understand this statement "where bi is the number of elements aj in A to the left of the element at = i such that aj ≥ (i + k)."
So, I don't know how to make B from A.

I also don't know how to lock my solution code and hack another solution code when in contest.

Can anyone explain it?
Thanks.
→ Reply
  • 14 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    For example:
    A = {3,1,5,2,4) and k = 1, this is how to calculate B:
    B1 = 1 means there's 1 element >=1+k (3) standing before 1 in A
    B2 = 2 means there're 2 elements >=2+k (3,5) standing before 2 in A
    so on...

    → Reply
    • 14 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it
      Thank you very much..
      I understand now.

      You(or others who knows it) know how to lock solution code?
      And how to hack another participant's solution code?

      Thanks in advance
      → Reply
      • 14 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it
        When you enter a contest, you can see:
        Problems - Submit - ... - Room -....
        Choose Problems, you will see locks on problems you submit and pass pretests. Click on the locks. Choose Room and click on other participants' submission to hack.
        → Reply
14 years ago, # |
  Vote: I like it 0 Vote: I do not like it
A question about problem C. I think the solution only works because of this condition:

"Also, it is given that 2· te ≥ ti  + td."

If this condition is not true, does anyone have an efficient way of solving this problem?

Many thanks in advance!
→ Reply
  • 14 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    I think without this statement every intermediate string could be a graph node and transformations could be routes in the graph with its weights. There are a number of solutions for this task, can be found in the
    "References" section here http://en.wikipedia.org/wiki/Sequence_alignment
    → Reply
    • 14 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it
      May I know what would be the complexity of your algorithm?
      → Reply
14 years ago, # |
  Vote: I like it 0 Vote: I do not like it
Too much of rating benefit because of this round.
In this almost everyone got good ratings, mainly because there were lots of "Unrated" participants.
Is this OK?
→ Reply
  • 14 years ago, # ^ |
      Vote: I like it +4 Vote: I do not like it
    “Unrated” means that this was the first rated competition on CodeForces for them (and I was one of them).  The fact that there were many “unrated” participants in this competition means that there were many new participants to CodeForces.  While I can see why it is a good thing, I cannot see why it might be a bad thing.
    → Reply
    • 14 years ago, # ^ |
      ← Rev. 3   Vote: I like it 0 Vote: I do not like it
      From " Is this OK? " , I meant to ask whether the ratings inflation provide good indication of how we performed ? .
      Because I saw many people not even solving a single problem got increase in rating.
      (I also think that my rating would not have gone that high by getting just getting 1200 pts if there would have been less "unrated" people.)
      I consider this is mainly because there were lots of "Unrated" contestants . That was only my concern that whether the rating actually reflect the performance , because u see "not even solving a single question and getting rating increase" is in my opinion weird.

      As far as new contestants are concerned , they are always Welcome . :)
      → Reply
      • 14 years ago, # ^ |
        ← Rev. 2   Vote: I like it +1 Vote: I do not like it
        I doubt that that is a real problem.  I agree that in this competition it was likely to be easier to gain rating than in usual Codeforces Beta Rounds because of the large number of first-timers.  However, even if some experienced participants gained rating by an undeserved amount because of that, it is difficult to keep that rating in Codeforces Beta Rounds in the future.

        In theory, if someone were desperate to keep the rating without actually improving his/her skills, he/she could use a silly “strategy”: participate only in the events where many first-timers are expected.  But it is unlikely that many people would try to use this “strategy,” and I do not think that we have to worry about such a possibility because it will not harm the rating of other participants anyway.
        → Reply
14 years ago, # |
  Vote: I like it 0 Vote: I do not like it
I cannot find "screw_it" and "imrankhan" ... in the standings, but i see they are winners( from India) , where are they ??
→ Reply
  • 14 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    Those are the codefest usernames.
    I believe that screw_it is pt1989.
    → Reply
    • 14 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it
      okays...  and is imrankhan ---> imrankane ?
      → Reply
      • 14 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it
        Looks like it.
        You can compare the ranks from codefest results to that of codeforces standings.
        → Reply