Can anyone explain the intuition behind the min-cut solution of the problem of the last ARC problem E? The editorial explains it but it does not explain the meaning of the taken steps.

The solution is quite fascinating but I cannot wrap my head around the complete idea.

Thanks in advance.

How can we solve this problem by Palindromic Tree aka Eertree?

I have participated at 80 contests and solved a good number of problems on CF. But I am nowhere near any improvement. I should have been CM a long time ago.

I know most of the typical algorithms and try harder problems like div2 D, E but none of them are helping much. I mostly have contest time weakness than offline problem solving.

Continuous failure is kind of killing me and letting me drown in frustrations. What should I do? I badly need a way out here.

Here is the problem: http://codeforces.com/problemset/problem/257/C

My approach was this: http://codeforces.com/contest/257/submission/11893523

I first sorted the points clockwise. Then from the last point of the 'clockwise-sorted' array, I go clockwise and counter-clockwise to calculate two angles: Angle1 and Angle2. These two values are actually the summation of the angle between two consecutive points. I output the minimum one.

Eventually, I found out that this problem can be solved in a lot shorter way but I cannot find a bug in my approach.

Was my approach correct? If no, then what did I do wrong? If yes, then how can I get rid of the error = '0.0000388'?

So again I am writing a post about ICL2015 Finals. My last post was about a DP problem which was not that much hard. But now I am really stuck by a tough problem (I am mentioning this one as tough because number of people who solved it was really low).

What I did for this one? Well, whatever I did to solve this problem was based on this tutorial from CodeChef. You can check that out.

In short the problem is:

Given n,k,m where n,k<=10^18, m<=10^6, we need to find C(n,k)%m where C(n,k) means number of ways to choose k objects from n objects.

So, the question is: What did I do to solve this problem?

Following the tutorial, I prime factorized m. Eventually, I got some prime numbers as factors. Then I applied Lucas' Theorem for each of this prime. After calculating answers for each of this prime, I had to solve some equations of the form X = A[i] (mod M[i]).

And these equations can be solved by Chinese Remainder Theorem.

Now, where did I get stuck? I did all these things mentioned above. But when we are given an m when m has prime powers in its factorized form, I could not find a solution to calculate the required result.

Let me give a quick example.

Imagine, n=10, k=5, m=12341. To find X=C(10,5)%12341, I first prime factorized 12341. So 12341=7*41*43.

I applied Lucas' Theorem for each of the prime factors. What I got is:

X = 0 (mod 7);
X = 6 (mod 41);
X = 37 (mod 43);

Now my task was to combine this equations to find our X. I applied CRT for this and got the required answer 252. Yahooo! :D

But wait, when m=1000 (or some number with prime powers), it didn't work. :(

This is where I need a solution. I actually need to calculate C(n,r)%m where m is of the form p^a where p is a prime.

As you can realize, I am not quite good. It will be too much helpful if you share your ideas on how to solve the above mentioned problem and give instructions to code it in detail, step by step. And I will be really grateful to you. :)

PS1: I found few ideas on how to get around this problem online. But I could not understand and of course could not code anything.

PS2: Really sorry for the long post.

Cheers and thanks in advance!

I was trying to solve this problem from ICL2015div2 finals. I understand this is a problem on combinatorics (and perhaps DP) but I could not find a way towards solution.

Problem Link

I am weak in DP problems. They seem overwhelming to me most of the times. An elaborate explanations will surely be helpful for me. :)

Thanks in advance.

There is this classical problem of counting number of inversions in an array.

Let A[0...n - 1] be an array of n distinct positive integers. If i < j and A[i] > A[j] then the pair (i, j) is called an inversion of A. 

This problem can be found here.

I found this problem on CF where we need to find number of such triples (i,j,k) such that i<j<k and A[i]>A[j]>A[k].

I solved both of the problems using BIT.

