Thread: programming help

Hey all, I am trying to solve problem j of this site(PAGE 19)
http://icpc.baylor.edu/icpc/press/20...ProblemSet.pdf


FOR EXAMPLE, IF you have this..the answer is 2
4 6
1 2
1 3
2 4
3 4
4 0
4 0


I wrote the code now.I read the number of rooms, then tunnels. I store all the others in an array. I check if at 1 there is a bridge to 0..if so i break it and increment count.
then i increment count2++..the number of bridges from 1 to other rooms.
i check later on for each room how many tunnels are connected.

in the above example..at first o is 2, then room 2 tunnels is 2..since o >= count2..so o is still 2..
then room 3 evaluated..since count2 = 2..then o is 2..
then room 4 evaluated..since its 4..o stays 2..


I know this works in some cases but not all.. how can I fix it, can someone help me algorithmic wise.
in this example it doesnt work.

4 6
1 2
1 3
1 4
1 2
4 0
4 0

the answer gives 3, while it should be one.you break the bridge between 1 and 4.
please help.

Code:

#include <stdio.h>
#include <stdlib.h>

int main(void)

{

                FILE *ifp, *ofp; /* input file pointer,output file pointer */
                ifp = fopen("c:\\test1.txt", "r"); /* open for reading */
               ofp = fopen("c:\\test2.txt", "w"); /* open for writing */


               double read_num;// the number being read from the file
               double d1[1000];// array to store numbers
               double d2[1000];// array to stor numbers, do note that d1[i] and d2[i] are connected to 
               // each   other via bridge
              double no_of_rooms = 0; // no of rooms
             double no-of_tunnels = 0; // no of bridges
             int count = 0; // count how many bridges to crush that connect 1 to 0 directly.
             int count2 = 0; // count bridges connected at some room
              int e = 0;// used to store all rooms in the array..

              if(fscanf (ifp,"&#37;lf",&read_num ) == 1 )
                 {
               
               
                              no_of_rooms  = read_num;// c is number of rooms

                                    }
 
              if(fscanf (ifp,"%lf",&read_num) == 1 )
                  {
                
                            no-of_tunnels  = read_num;// q is number of tunnels



                                           }
       
    
        // store each connected rooms by a tunnel in an array
        while(fscanf (ifp,"%lf",&read_num ) == 1 && e < no-of_tunnels )
        {
                    // note here. if rooma 1 and 2 are connected. d1[e] stores 1 and d2[e] stores 2
                     int qw = (int)read_num;
                     fscanf (ifp,"%lf",&read_num);
                     int z = (int)read_num;
                     d1[e] = qw;
                     d2[e] = z; 
                     e++;
                                       }

        int i2 = 1;// used to check until no_of_rooma..from room = i2 = 1  to room c
        int i1;// used to check from bridges i1 to q. then is restored to 0..to check for bridges for 
       // next room
        int final_answer = 0;// last number needed, the final answer of how much bridges to crush
        int yu = 0;// needed to initialize bridges to crush at room 1.
        
        while(i2<no_of_rooms )
        {
                   i1 = 0;
                   
                   while(i1< no-of_tunnels )
                   {
                        // check if room 1 has a way out directly. if so, crash that tunnel
                        if(d1[i1] == 1 && d2[i1] == 0)
                         count++;
                         // check if room 1 has a way out directly. if so, crash that tunnel
                         if(d1[i1] == 1 && d2[i1] == 0)
                          count++; 
                         // for each room check how much tunnels need to be broken
                         if(d1[i1] == 1 && d2[i1] != 0 && i2 == 1)
                         count2++;                        
                         if(d2[i1] == 1 && d1[i1] != 0 && i2 == 1)
                         count2++;
                        if(d1[i1] == i2 && d1[i1] != 1)
                         count2++; 
                         if(d2[i1] == i2 &&  d2[i1] != 1)
                         count2++;
         
                             i1++;

                                                        }

               // o at first is how much bridges we cut at 1. then if there is way to crush much less we crash at that         
               // point.
               if((o >= count2 || yu == 0))
             {
        
                    final_answer = count2;
                    yu++;
                             }
                count2 = 0;
        
                i2++;
       
       
                   
                                                       }
                  

               count += final_answer;
               printf(" ");
               printf(" ");
               printf("%d",final_answer);
                   
               fclose(ifp);
               fclose(ofp);
              return 0;
                                                  }

To assess the problem, I would suggest putting a few printfs in the code to determine which connections are causing the count to be increased. Once you figure out which connections are erroneously increasing the count (and why), you can get closer to figuring out where the error is in your algorithm.

EDIT: I would also suggest picking more descriptive variable names so I can understand what your code says. Also, please fix your indentions.

I suggest - use more wise indentation and meaningful variable names - current code is just unreadable

Originally Posted by JDGATX

To assess the problem, I would suggest putting a few printfs in the code to determine which connections are causing the count to be increased. Once you figure out which connections are erroneously increasing the count (and why), you can get closer to figuring out where the error is in your algorithm.

Such is not necessary. That's what we have debuggers for. It can do this and much more.

People are willing to take a look for you, but your code is broken in terms of indentation and meaningful variable names.
If you fix that, someone can help.

If the file is full of integers, why are you reading in doubles?
It is confusing, and further calculations might get decimal points which according to your result
should not be there.
Also why so much whitespace? A <Return> between code paragraphs should be sufficient.

