Improve my skills in competitive programming

What is the connection between computer science and algorithms?

Thomas Cormen:
"I’ll tell you a little story. A true story.

In the late 1970s and early 1980s, I worked at a startup that made systems for computer-aided design. Users could define parts and store them in a library of parts. Each part could include another part by reference, so that if you changed the definition of a part, then all of its uses would update automatically. Part A could include a reference to part B, which could include a reference to part C, and so on. Circular references were not allowed, as a part could not include itself.

We had a customer that wanted the library of parts written out to tape so that each part appeared on the tape before any other part that used it. I was the only person at the company who knew that what this customer wanted was a topological sort of a directed acyclic graph. I knew that there was an efficient algorithm for this problem, and I knew where I’d seen it (in Knuth). I didn’t remember the details of the algorithm, and so I went to the library, got a copy of Knuth, and implemented the algorithm.

People at the company thought I was a god for knowing how to solve the problem, and how to solve it efficiently.

That’s why you want to know about algorithms."

Sieve of Eratosthenes

Prime generator with sieve Algo:

Tutorial (ENG)
shafaet tutorial (bangla)

Prime Factors Finding

Algorithm:

1) divide n by 2 till n is divided by 2 and save 2 in a list each time
2) divide n by (3 to  root(n) and only the odd numbers) if divisible save it in the list
3)if n is greater than 2 save n in the list

all the prime factors are in the list.

From Demi Guo

Programming contest is a kind of sports, no different from running. Online speed programming contests are especially exciting and competitive. You have to prepare and be ready to finish reading a problem and coding a 20-lines program in 2-3 minutes in order to beat your opponents. Your heart beats faster, when you wait in front of your computer, staring at the countdown. It has a sync scoreboard. You can also hack other people's codes to win points!!!
If I realize that I'm not among the smartest kids in the classroom, I'll definitely be more hard-working, I won't feel depressed but feel excited. I love realizing my weakness and confronting difficulties, because I know they make me conscious and tell me that I can become a even better person. I always believe that the most powerful ability we have is the ability to improve ourselves. Jack Ma (Alibaba CEO) once said, “I am very excited if I see my opponents are stronger than me in present, because I know that I will beat them and become the stronger in the future.”

Something I found on quora

From Mostafa Hany Gomaa :

"it's normal to feel frustrated, and it's even normal to sometimes feel that you're just plain stupid when practicing algorithmic problems. I felt the same way when I first started practicing on codeforces. I could only do DIV 2 level A problems, and I even got stuck on some of them sometimes. I felt so frustrated that I asked one of my friends who is a pretty good competitive programmer,  what' the use if I can't even solve some DIV2 level A problems?. He told me it's normal, and just keep going. So, I will tell you the same thing, just keep trying. The biggest mistake you can make is get too frustrated and decide to quit. I know because I quit multiple times, but it is when I persevered that I started to see some improvement. I got faster, I was able to solve tougher problems, and it became more fun. I am still not that good, yet. Right now, I can consistently solve level A, B problems, and I am starting to build consistency on C problems, but I still have to make it to harder ones, and eventually to DIV1. So my advice is stick in there, if you get stuck on a problem, think about it as much as you can and give it a lot of effort, if you're still stuck after that, then ask someone for hints, if you still can't figure it out, then look up the solution. When you read the solution, make sure you understand it well, if you found out that you're missing some background knowledge, then study that. Also, it's very important to implement the solution after understanding it. Another important thing to consider is to save the links to the problems you couldn't figure out on your own so that you can revisit them later. If you revisit the problem at a later time, and you still couldn't solve it, then you didn't really understand its solution well enough. Finally, don't get too scared of harder problems. It's very easy to stay in the comfort zone of solving problems that are at your level. You should always keep pushing the limit and go for harder problems, otherwise you won't learn anything new and you won't see much improvement. Best of luck, and have fun :)."

Light OJ 1074 - Extended Traffic

Problem link - 1074 - Extended Traffic

In this problem we have to compute minimum earning from node 1. At first we have to do a dfs to see if destination is reachable from 1.Every node that can be reached with negative earning , all its adjacent nodes can be reached with negative earning too.

If a node if not reachable from 1 or or the earning is less than 3 then we have to print '?' else we have to print ta earning from 1. We can use bellman ford algorithm from this problem as there are negative earnings.

let us analyze some test cases:

1

5

6 7 8 9 10

6

1 2

2 3

3 4

1 5

5 4

4 5

2

4

5

here node 4 (D) can be reached with earning 3 and node 5(E) can be reached with earning 4

Breadth-first search implementation

I learned bfs from my friend and from this blog shafaetsplanet . In shafaetsplanet the algorithm is explained very easily. There the bfs code was implemented using adjacent metrix. Here we will implement it using adj list.

from safaet's blog I will take few lines to show everyone how bfs works

     01. A node can't be visited more than once.
     02. The source node is always level 0.
     03. All nodes directly connected to level 0 or source node are level 1.
     04. All nodes directly connected to level 1 are level 2.And this is how level will keep on rising one by one.
     05. Level of each node is the shortest path distance from its source node


Basic Graph:

Run Meter (pedometer app android) (2nd year,2nd semester)

A basic pedometer app which counts calorie burned while running or cycling  for fulfillment of my 2nd year,2nd semester Project Work.

Screenshot:

Unity Pos System Using Java Netbeans and Database (2nd year,1st semester)

This Project has been designed and developed for fulfillment of my 2nd year,1st semester Project Work.

Video:

Run Away using c++(1st year,2nd semester)

A 2D game on basic c and c++ for fulfillment of my 1st year,2nd semester Project Work.

Screenshot:

Second best mst (using Kruskal)

Sometimes we are asked to find Second best mst in some problems. We can do this with brute force.
At first we will find the mst and all the edges of mst. From all the edges of mst we will remove every edge once and and will create a new mst. In this way the minimum of all newly created mst is the Second best mst

mst:

yellow edges are edges of mst

sum of all weights is 110.

minimum spanning tree (Kruskal's algorithm) Implementation

There is an awesome kruskal algorithm tutorial  in - shafaetsplanet

here I will try to implement the algorithm in my way

a normal undirected graph

Light OJ 1041 - Road Construction

Problem link -  1041 - Road Construction

In this problem we are given m roads with this roads we have to create a mst. If there are n cities and if we can select n-1 edges from  all edges when running mst then we can say we have a solution as we got a tree :-)

For mapping the cities we can use STL map.

Light OJ 1040 - Donation

Problem link - 1040 - Donation

Its a very basic mst problem.

let us try to analyze some test case

2

27 26

1 52