Education Website – eLearning – Website Using HTML – CSS – JS. Education Website – eLearning – Website Free Download
CPP has two separate functions called sort and stable sort. The purpose of this post is to show the difference between the two, not to teach how to use them. Today in the codeforces contest, I got caught up in a very simple problem because I didn’t have things in mind.
Education Website – eLearning – Website Free Download
Link to the problem:
http://www.codeforces.com/problemset/problem/63/A
Here it is said that the list of names will be given as follows:
6
Jack captain
Alice woman
Charlie man
Teddy rat
Bob child
Julia woman
It should be sorted in such a way that rat comes first, then woman and child (their precedence is equal), then man and finally captain. If the precedence of both is equal, the one inputted earlier should be kept first. Then the output will be:
Teddy
Alice
Bob
Julia
Charlie
Jack
Very simple problem, I wrote the code in 5 minutes quite quickly:
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
#define READ(f) freopen(f, “r”, stdin)
#define WRITE(f) freopen(f, “w”, stdout)
struct node
{
string S;
int w;
bool operator < ( const node &b) const{
return w<b.w;}
}e[10000];
int main()
{
READ(“in”);
int N,i;
cin>>N;
for(i=0;i<N;i++)
{
string name, X;
cin>>name>>X;
e[i].S=name;
if(X==”rat”)e[i].w=1;
if(X==”woman”)e[i].w=2;
if(X==”child”)e[i].w=2;
if(X==”man”)e[i].w=3;
if(X==”captain”)e[i].w=4;
}
sort(e,e+N);
for(i=0;i<N;i++)
cout<<e[i].S<<endl;
return 0;
}
Thinking that there is no possibility of mistake, I locked it and continued to see the code of others. After the system test, I saw the wrong answer, which was completely unexpected in such a simple problem. After submitting the volume, I realized where the problem was after seeing the case for which it was being mistaken. The case is:
20
Wswwcvvm woman
Btmfats rat
I rat
Ocmtsnwx man
Urcqv rat
Yghnogt woman
Wtyfc man
Wqle child
Ujfrelpu rat
Dstixj man
Ahksnio woman
Khkvaap woman
Sjppvwm rat
Egdmsv rat
Thank you
Nquicjnw rat
Lh captain
Tdyaqaqln rat
Qtj rat
Tfgwijvq rat
My output came:
Tfgwijvq
Btmfats
I
Qtj
Urcqv
Tdyaqaqln
Nquicjnw
Dank
Ujfrelpu
Egdmsv
Sjppvwm
Khkvaap
Ahksnio
Wqle
Yghnogt
Wswwcvvm
Dstixj
Wtyfc
Ocmtsnwx
Lh
This is definitely wrong. Tfgwijvq should initially be replaced by btmfats because it is earlier in the input.
Here is the difference between sort() and stable_sort(). The latter keeps the input sequence right, the former doesn’t. After submitting the code by writing stable_sort(e,e+N) it got accepted even though I ate the catch. But it is better to learn from them than to be caught in a big contest.
Hands on Graph Theory – 3 (Graph Store in Variables-2)
In this episode I will write about the 2nd method of graph storage with adjacency list. In this method, more efficient code can be written using less memory by storing the graph. In this case we will dynamically allocate memory, no fear, the work can be done very easily by using standard template library (STL) of C++. At the end of the previous post I linked some tutorials on STL, hope you now know how vectors work.
Education Website – eLearning – Website Free Download
As scary as adjacency list sounds, it is actually quite simple.
Now create a list like the marketing list:
This is the adjacency list, a list of which nodes are connected to which nodes. But how to store this list while coding?
first way(array):
The list can be stored using a simple 2D array. For example:
arr[1][1]=2, arr[1][2]=4;
arr[2][1]=1; arr[2][2]=4, arr[2][3]=5;
But storing it like this has some problems:
Problem 1. We have 6 nodes. Each node can have a maximum of 6 nodes associated with it (assuming no more than 1 connection between two nodes). In this case we need an integer array of size [6][6]. If only 2 nodes are connected to node 1 then rest of array[1][0],array[1][1] will be used, space from array[1][2] to array[1][6] will be useless. .
It may seem that this is not even a problem. But consider a graph with 10000 nodes. You cannot use [10000][10000] integer array, memory limit will be exceeded, also wasting memory like this is not a sign of good programmer :). As was the memory problem when using the adjacency matrix, that problem will still remain.
Problem 2. Another variable must be maintained for each index to keep track of how many elements are at which index in the array.
Second way(Vector):
To eliminate the problem we will store the graph using STL vector or list. In vector/list you don’t have to specify the size of the list, just specify the maximum number of nodes. In this tutorial I will use vectors because lists have several problems.
When inputting a graph of 100,000 nodes, never give it as a matrix, then the size of the input will become excessively large. It can provide input as shown in the 2nd example in the previous post, that is, first by telling the number of nodes and edges, then it will tell who is connected to which node. Input for the above graph:
6 8 //node-edge
1 2 //node1-node2
1 4
2 4
2 5
4 5
5 3
3 6
6 6
It takes input with vectors like this:
#include <cstdio>
#include <vector>
using namespace std;
#define MAX 100000 //maximum node
vector <int> edges[MAX];
vector <int> cost[MAX]; //parallel vector to store costs;
int main() {
int numNodes, numEdges;
scanf(“%d%d”, &numNodes, &numEdges);
for (int i = 1; i <= numEdges; i++) {
int x, y;
scanf(“%d%d”, & x, & y);
edges[x].push_back(y);
edges[y].push_back(x);
cost[x].push_back(1);
cost[y].push_back(1);
}
return 0;
}
The cost vector is not needed for this graph, but is definitely needed for the weighted graph. Surely you understand that edge and cost vectors will work in parallel, that is, in the position of edge vector you will get the connection of two specific nodes, you will get cost in that position of cost vector.
If there are 1000 or less nodes then matrix or list will not be a memory problem in any case. Also we will store the graph with vectors. Because, imagine you need to find out what is connected to 1 in a matrix of 100 nodes, matix[1][0],matrix[1][1]…….matrix[1][99] checks 100 positions like this, which one has 0 No need to extract, no matter how many nodes are connected to node 1. So even here the array cannot give us additional benefits.
Before Download
You must Join our Facebook Group and Subscribe YouTube Channel
All Links in Below:
Join Our FreeWebsiteCreate Facebook Group to get an instant update for projects, templates, design resources, and solutions.
Join Our YouTube Channel & Subscribe with Bell Icon for New Video:
Join Our Official Facebook Page For the Latest updates All Code Projects are Free:
Visit our service page to get premium services.
Free Website Create – HTML CSS, PHP, JavaScript Programming Projects For Free
Follow Us
Thank You,
Before Download
You must Join our Facebook Group and Subscribe YouTube Channel
FreeWebsiteCreate.net tries to provide HTML, CSS, SCSS, JavaScript, React, Android Studio, Java, PHP, Laravel, Python, Django, C#(C Sharp), and ASP.net-related projects 100% free. We try to make learning easier. Free Website Create always tries to give free projects to new learners. Free projects and source code will help to learn quickly.
They can save time and learn more. In this post, we share a free portfolio project website code with HTML and CSS. This free code portfolio contains a single landing page with a responsive design. In this post, we get a free best carpenter and craftsman service website designed by FreeWebsiteCreate with HTML, CSS, Bootstrap, and JavaScript.