sentinel45's blog

Technex'14 and FireEye, Inc. present Matheletics
By sentinel45, 11 years ago, In English

Matheletics is a mathematical contest (inspired from PROJECT EULER) where a sound knowledge of mathematics together with computational thinking will be essential to solve problems.

The motivation behind Matheletics is to provide a platform for the inquiring mind to delve into unfamiliar areas and learn new concepts in a fun and recreational context.

Prizes worth ₹ 65000 on stake and Hackerrank goodies and T-shirts for top performers.

It's a 5 hour long individual contest hosted at HackerRank. Sign up for the event on HackerRank For registration, You must be registered on hackerrank.com.

Check event time in your time zone.

Registration on Technex website is necessary to be eligible for prizes.

For regular updates,join the facebook event page

  • Vote: I like it
  • +8
  • Vote: I do not like it

»
11 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Is it a team contest?

→ Reply
»
11 years ago, # |
  Vote: I like it 0 Vote: I do not like it

The contest is seeing a close fight between UWI and Gennady.

More than 1000 registrations so far...still more than 2 hours left for the contest. Join the contest

→ Reply
»
11 years ago, # |
  Vote: I like it +19 Vote: I do not like it

When the final results will be available?

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

    The submissions are being re-judged for large test cases. The result would be declared soon. The official announcement for the winners will be made during valedictory function of Technex to be held during 7-9 March.

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

    Contest Leaderboard after judging large testcases Matheletics Leaderboard

    → Reply
»
11 years ago, # |
← Rev. 3   Vote: I like it 0 Vote: I do not like it

I really liked the problem Save The Land, mainly because I worked very hard to solve it (not in contest, unfortunately). I will describe my solution below.

First imagine a straight (not circular) arrangement of gates. Let be the number of ways where any two adjacent gates are hit by fire-balls. To find a recurrence for it, consider the first three gates (say A, B, C, in that order). The following cases are possible, and their contributions to answer are:

  • A=0, B=0, C arbitrary:
  • A=1, B=0, C arbitrary:
  • A=0, B=1, C=0:
  • A=0, B=1, C=1:
  • A=1, B=1, C=0:
  • A=1, B=1, C=1:

From these we get the recurrence . This helps us design the following matrix equation for finding .


From this, we can get . We can easily obtain by brute-force.
Now we can find using matrix exponentiation method.

Let us now come back to the problem. We have a circular arrangement of gates, and we need to find be the number of ways where any two adjacent gates are hit. Let be this number. To find a recurrence, take any three consecutive gates (say A, B, C). The possible cases and their contributions are:

  • A arbitrary, B=0, C arbitrary:
  • A=0, B=1, C=0:
  • A=0, B=1, C=1:
  • A=1, B=1, C=0:
  • A=1, B=1, C=1:

So the recurrence we get is . Since the RHS does not involve , we need not formulate any matrix for this; we can directly get the terms involving using the old matrix and calculate by simply plugging in these values into the above formula.

Complexity:
Link to my accepted solution.

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

    I have another solution in a Russian thread.

    The answer is 2n  -  Fn  -  Fn  -  2. Indeed, the number of sequences of length n, without successive ones and ending by zero, equals Fn. By induction, F1 = 1, F2 = 2, Fn = Fn - 1 + Fn - 2, since a sequence can end by 0 or 10. A sequence without two successive ones can end by 1, then the first element and the element before the last one are zeros. Therefore the number of such sequences is Fn - 2.

    → Reply
»
11 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Congratulations to tourist ! Amazing, always see him on #1

Math problems are my worst ability.. I could solve nothing from Codeforces Round 232 (Div. 1) which is a totally mathematics round...

→ Reply
»
11 years ago, # |
← Rev. 2   Vote: I like it +3 Vote: I do not like it

It has been 3 months. I (along with 2 others) were the Indian winners and I don't know where Prizes worth ₹ 65000 on stake and Hackerrank goodies and T-shirts for top performers are. No one has received anything. This is a very sad scenario :(

→ Reply