The Official Programming Thread

r3v3rs3

Proficient
May 25, 2007
586
1
23
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
 
Last edited:

r3v3rs3

Proficient
May 25, 2007
586
1
23
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.
 
Last edited:

r3v3rs3

Proficient
May 25, 2007
586
1
23
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 :p

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
 
Last edited:

prohyper

Proficient
Aug 24, 2011
837
0
21
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


Code:
Now can anybody explain me how we get these values ? especially logn, nlogn and n!.

my calculation is that

10^6 = 1 sec.

n = 10^6.
n^2 = 10^12 but in solution its 10^3
n^3 = 10^18 but in solution its 10^2
n^1/2 = 10^3 but in solution its 10^12
 
Last edited by a moderator:

EternalBlizzard

Lazy guy :s
Moderator
Oct 29, 2011
2,733
1,192
129
Attractor Field Beta
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


Code:
Now can anybody explain me how we get these values ? especially logn, nlogn and n!.

my calculation is that

10^6 = 1 sec.

n = 10^6.
n^2 = 10^12 but in solution its 10^3
n^3 = 10^18 but in solution its 10^2
n^1/2 = 10^3 but in solution its 10^12
I don't know how you are solving that... I'd do this with inequalities...

F( n ) <= 1sec
or
F( n ) <= 10^6 micro seconds

Now for F( n ) = n^2 put the function

n^2 <= 10^6 microseconds
n <= 10^3 microseonds ------------ This is the answer. The largest possible value for n for which F( n ) i.e n^2 gives 1 second

On 2nd thought you don't need inequalities here i misunderstood the question. It can be done with simple Equations ( = sign) too.
 
Last edited:

Fate

-
Aug 21, 2015
61
0
0
Karachi
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
 

kkkhattak

Active member
Aug 18, 2012
304
0
21
Peshawar
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.
 
Last edited:

Newton

Well-known member
May 17, 2009
2,223
0
41
Lahore, Faisalabad
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.
Have you done this? Is this a class assignment? ?

Sent from my LG-H818 using Tapatalk
 

puppet

Well-known member
Sep 30, 2013
2,169
0
42
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.
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 ,
 

kkkhattak

Active member
Aug 18, 2012
304
0
21
Peshawar
Have you done this? Is this a class assignment? ?

Sent from my LG-H818 using Tapatalk
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 ,
yes it was a class assignment and have already done it :D but thanks for your time :D
 

XxRebellionxX

Moderator
Moderator
Mar 10, 2010
6,130
0
42
Dublin
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.
 

Newton

Well-known member
May 17, 2009
2,223
0
41
Lahore, Faisalabad
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.

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

Moderator
Moderator
Mar 10, 2010
6,130
0
42
Dublin
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 )
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?
 

Newton

Well-known member
May 17, 2009
2,223
0
41
Lahore, Faisalabad
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?
please post a sample set of the items which aren't being sorted correctly.
 

XxRebellionxX

Moderator
Moderator
Mar 10, 2010
6,130
0
42
Dublin
please post a sample set of the items which aren't being sorted correctly.
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.
 

Newton

Well-known member
May 17, 2009
2,223
0
41
Lahore, Faisalabad
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.
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.
 
