Overclock.net › Forums › Software, Programming and Coding › Coding and Programming › [Java] A really hard algorithm implementation
New Posts  All Forums:Forum Nav:

[Java] A really hard algorithm implementation

post #1 of 11
Thread Starter 
So I wanted to solve this problem:

After a tennis tournament each player was asked how many matches he had.
An athlete can't play more than one match with another athlete.
As an input the only thing you have is the number of athletes and the matches each athlete had. As an output you will have 1 if the tournament was possible to be done according to the athletes answers or 0 if not. For example:

Input: 4 3 3 3 3 Output: 1
Input: 6 2 4 5 5 2 1 Output: 0
Input: 2 1 1 Output: 1
Input: 1 0 Output: 0
Input: 3 1 1 1 Output: 0
Input: 3 2 2 0 Output: 0
Input: 3 4 3 2 Output: 0

the first number of the input is not part of the athletes answer it's the number of athletes that took part in the tournament for example in 6 2 4 5 5 2 1 we have 6 athletes that took part and their answers were 2 4 5 5 2 1

This is what I have wrote so far and it is not working completely:
Code:
import java.util.Scanner;
import java.util.Arrays;

public class Tennis {

    public static void main(String[] args) {
        Scanner input = new Scanner(System.in);

        String N;
        int count;
        int sum = 0;
        int max;
        int activeAthletes;
        int flag;

        System.out.printf("Give: ");
        N = input.nextLine();

        String[] arr = N.split(" ");
        int[] array = new int[arr.length];

        for (count = 0; count < arr.length; count++) {
            array[count] = Integer.parseInt(arr[count]);
            //System.out.print(arr[count] + " ");
        }

        for (count = 1; count < arr.length; count++) {
            sum += array[count];
        }
        //System.out.println("\n" + sum);

        activeAthletes = array[0];
        
        for (count = 1; count < array.length; count++) {
            if (array[count] == 0) {
                activeAthletes--;
            }
        }

        max = array[1];
        for (count = 2; count < array.length; count++) {
            if (array[count] > max) {
                max = array[count];
            }
        }
       // System.out.println(max);
        
        if ((sum % 2 == 0) && (max < activeAthletes)) {            
            flag = 1;
        } else{
            flag = 0;
        }
            
        System.out.println(flag);
    }
}
post #2 of 11
Okay, so aren't there 3 cases, there must be an even number of matches, no one is allowed to have more than n-1 matches where n is the total number of players and no one is allowed to have greater than half the number of total matches right?

Did I miss a case?

