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.

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 WRITE(f) freopen(f, “w”, stdout)

struct node

{

string S;

int w;

bool operator < ( const node &b) const{

return w<b.w;}

}e;

int main()

{

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.

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=2, arr=4;

arr=1; arr=4, arr=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 . If only 2 nodes are connected to node 1 then rest of array,array will be used, space from array to array will be useless. .

It may seem that this is not even a problem. But consider a graph with 10000 nodes. You cannot use  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,matrix…….matrix 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.

## Join Our FreeWebsiteCreate Facebook Group to get an instant update for projects, templates, design resources, and solutions.

Free Website Create – HTML CSS, PHP, JavaScript Programming Projects For Free

## Thank You,

Stay with FreeWebsiteCreate.net

Share the post if necessary.

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.

To get a free website project code,