The Official Programming Thread

Aren't there two variables here? If I understood the problem correctly, then the number of queens (say m) and dimensions of board (say n) both should be considered as variables (over which running time has to be described).

Maybe I misunderstood the problem, but isn't it somewhat trivial (assuming the only variable is dimension of the board)? So suppose the board size is n x n. Say n=20. So the coordinates of the lower-left corner is (1,1) and the coordinates of the upper-right corner are (20,20). Suppose you are given coordinates of any two queens, say (x1,y1) and (x2,y2).

We can just set two variables X and Y:
X=x2-x1
Y=y2-y1

Now a queen on (x1,y1) can attack a queen on (x2,y2) only if one of the following is true:
a) X=Y
b) X=-Y
c) X=0
d) Y=0

To elaborate on the previous post, consider the following two simplistic methods of finding the given function (whether any queen can attack any other):

a) Iterate over all the positions of the queens individually. Check whether all of the cells which are in attack range of the given queen are free. If they are free then move to the next queen position and do the same.

It seems that running time for this method will be in O(m.n) because at each individual position we roughly have to check 4.n cells (sometimes a little less ... depending on the position).

b) Make a double loop for all combination of queen positions and check directly whether any one attacks any other (using the conditions I described in the previous post).

Running time for this method will be in O(m^2). The board size should be irrelevant in this.

---

I don't know whether we can do significantly better than any of these two simple methods.

My third post got deleted .... I will just repeat the few points that need to be completed.

If we denote "n" as dimension of the board, then we can see quite easily that there can't be more than n queens placed on the board such that all of them are safe.

Using that fact, it can be shown that the running time for the first method (in the previous post) is also in O(n^2). That follows from the fact that you can't place more than n queens on board of size nxn, while keeping them all safe (so an upper-bound of (4n).n+4n on the running time can easily be established).

If you add the condition that "if(m>n) return false" at the beginning of second method, its running time will also be
in O(n^2) for sure. What if you don't add it? I haven't thought about it fully

In practice, we would add the "if condition" above for both methods at any rate. In that case the second method would be better when m is much smaller than n.

------

Another interesting function is the maximum number of queens(ouput) that can be placed on a board of given dimensions(input), such that all of them are safe. It can be programmed easily, but how efficiently?


edit: corrected a small mistake

Guys new to programming and need help

Imgur: The most awesome images on the Internet


Getting some different value in cm But in C it works just fine but in C++ i get this need help please

Eternal Blizzard said:

I don't get what is the problem? Cm value is correct

Click to expand...

idk whats the problem here

I'm having really hard time understanding Analysis of algorithms, can any body direct me to a book or tutorial from where i can get a good hold of this subject.

I also have a question



Solution for first two

For all the web developers out there, I want to create a sort of directory and have a search function on my website. Is there an easier way to do it without PHP? If not, how do I do it WITH PHP? Kind of a naive question I assume

Guys need help in the following C++ Program


Write a program to declare a 2-dimensional Matrix A of size R X C, and input values in all elements then do the following

a) Find the Smallest and Largest Element in Matrix A
b) Find Sum of each Row and Column of Matrix A
c) Find the Sum of the Diagonals of matrix A.
d) Find Transpose of Matrix A
e) Check wether the Matrix you entered is an identity matrix or not.

kkkhattak said:

Guys need help in the following C++ Program


Write a program to declare a 2-dimensional Matrix A of size R X C, and input values in all elements then do the following

a) Find the Smallest and Largest Element in Matrix A
b) Find Sum of each Row and Column of Matrix A
c) Find the Sum of the Diagonals of matrix A.
d) Find Transpose of Matrix A
e) Check wether the Matrix you entered is an identity matrix or not.

Click to expand...

Have you done this? Is this a class assignment? ?

Sent from my LG-H818 using Tapatalk

kkkhattak said:

Guys need help in the following C++ Program


Write a program to declare a 2-dimensional Matrix A of size R X C, and input values in all elements then do the following

a) Find the Smallest and Largest Element in Matrix A
b) Find Sum of each Row and Column of Matrix A
c) Find the Sum of the Diagonals of matrix A.
d) Find Transpose of Matrix A
e) Check wether the Matrix you entered is an identity matrix or not.

Click to expand...

what help you need in this assignment? understanding how it is solved ? bcz this basic matrix operation in c++ code is already available in many books and internet .
well matrix is btw just playing with array indexes nothing complex ,

Newton said:

Have you done this? Is this a class assignment? ?

Sent from my LG-H818 using Tapatalk

Click to expand...

puppet said:

what help you need in this assignment? understanding how it is solved ? bcz this basic matrix operation in c++ code is already available in many books and internet .
well matrix is btw just playing with array indexes nothing complex ,

Click to expand...

yes it was a class assignment and have already done it but thanks for your time

XxRebellionxX said:

So I wanted to ask is there a way to sort a HashSet without converting the HasSet to a TreeSet in java?
I have a couple of names that I want to order, but only using HashSets.

Click to expand...

Unlike other collections which follow the rule of collection.sort(list) the hashset cannot use this because it contradicts with the hashset implementation.

You will need to put the items into another collection like array, treeset etc

Reference : HashSet (Java Platform SE 7 )

XxRebellionxX said:

I tried with treeset, it works. But the problem was there were two surnames in my Set. If I convert it to Treeset, it does sort it but removes one of the names with the same surname. Weirdly, it didn't do that if the first names were same. Regardless, I suppose I have to implement a comparator to do, I suppose? Or convert it to an ArrayList and use collections.sort?

Click to expand...

please post a sample set of the items which aren't being sorted correctly.

XxRebellionxX said:

Spoiler: show

Code:

    Friends f = new Friends();        f.add(new Person("Locke", "Lamora"));
        System.out.println(f);
        Set<Person> st = new HashSet<>();
        st.addAll(Arrays.asList(
                    new Person("Jean", "Tannen"),
                    new Person("Calo", "Sanza"),
                    new Person("Galdo", "Sanza"),
                    new Person("Sabetha", "Belacoros"),
                    new Person("Ezri", "Delmastro")
            ));
        f.add(st);

Now, the 'Sanza' surname is appears twice here. And if sort it using a treeset, one of the 'Sanza' names will be omitted. But if I change 'Jean Tannen' to 'Locke Tannen'. I now have two names with the same firstname 'Locke', and they will not be omitted by the treeset.

Click to expand...

Which name is being used for the sort? I'm assuming it's using the surname. You really should have your own comparator for this situation. In your comparator decide the order based on the last name, in case if both the last names are the same then decide on the first name; if the first names are the same too then retain their order in the sorted list. Such a comparator will give you a correct output.