You are not logged in. Please login at www.codechef.com to post your questions!

×

Help regarding MIKE3 In March challenge 2014

I solved the problem MIKE3 which is giving me a correct answer for all random test cases i give to it but the OJ is giving me a WA for some reasons. here is my solution non documented version or documented version on pastebin

In the solution which is documented enough for a good understanding i have reduced the problem to find the sets of the group(offers) which cant be dealt with together and used an array named graph to store this to find the solution.

Help find the error in this algorithm/code !

asked 18 Mar '14, 15:31

randomizer's gravatar image

4★randomizer
1462311
accept rate: 11%

edited 19 Mar '14, 14:18

admin's gravatar image

0★admin ♦♦
19.7k350498541


Your criteria for selecting the customer with minimum clash is wrong. This the test case answer is 3. test 100 9 1 1 3 2 1 9 3 3 1 9 3 4 1 9 3 5 1 9 3 6 1 9 5 2 3 4 5 6 2 6 7 2 7 9 Your program giving 2.

link

answered 18 Mar '14, 15:53

jangwa's gravatar image

2★jangwa
17229
accept rate: 10%

edited 18 Mar '14, 16:14

1

Can you explain how the answer is 3 ? I believe it is 2.

(18 Mar '14, 16:04) xorfire_3★

sorry : this is 100 9 1 1 3 2 1 9 3 3 1 9 3 4 1 9 3 5 1 9 3 6 1 9 5 2 3 4 5 6 2 6 7 2 7 9

(18 Mar '14, 16:13) jangwa2★

thanks for that test case finally getting close to finally debug it :)

(18 Mar '14, 16:24) randomizer4★

Approach is try all possible combination 2^20. using DP

link

answered 18 Mar '14, 15:33

jangwa's gravatar image

2★jangwa
17229
accept rate: 10%

no i don't want to change the approach , my algorithm looks mathematically sound to me but i want to know what went wrong

(18 Mar '14, 15:36) randomizer4★

What is your criteria to select a customer?

(18 Mar '14, 15:39) jangwa2★
1

Simply trying all possible combination is fine. DP is not necessary.

(18 Mar '14, 15:41) xorfire_3★

Ya you may ignore DP part. just use recursion

(18 Mar '14, 15:44) jangwa2★

@randomizer I dont see any reason why you should downvote this answer. He was just trying to help. @jangwa retaliation is just as bad :D

(18 Mar '14, 16:02) kcahdog3★

point taken @kcahdog

(18 Mar '14, 16:04) randomizer4★

Let people feel that codechef give equal right to every one. @kcahdog

(18 Mar '14, 16:07) jangwa2★
showing 5 of 7 show all

@randomizer I followed an approach similar to yours in making the m * m matrix denoting intersections but after that i used an exponential solution (of order O(m)*m ) to get the answer. here is link to my solution for reference right now. I will tell you what is wrong with your code in some time.

link

answered 18 Mar '14, 15:43

kcahdog's gravatar image

3★kcahdog
10.0k2854129
accept rate: 14%

thanks @kcahdog

(18 Mar '14, 15:49) randomizer4★

Following assumption

//this piece finds the possible groups which can sit starting from the [row] which has lowest number of 1s because it will have least number of collisions

Looks incorrect.

link

answered 18 Mar '14, 15:51

mjbpl's gravatar image

5★mjbpl
41927
accept rate: 6%

can you provide me a test case which proves this ? or some proof why it will not work

(18 Mar '14, 16:00) randomizer4★
3

15 8 <\n> 2 1 15 <\n> 2 1 2 <\n> 2 3 15 <\n> 5 2 3 4 5 6 <\n> 5 2 3 7 8 9 <\n> 2 4 7 <\n> 2 5 8 <\n> 2 6 9 <\n>

(18 Mar '14, 16:15) mjbpl5★

thanks for the test case :)

(18 Mar '14, 16:25) randomizer4★
toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • image?![alt text](/path/img.jpg "title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported
  • mathemetical formulas in Latex between $ symbol

Question tags:

×1,650
×846
×9

question asked: 18 Mar '14, 15:31

question was seen: 1,070 times

last updated: 19 Mar '14, 14:18