Edit:
I'm in class right now, and quickly looking your code, I don't think you accounted that each athelete can only play n-1 matches (they can't play themself)

Edit2:
Nvm, I just saw your max < athletes in the true case. What cases is it failing on?

Edit3: according to your answers, the case of 1 0, where there is only one athlete, who answers 0, that can't be a tournament
Edited by AchuSaysBlessYou - 4/25/12 at 2:16pm
post #3 of 11
Correct me if I'm wrong, but my first instinct is that this is a pretty simple graph/combinatoric problem. Do the numbers violate the handshaking lemma? Given N players, does any player state that they played more than N-1 matches? Does the total number of matches exceed N choose 2? If all three answers are no, the tournament is possible.
TheHydra
(13 items)
 
  
CPUMotherboardGraphicsRAM
i7 860 @ 3.6 EVGA P55 FTW Sapphire TOXIC 2GB 6950 CORSAIR XMS3 4 x 2GB CMX4GX3M2A1600C7 
Hard DriveOSKeyboardPower
C300 64Gb + 2x F3 HD103SJ 1TB in RAID 0 Win7 x64 Razer BlackWidow Corsair 750HX 
CaseMouseMouse Pad
Lian Li A05NB with 140mm top fan. Razer DeathAdder Razer Kabuto 
  hide details  
Reply
TheHydra
(13 items)
 
  
CPUMotherboardGraphicsRAM
i7 860 @ 3.6 EVGA P55 FTW Sapphire TOXIC 2GB 6950 CORSAIR XMS3 4 x 2GB CMX4GX3M2A1600C7 
Hard DriveOSKeyboardPower
C300 64Gb + 2x F3 HD103SJ 1TB in RAID 0 Win7 x64 Razer BlackWidow Corsair 750HX 
CaseMouseMouse Pad
Lian Li A05NB with 140mm top fan. Razer DeathAdder Razer Kabuto 
  hide details  
Reply
post #4 of 11
Thread Starter 
That's exactly it I think, I'll test it and let you know
post #5 of 11
Quote:
Originally Posted by blangblang View Post

Correct me if I'm wrong, but my first instinct is that this is a pretty simple graph/combinatoric problem. Do the numbers violate the handshaking lemma? Given N players, does any player state that they played more than N-1 matches? Does the total number of matches exceed N choose 2? If all three answers are no, the tournament is possible.

I think the total matches have to be 2 * n choose 2 since each game will be reported twice
post #6 of 11
Quote:
Originally Posted by AchuSaysBlessYou View Post

I think the total matches have to be 2 * n choose 2 since each game will be reported twice

Good catch, that's exactly right.
TheHydra
(13 items)
 
  
CPUMotherboardGraphicsRAM
i7 860 @ 3.6 EVGA P55 FTW Sapphire TOXIC 2GB 6950 CORSAIR XMS3 4 x 2GB CMX4GX3M2A1600C7 
Hard DriveOSKeyboardPower
C300 64Gb + 2x F3 HD103SJ 1TB in RAID 0 Win7 x64 Razer BlackWidow Corsair 750HX 
CaseMouseMouse Pad
Lian Li A05NB with 140mm top fan. Razer DeathAdder Razer Kabuto 
  hide details  
Reply
TheHydra
(13 items)
 
  
CPUMotherboardGraphicsRAM
i7 860 @ 3.6 EVGA P55 FTW Sapphire TOXIC 2GB 6950 CORSAIR XMS3 4 x 2GB CMX4GX3M2A1600C7 
Hard DriveOSKeyboardPower
C300 64Gb + 2x F3 HD103SJ 1TB in RAID 0 Win7 x64 Razer BlackWidow Corsair 750HX 
CaseMouseMouse Pad
Lian Li A05NB with 140mm top fan. Razer DeathAdder Razer Kabuto 
  hide details  
Reply
post #7 of 11
I think the max matches could be n * (n-1) , that your input should not exceed for the tournament to be possible.


For 4 players:-

A: AB,AC,AD :3
B: BA,BC,BD :3
C: CA,CB,CD :3
D: DA,CB,CD :3

= (n-1) * n = (4-1) * 4 = 12


For 5 players:-

A: AB,AC,AD,AE :4
B: BA,BC,BD,BE :4
C: CA,CB,CD,CE :4
D: DA,CB,CD,CE :4
E: EA,EB,EC,ED :4

= (n-1) * n = (5-1) * 5 = 20


But then as each player gets a max of n-1 matches, you will have to check on false inputs like your last case.
My System
(13 items)
 
  
CPUMotherboardGraphicsRAM
i5 2500k ASUS - P8Z68-V/GEN3 GTX 770 DDR3 - 8G 
Hard DriveOSMonitorPower
WD Green Win 7 x64 Dell ST2320L Corsair 750TX 
CaseMouse
Coolermaster 310 Logitech G502 
  hide details  
Reply
My System
(13 items)
 
  
CPUMotherboardGraphicsRAM
i5 2500k ASUS - P8Z68-V/GEN3 GTX 770 DDR3 - 8G 
Hard DriveOSMonitorPower
WD Green Win 7 x64 Dell ST2320L Corsair 750TX 
CaseMouse
Coolermaster 310 Logitech G502 
  hide details  
Reply
post #8 of 11
I think this is actually a lot harder than we are all giving it credit for. The minimum number of matches any one (or more) players played is also a factor.

8 2 1 1 0 0 0 0 0 = 1
8 2 2 0 0 0 0 0 0 = 0

the total number of matches must be less than 2n-1 (.. and %2==0 for input validation), but there is no lower bound. that case there to me looks like a graph problem. hrmmm let me get my notebook and draw this up a bit
Edited by lloyd mcclendon - 4/26/12 at 11:43pm
stable again
(25 items)
 
  
CPUCPUMotherboardGraphics
E5-2687W E5-2687W ASUS Z9PED8-WS EVGA GTX 570 (Linux host) 
GraphicsRAMHard DriveHard Drive
EVGA GTX 970 FTW (win7 guest) 64GB G.SKILL 2133 2x Crucial M4 256GB raid1 4x 3TB raid 10 
CoolingCoolingCoolingCooling
2x Apogee HD  2x RX 480 2x MCP 655 RP-452x2 rev2 (new) 
CoolingCoolingOSOS
16x Cougar Turbine CFT12SB4 (new) EK FC 580 Gentoo (host) Gentoo (x23 guests) 
OSMonitorMonitorPower
windows 7 (guest w/ vfio-pci) Viewsonic 23" 1080P Viewsonic 19" Antec HCP Platinum 1000 (new) 
CaseOtherOther
Case Labs TH10 (still the best ever) 2x Lamptron FC-5 IOGEAR 2 way DVI KVM Switch 
  hide details  
Reply
stable again
(25 items)
 
  
CPUCPUMotherboardGraphics
E5-2687W E5-2687W ASUS Z9PED8-WS EVGA GTX 570 (Linux host) 
GraphicsRAMHard DriveHard Drive
EVGA GTX 970 FTW (win7 guest) 64GB G.SKILL 2133 2x Crucial M4 256GB raid1 4x 3TB raid 10 
CoolingCoolingCoolingCooling
2x Apogee HD  2x RX 480 2x MCP 655 RP-452x2 rev2 (new) 
CoolingCoolingOSOS
16x Cougar Turbine CFT12SB4 (new) EK FC 580 Gentoo (host) Gentoo (x23 guests) 
OSMonitorMonitorPower
windows 7 (guest w/ vfio-pci) Viewsonic 23" 1080P Viewsonic 19" Antec HCP Platinum 1000 (new) 
CaseOtherOther
Case Labs TH10 (still the best ever) 2x Lamptron FC-5 IOGEAR 2 way DVI KVM Switch 
  hide details  
Reply
post #9 of 11
As has already been pointed out, the maximum number of games is n(n-1). The more difficult thing is when you have fewer than the maximum. I just ran through plotting all the minimum combinations of n=2 through n=10 in Excel to confirm my suspicion. The minimum number of games is 2(n-1). Here are the results for the some valid combinations of the minimum number of games for 2 through 10 (code used for monospaced font):
Code:
2  1 1
3  2 1 1
4  2 2 1 1
5  2 2 2 1 1
6  3 2 2 1 1 1
7  3 3 2 1 1 1 1 
7  3 2 2 2 1 1 1
8  3 3 2 2 1 1 1 1
9  3 3 2 2 2 1 1 1 1
9  4 2 2 2 2 1 1 1 1 
10 4 3 2 2 2 1 1 1 1 1

There is a clear pattern here for the minimum number of games. The tricky thing is that once you get to a higher value n (this seems to start at 7), the combinations can start shifting. As far as I can tell, this requires a log(2) algorithm that will divide n/2 repeatedly. Any time that the dividend is odd, the player with the most games may steal a game from middle player. However, games played can also be shifted in other ways, as demonstrated by the second example of 9. I haven't thought about this much but it seems like the only time when there is only one combination of minimum games is when n is a power of 2.

Hope that made sense and there's no glaring error there. It's 2 AM and I don't know why I'm up doing this when I have a paper to write. biggrin.gif
Edited by ChaoticKinesis - 4/26/12 at 11:10pm
     
CPUMotherboardGraphicsRAM
Intel Core i7-4770K Gigabyte G1.Sniper M5 EVGA GTX 780 SC Crucial Ballistix Sport 2 x 8GB 
Hard DriveHard DriveHard DriveOptical Drive
Samsung 840 Pro 256GB Seagate Barracuda 3TB Seagate Barracuda 4TB Asus BD-ROM 
CoolingOSMonitorKeyboard
Noctua NH-D14 Windows 8 Pro Dell U2713HM Ducky YOTD (MX Brown) 
PowerCaseMouseMouse Pad
SeaSonic SS-760XP2 Fractal Design Arc Mini Roccat Savu SteelSeries 9HD 
Audio
Beyerdynamic DT990 250 Ohm 
CPUMotherboardGraphicsRAM
AMD A6-3500 Asrock A75M HD 6530D Samsung 4GB DDR3 1600  
Hard DriveHard DriveHard DriveOptical Drive
Intel 320 80GB Samsung Spinpoint F4 2TB WD Caviar Green 3TB Sony BD-Rom 
CoolingOSMonitorKeyboard
Noctua NH-C12P SE14 Win 7 Professional 64-bit Samsung LN46C600 Lenovo N5902 
PowerCaseOther
Corsair CX430 Antec Veris Fusion HDHomeRun Prime 
CPUMotherboardGraphicsRAM
AMD Phenom II X3 B55 Asus M5A99X EVO Sapphire HD 7950 G.Skill 8GB DDR3 
Hard DriveOptical DriveCoolingMonitor
Samsung F3 1TB LG DVD-RW CM Hyper 212 Plus Dell U2312HM 
KeyboardPowerCaseMouse
Pink KBT Race (MX Blue) Lepa G700-MA Corsair 500R Razer Abyssus 
Mouse Pad
Razer Goliathus Speed 
  hide details  
Reply
     
CPUMotherboardGraphicsRAM
Intel Core i7-4770K Gigabyte G1.Sniper M5 EVGA GTX 780 SC Crucial Ballistix Sport 2 x 8GB 
Hard DriveHard DriveHard DriveOptical Drive
Samsung 840 Pro 256GB Seagate Barracuda 3TB Seagate Barracuda 4TB Asus BD-ROM 
CoolingOSMonitorKeyboard
Noctua NH-D14 Windows 8 Pro Dell U2713HM Ducky YOTD (MX Brown) 
PowerCaseMouseMouse Pad
SeaSonic SS-760XP2 Fractal Design Arc Mini Roccat Savu SteelSeries 9HD 
Audio
Beyerdynamic DT990 250 Ohm 
CPUMotherboardGraphicsRAM
AMD A6-3500 Asrock A75M HD 6530D Samsung 4GB DDR3 1600  
Hard DriveHard DriveHard DriveOptical Drive
Intel 320 80GB Samsung Spinpoint F4 2TB WD Caviar Green 3TB Sony BD-Rom 
CoolingOSMonitorKeyboard
Noctua NH-C12P SE14 Win 7 Professional 64-bit Samsung LN46C600 Lenovo N5902 
PowerCaseOther
Corsair CX430 Antec Veris Fusion HDHomeRun Prime 
CPUMotherboardGraphicsRAM
AMD Phenom II X3 B55 Asus M5A99X EVO Sapphire HD 7950 G.Skill 8GB DDR3 
Hard DriveOptical DriveCoolingMonitor
Samsung F3 1TB LG DVD-RW CM Hyper 212 Plus Dell U2312HM 
KeyboardPowerCaseMouse
Pink KBT Race (MX Blue) Lepa G700-MA Corsair 500R Razer Abyssus 
Mouse Pad
Razer Goliathus Speed 
  hide details  
Reply
post #10 of 11
it's definitely a graph matching problem. It's beyond number crunching as different cases will have different results based on how one thing relates to the other things. You can check up front that n%2==0 && Em < 2n-1, but if that's met, you have to build the graph

lay out the nodes that have a nonzero edge count, draw the edges but leave them unconnected.
for each edge, try to connect it to another node's available edge and mark both of them off
is there _any way to connect the graph such that all edges are connected and no two nodes have more than one connection to each other
Code:
2 2 1 1

  A B C D
A X 1
B 1 X
C      X
D        X

now .. i'm not even sure if that's the right and correct approach yet, but thinking through it a bit i think it would at least work. as far as coding it, i haven't got much besides a brute forceish type approach with 2 or 3 for loops or recursion .. there's probably a clean way. it reminds me a little bit of the stable marriage problem, but it's not a bipartite graph...
Edited by lloyd mcclendon - 4/26/12 at 11:37pm
stable again
(25 items)
 
  
CPUCPUMotherboardGraphics
E5-2687W E5-2687W ASUS Z9PED8-WS EVGA GTX 570 (Linux host) 
GraphicsRAMHard DriveHard Drive
EVGA GTX 970 FTW (win7 guest) 64GB G.SKILL 2133 2x Crucial M4 256GB raid1 4x 3TB raid 10 
CoolingCoolingCoolingCooling
2x Apogee HD  2x RX 480 2x MCP 655 RP-452x2 rev2 (new) 
CoolingCoolingOSOS
16x Cougar Turbine CFT12SB4 (new) EK FC 580 Gentoo (host) Gentoo (x23 guests) 
OSMonitorMonitorPower
windows 7 (guest w/ vfio-pci) Viewsonic 23" 1080P Viewsonic 19" Antec HCP Platinum 1000 (new) 
CaseOtherOther
Case Labs TH10 (still the best ever) 2x Lamptron FC-5 IOGEAR 2 way DVI KVM Switch 
  hide details  
Reply
stable again
(25 items)
 
  
CPUCPUMotherboardGraphics
E5-2687W E5-2687W ASUS Z9PED8-WS EVGA GTX 570 (Linux host) 
GraphicsRAMHard DriveHard Drive
EVGA GTX 970 FTW (win7 guest) 64GB G.SKILL 2133 2x Crucial M4 256GB raid1 4x 3TB raid 10 
CoolingCoolingCoolingCooling
2x Apogee HD  2x RX 480 2x MCP 655 RP-452x2 rev2 (new) 
CoolingCoolingOSOS
16x Cougar Turbine CFT12SB4 (new) EK FC 580 Gentoo (host) Gentoo (x23 guests) 
OSMonitorMonitorPower
windows 7 (guest w/ vfio-pci) Viewsonic 23" 1080P Viewsonic 19" Antec HCP Platinum 1000 (new) 
CaseOtherOther
Case Labs TH10 (still the best ever) 2x Lamptron FC-5 IOGEAR 2 way DVI KVM Switch 
  hide details  
Reply
New Posts  All Forums:Forum Nav:
  Return Home
  Back to Forum: Coding and Programming
Overclock.net › Forums › Software, Programming and Coding › Coding and Programming › [Java] A really hard algorithm implementation