In Codeforces Round 433 Div 2, I have seen a solution of problem E.

Since, the value of n was 200000. So it was not possible to solve the problem by declaring a n*n(200000*200000) array.

But, In that solution a solver has used a vector efficiently instead of two dimensional array. I have tried but couldn't got this.

Can anyone please help me on this?

Thanks in advance.

Problem : http://codeforces.me/contest/854/problem/E

Hello everyone!!

Google Codejam is coming!! I have never been qualified for online round 2. Now I have just one month to prepare myself. Can anyone suggest me a way to practice for a well preparation.

I want to know about which sections of algorithm I must be strong for qualifying to Round 2. Mentioning, I am week in probability and expected value and geometry. Thanks.

I am trying to find the position of an element in set using lower bound or binary search i.e, in lg(n) time.

For example, Elements in set are: 1 2 4 5 7.

I need to find the position of 4 which is in 3rd position. I have tried but can't do this. Is there any way ?

Thanks in Advance.

When solving LightOJ 1144 problem then I've found a new term "Möbius function". Can Anyone please help me what is this and where and how to apply it?

Thanks in advance.

Hi!! I am facing problem on solving the following problem: http://codeforces.me/contest/128/problem/C

Actually I've tried many times but I couldn't manage to code it by myself. Then I've seen others code which is done only by finding nCr, calculating combination.

Can anyone help me on this?

Thanks in advance.

I Have tried this problem for long time but not getting accepted solution. My idea was: 1) Find Strongly Connected Components.

2) Form a DAG.

3) Run topsort on the DAG.

4) A DFS for number of assasin.

But I am getting continuously WA.

Problem:

Ezio needs to kill N targets located in N different cities. The cities are connected by some one way roads. As time is short, Ezio can send a massage along with the map to the assassin's bureau to send some assassins who will start visiting cities and killing the targets. An assassin can start from any city, he may visit any city multiple times even the cities that are already visited by other assassins. Now Ezio wants to find the minimum number of assassins needed to kill all the targets.

Input

Input starts with an integer T (≤ 70), denoting the number of test cases.

Each case starts with a blank line. Next line contains two integers N (1 ≤ N ≤ 1000) and M (0 ≤ M ≤ 10000), where N denotes the number of cities and M denotes the number of one way roads. Each of the next M lines contains two integers u v (1 ≤ u, v ≤ N, u ≠ v) meaning that there is a road from u to v. Assume that there can be at most one road from a city u to v.

Output

For each case, print the case number and the minimum number of assassins needed to kill all targets.

Sample Input:

3

5 4

1 2

1 3

4 1

5 1

7 0

8 8

1 2

2 3

3 4

4 1

1 6

6 7

7 8

8 6

Sample Output:

Case 1: 2

Case 2: 7

Case 3: 2

My Solution: http://paste.ubuntu.com/14006313/

Problem Link: http://www.lightoj.com/volume_showproblem.php?problem=1429

Thanks in Advance.

I am trying to solve this problem but getting Wrong Answer several times. My Idea was Binary Search the Bandwidth and run Directed Minimum Spanning Tree each time. I am providing the problem and my code below. Anyone please help me on this. Thanks in advance.

Problem::

During 2009 and 2010 ICPC world finals, the contests were webcasted via World Wide Web. Seeing this, some contest organizers from Ajobdesh decided that, they will provide a live stream of their contests to every university in Ajobdesh. The organizers have decided that, they will provide best possible service to them. But there are two problems:

1. There is no existing network between universities. So, they need to build a new network. However, the maximum amount they can spend on building the network is C.

2. Each link in the network has a bandwidth. If, the stream's bandwidth exceeds any of the link's available bandwidth, the viewers, connected through that link can't view the stream.

Due to the protocols used for streaming, a viewer can receive stream from exactly one other user (or the server, where the contest is organized). That is, if you have two 128kbps links, you won't get 256kbps bandwidth, although, if you have a stream of 128kbps, you can stream to any number of users at that bandwidth.

Given C, find the maximum possible bandwidth they can stream.

Input

Input starts with an integer T (≤ 35), denoting the number of test cases.

Each case starts with a blank line. Next line contains three integers N, M, C (1 ≤ N ≤ 60, 1 ≤ M ≤ 104, 1 ≤ C ≤ 109), the number of universities and the number of possible links, and the budget for setting up the network respectively. Each university is identified by an integer between 0 and N-1, where 0 denotes the server.

Each of the next M lines contains four integers u, v, b, c (0 ≤ u, v < N, 1 ≤ b, c ≤ 106), describing a possible link from university u to university v, that has the bandwidth of b kbps and of cost c. All links are unidirectional. There can be multiple links between two universities.

Output

For each case, print the case number and the maximum possible bandwidth to stream. If it's not possible, print "impossible". See the samples for details.

Sample Input

3

3 4 300

0 1 128 100

1 2 256 200

2 1 256 200

0 2 512 300

3 4 500

0 1 128 100

1 2 256 200

2 1 256 200

0 2 512 300

3 4 100

0 1 128 100

1 2 256 200

2 1 256 200

0 2 512 300

Output for Sample Input

Case 1: 128 kbps

Case 2: 256 kbps

Case 3: impossible

My Code: http://paste.ubuntu.com/13223544/

I want to know which is more helpful?

1. Up-solve a single problem without any help from tutorial of contest by taking three days.
2. Up-solve two problems with the help of tutorial of contest by taking three days.

Point to be noted: In both case, My concept get clear about a particular problem.

Difference is:

1. In the case of 1, I find the technique by myself but solve 1 problem of one type.

2. In case of 2, I find the technique with the help of tutorial but I can solve 2 problems and they can be of different types.

Hi !!

How I can change my handle name? In settings option I have selected the handle tab but the message shown is : "The page is temporarily blocked by administrator."

Is there any alternative to change or there are no option to change the Handle name ?

Thanks in advance.

Hi Everybody !!! In solving dp problems, I have seen that it is easy to solve the problem recursively. But , recursive solution has so many function calling and dependencies.

There are many problem where recursive solution only produce TLE so there needs a iterative solution.

In the following problem, "There is no recursive accepted solution"-Moderator said. http://www.lightoj.com/volume_showproblem.php?problem=1232

or

http://paste.ubuntu.com/9639366/

So I need iterative as the only solution. While doing this in case of this problem I have found that it is difficult to transform recursive solution to iterative solution. I think there should be any general algo in this case.

Can you help me by give me any tips that you follow generally in that kind of transformation?

Thanks in advance.

Hi!!! A->B->C... C->B->A...A->C->B ...C->A->B

Among these orders which order you would like to follow in Div. 2 contest for good rating? or what's your technique? Sometimes I try to follow last order but most of the times doesn't work :(

I didn't mention D and E cause they are out of my range now :p I should try to Discover D and E ... How you try?

Hi !!! I am learning algorithm. I think for a contest programmer there must be a proper order to learn!! May I know the order of learning algorithm for getting next topics easy and for a better performance in contest??(I mean, which should be first,second...etc..? among number theory,data structure, dp, counting ,graph etc.)

For me, I know many of graph algorithms.But I didn't learn segment tree at all :( So, I think its not a proper way. I could never solved a graph problem in contest. I could spent this time in data structure/dp and my basic could be stronger and i could got a good rating in cf contests???

How can I quickly identify a particular problem can easily be solved by BIT? What kinds of problems can be solved by BIT other than range sum calculation & increasing sub-sequence?

Hello !! I don't understand the error tolerance(EPS) thing in geometrical problem solving very clearly.I think, to be a good programmer, I should have clear concept on any topic. So, Please anyone give me a description on this.
Thanks in advance.