It should look something like this:

Code:

#include <stdio.h>
#include <stdlib.h>

int main(void)
{
	FILE *ifp, *ofp; /* input file pointer,output file pointer */
	ifp = fopen("c:\\test1.txt", "r"); /* open for reading */
	ofp = fopen("c:\\test2.txt", "w"); /* open for writing */


	double read_num;// the number being read from the file
	double d1[1000];// array to store numbers
	double d2[1000];// array to stor numbers, do note that d1[i] and d2[i] are connected to 
	// each   other via bridge
	double no_of_rooms = 0; // no of rooms
	double no-of_tunnels = 0; // no of bridges
	int count = 0; // count how many bridges to crush that connect 1 to 0 directly.
	int count2 = 0; // count bridges connected at some room
	int e = 0;// used to store all rooms in the array..

	if(fscanf (ifp,"%lf",&read_num ) == 1 )
	{
		no_of_rooms  = read_num;// c is number of rooms
	}

	if(fscanf (ifp,"%lf",&read_num) == 1 )
	{
		no-of_tunnels  = read_num;// q is number of tunnels
	}


	// store each connected rooms by a tunnel in an array
	while(fscanf (ifp,"%lf",&read_num ) == 1 && e < no-of_tunnels )
	{
		// note here. if rooma 1 and 2 are connected. d1[e] stores 1 and d2[e] stores 2
		int qw = (int)read_num;
		fscanf (ifp,"%lf",&read_num);
		int z = (int)read_num;
		d1[e] = qw;
		d2[e] = z; 
		e++;
	}

	int i2 = 1;// used to check until no_of_rooma..from room = i2 = 1  to room c
	int i1;// used to check from bridges i1 to q. then is restored to 0..to check for bridges for 
	// next room
	int final_answer = 0;// last number needed, the final answer of how much bridges to crush
	int yu = 0;// needed to initialize bridges to crush at room 1.

	while(i2<no_of_rooms )
	{
		i1 = 0;

		while(i1< no-of_tunnels )
		{
			// check if room 1 has a way out directly. if so, crash that tunnel
			if(d1[i1] == 1 && d2[i1] == 0)
				count++;
			// check if room 1 has a way out directly. if so, crash that tunnel
			if(d1[i1] == 1 && d2[i1] == 0)
				count++; 
			// for each room check how much tunnels need to be broken
			if(d1[i1] == 1 && d2[i1] != 0 && i2 == 1)
				count2++;                        
			if(d2[i1] == 1 && d1[i1] != 0 && i2 == 1)
				count2++;
			if(d1[i1] == i2 && d1[i1] != 1)
				count2++; 
			if(d2[i1] == i2 &&  d2[i1] != 1)
				count2++;

			i1++;

		}

		// o at first is how much bridges we cut at 1. then if there is way to crush much less we crash at that         
		// point.
		if((o >= count2 || yu == 0))
		{
			final_answer = count2;
			yu++;
		}
		count2 = 0;
		i2++;
	}

	count += final_answer;
	printf(" ");
	printf(" ");
	printf("%d",final_answer);

	fclose(ifp);
	fclose(ofp);
	return 0;
}

It's called indentation.

It's not double numbers, it's pair of integers.
Well you need to reconsider your approach. A problem is not solved by the programming
language, but by the human brain that is facing it.

Code:

			// for each room check how much tunnels need to be broken
			if(d1[i1] == 1 && d2[i1] != 0 && i2 == 1)
				count2++;                        
			if(d2[i1] == 1 && d1[i1] != 0 && i2 == 1)
				count2++;
			if(d1[i1] == i2 && d1[i1] != 1)
				count2++; 
			if(d2[i1] == i2 &&  d2[i1] != 1)
				count2++;

Do you consider your code solving the problem? Asides from dealing with the trivial case for
room #1, did you construct a data structure to represent the physical structure of your
problem? You don't crush a tunnel by increasing one variable by one.
Instead when you parse the file you will need something close to a graph to map the problem,
as a data structure appropriate for solving it. After representing it correctly, you should then
think how will i block room #1, in the least number of moves. An algorithm fitting for your
question, would not be so trivial to describe or even devise in a simple post.
In fact that is your task not mine, i simply tell you that you need to completely reconsider your
so far approach.

Problems are solved on paper, then translated into programs. Otherwise you
are spending my time, your time, and the time of everybody else reading your post.

The problem solution could be formulated using graphs.
Assume that rooms are vertices, and pairs given are edges therefore a single
test case can be mapped to a graph G(V,E), where:

Code:

V={a[ι] | a[ι]εΝ}  and E={(x[ι],y[ι]), x[ι],y[i] ε R}

We can then define two graph functions that will describe the solution:
The first function is minimumPath(R1, R2), which returns the minimum path of
E[i] ε E, from rooms R1,R2: R1,R2 ε V.
The second function is a boolean isConnected(R1,R2), which returns true if
there is a path connecting rooms R1,R2 ε V.
And the solution in pseudocode would look something like this.
Let X be the variable that holds the result answer.

Code:

WHILE(isConnected(1,0)) DO
BEGIN
    P = minimumPath(1,0);
    X += NUMBER_OF_EDGES(P);
    REMOVE_PATH(G,P);
END

The logic should work for an arbitrary graph, but the functions involved may have a
large time complexity as long as advanced methods are not used.