For the second problem, I counted number of numbers greater than A[i] at its left (left[i]) and number of numbers less than A[i] at its right (right[i]). So the output is summation of right[i]*left[i] for all i from 0 to n-1.

Now I have a question, what if the problem is counting inversions of length N? It means we need to find number of such combinations (i,j,k,...) such that i<j<k<... and A[i]>A[j]>A[k]>...

What should be a generalized solution for this problem?

Let us have a look at this series:

nm + (n-1)(m-1) + (n-2)(m-2) + (n-3)(m-3) + ...... + (until either n==1 or m==1).

Example:

Let, n=5, m=3. So we need to find the summation of

5.3 + 4.2 + 3.1

Well, what I need is a closed form. And how should I find out a closed form of such kind of series?

Thanks in advance! :)

Problem Statement:

Yes, you are developing a 'Love calculator'. The software would be quite complex such that nobody could crack the exact behavior of the software.

So, given two names your software will generate the percentage of their 'love' according to their names. The software requires the following things:

1. The length of the shortest string that contains the names as subsequence.
2. Total number of unique shortest strings which contain the names as subsequence.

Now your task is to find these parts.

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

Each of the test cases consists of two lines each containing a name. The names will contain no more than 30 capital letters.

Output For each of the test cases, you need to print one line of output. The output for each test case starts with the test case number, followed by the shortest length of the string and the number of unique strings that satisfies the given conditions.

You can assume that the number of unique strings will always be less than 263. Look at the sample output for the exact format.

Sample Input:

3

USA USSR

LAILI MAJNU

SHAHJAHAN MOMTAJ

Sample Output:

Case 1: 5 3

Case 2: 9 40

Case 3: 13 15

How to solve the second part of the problem? I mean how can I find "Total number of unique shortest strings which contain the names as subsequence."?

I was trying to solve this problem http://lightoj.com/volume_showproblem.php?problem=1201 on LightOJ. My algo was to split the graph into two sets (vectors A and B) (since the graph is undirected and acyclic and so bipartite). Then I found the maxBPM from A to B and the answer is number of nodes-maxBPM.

Here is my cod: http://paste.ubuntu.com/8170061/

What is my mistake actually?

Problem Description:

"Yes, I am the murderer. No doubt" I had to confess it in front of all. But wait, why I am confessing? Nobody wants to go to jail, neither do I. As you have suspected there is something fishy. So, let me explain a bit.

The murder was happened in 19th June, at 11:30 pm this year (2009) according to the medical report. So, I was asking the judge "Can you find the time 19th June 11:30 pm in Bangladesh?" The judge informed other reporters to find the time. But alas! There was no time — "2009, 19th June, 11:30 pm". So, the judge got a bit confused about my confession. So, I began to tell them, "The time the murder was happened, is not a valid time according to you. So, how can you claim that I am the murderer?"

And what happened next, you all know. I am in the streets again with a clean sheet.

But now I have planned to kill again. I have a list of N mosquitoes which are to be killed. But there is a small problem. If I kill a mosquito, all of his friends will be informed, so they will be prepared for my attack, thus they will be impossible to kill. But there is a surprising fact. That is if I denote them as a node and their friendship relations as edges, the graph becomes acyclic.

Now I am planning when and how to kill them (how to get rid of the law!) and you have to write a program that will help me to find the maximum number of mosquito I can kill. Don't worry too much, if anything goes wrong I will not mention your name, trust me!

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

Each case starts with a blank line and two integers N (1 ≤ N ≤ 1000) denoting the number of mosquito I want to kill and M denoting the number of friendship configurations. Each of the next M lines contains two integers a and b denoting that ath and bth mosquitoes are friends. You can assume that (1 ≤ a, b ≤ N, a ≠ b) and each friendship relation is given only once. As I have already mentioned, you will not find any cycle in the relations.

Output For each case, print the case number and the maximum number of mosquitoes I can kill considering the conditions described above.

Sample input output here: http://paste.ubuntu.com/8171545/