General chit-chat
Help Users
We have disabled traderscore and are working on a fix. There was a bug with the plugin | Click for Discord
  • No one is chatting at the moment.
  • faraany3k faraany3k:
    I dont think games have looked any better since 2019 onwards and they are performing worse and worse. Game developers have really dropped the ball.
    Link
  • Necrokiller Necrokiller:
    Consoles can't even catch a break in titles developed exclusively for them 😢
    Link
  • Necrokiller Necrokiller:
    "All of this lends the game distinctly last-gen look at times, which is compounded by image quality and frame-rate issues."
    Link
  • Necrokiller Necrokiller:
    Link
  • Chandoo Chandoo:
    no jokes.
    Link
  • Chandoo Chandoo:
    faraany3k said:
    So while Playing Control, I found a journal which said that a bathroom is missing in Islamabad Beurue of Control. With Alan Wake and Control seems to be connected worlds. Even our city is in the universe as well. No wonder those Trail 5 and Trail 6 are haunted.
    did you know you can see @NaNoW credited in the game too ? :p
    Link
  • faraany3k faraany3k:
    So while Playing Control, I found a journal which said that a bathroom is missing in Islamabad Beurue of Control. With Alan Wake and Control seems to be connected worlds. Even our city is in the universe as well. No wonder those Trail 5 and Trail 6 are haunted.
    Link
  • EternalBlizzard EternalBlizzard:
    faraany3k said:
    What is peoples obsession with Battle Royale genre. 6 minutes to find a match, 3 minutes to setup a match, 2 minutes to land, 10 minutes for scavanging maybe 2 3 gunfigts and its over. Multiplayer landscape is looking absolute dogshit.
    I tried playing Apex Legends once. Couldn't find a gun for 5 minutes straight. If I found a gun, I couldn't find the right ammo for it. Got killed fighting with my fists. Uninstalled it the next day.
    Link
  • faraany3k faraany3k:
    What is peoples obsession with Battle Royale genre. 6 minutes to find a match, 3 minutes to setup a match, 2 minutes to land, 10 minutes for scavanging maybe 2 3 gunfigts and its over. Multiplayer landscape is looking absolute dogshit.
    • Like
    • Haha
    Reactions: iampasha and EternalBlizzard
    Link
  • M muneebjahangir:
    skip the villain arc
    Link
  • EternalBlizzard EternalBlizzard:
    iampasha said:
    I usually stay away from animes. Vinland saga changed the way i look at my life, and my experiences within. I recommend every breathing human being to watch this animated masterpiece at least once fromstart to finish.
    After I watched it, I never felt like i watched a show. It was a friggin journey. I got way too attached to Thorfinn and seeing him grow up and find himself and get rid of all the negativity inside of him was just pure bliss.
    Link
  • iampasha iampasha:
    EternalBlizzard said:
    Vinland Saga > Berserk
    I usually stay away from animes. Vinland saga changed the way i look at my life, and my experiences within. I recommend every breathing human being to watch this animated masterpiece at least once fromstart to finish.
    • Like
    Reactions: EternalBlizzard
    Link
  • Necrokiller Necrokiller:
    Crapcom's RE Engine expose hogaya saaeen. This shit ain't worth experiencing on any platform. 🤷‍♂️
    Link
  • Chandoo Chandoo:
    When a $399 console provides the same experience as a 4090. Yikes indeed saeen :sneaky:
    Link
  • Necrokiller Necrokiller:
    that's a yikes saaaen
    Link
  • Necrokiller Necrokiller:
    " Both PS5 and Series X have an unlocked frame-rate here, with performance that generally lies between 30fps and 45fps. That makes for a stuttering and inconsistent output in general play, no matter what you are doing at any given time."
    • Haha
    Reactions: EternalBlizzard
    Link
  • Link
  • EternalBlizzard EternalBlizzard:
    Vinland Saga > Berserk
    • Like
    Reactions: iampasha
    Link
  • faraany3k faraany3k:
    I absolutely hate parry and Sekiro made me love it, i hate sci fi and Mass Effect made me love it. This is the definition of genre defining experiences.
    Link
  • Necrokiller Necrokiller:
    Forbidden West Complete Edition now available on your fav websites. And Nixxes showed Crapcom how it's done 👍
    Link
  • Necrokiller Necrokiller:
    RE Engine is just utter shit for anything other than corridor design remakes
    Link
  • Necrokiller Necrokiller:
    This is a console first developer. LMAO
    Link
  • Link
  • faraany3k faraany3k:
    With how great cod warzone has translated onto mobile. Mainstream Consoles have lost its value even further. Maybe console gaming was associated with TVs and how TV is not the primary source of media consumption anymore, consoles will lose its 200 million core audiences even further.
    Link
  • Necrokiller Necrokiller:
    Even VRR can't rescue it 🥲
    Link
    faraany3k faraany3k: I dont think games have looked any better since 2019 onwards and they are performing worse and...