shettynamit's blog

Bitwise 2012 — Solutions Uploaded
By shettynamit, 13 years ago, In English

EDIT: Solutions are available @ http://www.bitwise.iitkgp.ernet.in/solutions

Hi all, Bitwise is an algorithm intensive programming contest organised by the Department of Computer Science and Engineering of IIT Kharagpur. Prizes worth $4000 (INR 2 Lakhs) are on the cards. Allowed Programming Languages are C/C++/Java.

Bitwise is scheduled to be on 12th February 2012. The Contest will start at 1030 hrs and end at 2230 hrs (UTC)

Register here: http://www.bitwise.iitkgp.ernet.in/register Main Website: http://www.bitwise.iitkgp.ernet.in/home

The break up of the prizes are as follows:-

Global Top 3:- 1st Place: 60,000 INR (~**1200** USD) 2nd Place: 35,000 INR (~ 700 USD) 3rd Place: 25,000 INR (~ 500 USD)

Indian Top 3:- 1st Place: 10,000 INR 2nd Place: 6,000 INR 3rd Place: 4,000 INR

There are other prizes for the global Top 20 as well — http://www.bitwise.iitkgp.ernet.in/home#prizes. So don't forget to participate!

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

Comments Comments (37)
| Write comment?
»
13 years ago, # |
  Vote: I like it +23 Vote: I do not like it

For the God sake, it is 2012. Still no Java?

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

    Our team is working to support Java as well; Will definitely let you know in a couple of days!

    → Reply
  • »
    »
    13 years ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    Java solutions will be accepted!

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

      Thank you for this Also I hope this year all limits on input data would be available from the start

      → Reply
»
13 years ago, # |
  Vote: I like it -23 Vote: I do not like it

Even if they include java, there is very bleak(small) chance for any java coder wining, because the scores are evaluated on the basis of correctness, TIME and SPACE efficiency.

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

    Actually there is standard tl and ml, at least that was the case for some last years

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

    As Egor correctly pointed out, there is a standard time and memory limit. Your solution just has to be within those limits — then you would be given full credit!

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

      Now it is clear. When I read the FAQ's on website I misunderstood the context of time and memory limit.

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

During Bitwise 2011, there was a problem which allowed precalculation of answers to all possible test cases on a local computer and then sending a simple program that just prints the right answers. Doing so is pretty legal in a number of other contests. However, in the middle of the contest, a rule appeared which informally rejected such submissions. From a participant's point of view, it was a bit inconvenient to see the rules change in the middle of the contest.

If you plan to include a problem which allows precalculation in Bitwise 2012, please either accept such solutions entirely or make a clear and formal rule against them and publish it in the competition rules and/or the problem statement.

To disallow such solutions in a formal way, there is often a limit on the source code size (e. g., 50 000 bytes on CodeChef or Sphere Online Judge, 256 KB on some ACM ICPC contests).

→ Reply
  • »
    »
    13 years ago, # ^ |
      Vote: I like it +8 Vote: I do not like it

    @Gassa: Yes, I am aware of the fact (on the receiving end as a participant). Rest assured, it won't happen this time. Thanks for the suggestion about the source limit. We will specify beforehand in the problem statement/Rules about any such limits.

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

Do I understand correctly that C++ programs will be compiled without -O2 flag?

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

Can you clarify about prizes, like if someone is in both list, global and india, then will they be counted in both list ?

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

    Well, no. But they will get the better of the two. So if an Indian comes in Global Top 3, then he gets the global prize.

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

      so, the 11th place in India will slide-up, right ?

      like if "x" comes in global top-3. then also the indian list will have 10 names excluding his name.

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

I cannot submit as of now, rights?

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

Java compiler considers warnings as errors, can you fix this?

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

    We are working on this...it requires some changes in our system because of -Xlint warnings. Please try removing the warnings for now.

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

Nice contest! :)

Can somebody explain how to solve P2?

→ Reply
  • »
    »
    13 years ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

    We will release the solutions soon :)

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

    I solved it using min cost max flow. At first you make add edge of capacity 1 and weight 0 for each pair of prefernces as well from source to each student. Also we will add edge from each faculty to sink with capacity 1 and weight 1. Then we will find flow of size 1 n times and if all edges from faculty to sink are filled add one more edge with capacity 1 and weight (number of allready added edges from this faculty to sink) + 1

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

      This can be solved with just max flow, without costs. We can initially set the capacities of the edges from faculties to sink to 1, then find the max flow, then increase these capacities to 2, then augment the flow while possible, then increase capacities again etc. A similar problem was in Petrozavodsk once, and this was the author's solution.

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

Thanks for a nice contest.

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

How to do Problem 3? I maintained the maximum power of the primes and when a new number is added I check with the current maximum power, if its more than answer is multiplied by prime raised to difference in power. When a number is removed and this was the number with maximum power, the answer is multiplied by the inverse of prime raised to difference in its power and the new maximum. I have used deque as the data structure.

It got WA. However, I am not able to find any test cases on which the code fails. Here is the code.

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

    Ah, i got the mistake. I didn't kept the prime powers which were greater than 10^5.

    Sorry for the trouble.

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

Solutions to Bitwise 2012 are up! You can view them here: http://www.bitwise.iitkgp.ernet.in/solutions

Hope every1 njoyed Bitwise this year!

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

    Since rudradevbasak is in two of the lists, and he will get the better of the two prizes, then why not slide-up the 11th place holder ?

    → Reply
    • »
      »
      »
      13 years ago, # ^ |
      ← Rev. 2   Vote: I like it 0 Vote: I do not like it

      Even though Rudradev is 4th globally, he is the Indian topper. So he has the option of 10,000 INR or a 16GB pendrive (for global 4th). Its not hard to see that the 10K INR is a better option for him. So we had already slided up the global 21st position

      Hope that answers your question.

      → Reply
  • »
    »
    13 years ago, # ^ |
      Vote: I like it +8 Vote: I do not like it

    Omg, we passed problem 1 by solution with Tutte matrix and used all 20 attempts

    → Reply
    • »
      »
      »
      13 years ago, # ^ |
        Vote: I like it +8 Vote: I do not like it

      We used Tutte matrix too. Only 13 attempts though :)

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

Unable to view the solutions?

→ Reply