Hello.

Recently, I was solving a problem to which I simplified it to evaluating this summation:

C is n choose k. N is up to 1000, and K is up to 2^30.

Answer appears to be I guess {K * (N - 1)^K}

I can't get however how to arrive at this, or perhaps compute the original summation in a smart way, I tried messing expanding nCk to factorials, but didn't get anywhere. <.<

Hello, I was recently solving this problem : http://mirror.codeforces.com/contest/35/problem/E

My solution uses line sweep here : http://mirror.codeforces.com/contest/35/submission/27660692

It gets MLE on the first sample test case + 1200+MS. Now when I run this on custom invocation without reading/writing into file I get :

Used: 15 ms, 4 KB

Is it possible to get past this MLE ? Can someone explain what is going on?

Thanks !

Hello.

Recently I was solving this problem : https://icpcarchive.ecs.baylor.edu/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=2103

Simply the problem says given 12 * n grid of zeros and ones, find the minimum number of swaps to map it to another 12 * n grid where allowed moves are down, up, left and right.

Upon tracing some samples the solution appeared to be minimum cost bipartite matching between non matched ( should be 0 but is 1 or vice versa) one nodes and zero nodes. ( If they are not equal this is impossible). I couldn’t prove correctness so I ran it against a backtracking solution for many small cases, and all passed. Submitted a flow solution and got AC.

Can any body help with proving correctness?

Hello CF !

Can someone recommend MCMF ( Min Cost Maximum flow ) problems from the CF or TC Problem set? Tags don't allow me to find them easily.

I will start the list by adding a nice problem :

http://mirror.codeforces.com/problemset/problem/717/G

Hello CF.

Recently, I was trying to solve this problem : https://community.topcoder.com/stat?c=problem_statement&pm=10469&rd=13749&rm=&cr=22697731.

Please note, this problem doesn't have an editorial. ( It's magically still coming soon even though it's from 2009).

I was constructing a functional graph G where an edge from node i to node j, means that the ith index contains the jth value.

Then, The graph must all of it lie in one cycle ( one SCC ) for the conditions to hold. Otherwise answer ( number of swaps ) is #SSC's — 1. Each component must be linked to another and only one.

The problem however lies in constructing the permutation. I was following an approach that involves greedily merging components starting from the first component that contains zero, but I keep getting WA on a large case.

Any help would be appreciated.

As an attempt to increase my performance and given my passion/love for writing, I’ve decided to create a Quora Blog where I will discuss in details interesting problems which I solve.

Of course for Experienced Competitive Programmers it won’t be helpful, but for people of my level I promise you to find something interesting. I will be solving problems that are harder than my level to begin with. :) I might also make some posts about non popular topics ( i.e. DP D&C Trick — SPD ).

I might not have high rating to get you reading it but I will try to make it challenging/interesting as much as I can. To start with I provided an analysis for the Problem C of the latest round ( 380C ). In future, the problems will be harder. I will aim for 1-2 Blog posts per week.

Link to Post : https://elevencompetingnodes.quora.com/CodeForces-380C

Topcoder SRM 697 starts in around 16 hours, and no blog made yet. So I thought I'd make one.

Timing here

So recently I was in an SRM, and was solving this problem, I will attach an image as it's not posted yet outside the applet. ( If you would like to check in the applet, it's Div1 694 250)

http://imgur.com/sLxbFSV (^There is an option to zoom in).

Each element is between 0 and 255, and size of the array is at most 50.

Solution is Dynamic Programming in O(255*255*51*8).

After the round I got TLE, I thought it was maybe Java TLEing on a max case, but instead it looks like I TLE'd on a case where n = 5 ( lol ) yet my code passes for cases where N is nearly 50. C++ as copy paste from java passes all tests in around 300ms.

Now how can my code be passing cases where N is nearly 50 yet TLE on this one ? It just doesn't make sense...I did run it on my own machine, and it was fine.

A red guy in my room as well couldn't find anything wrong with, and just said it's weird. That's why I'm here CF :).

If this is a max case, I'd try to convince myself that the recursion overhead is too much, but N is just 5..

Incase you would like to have a look at the code, here you go :

https://ideone.com/HuKQK3

It also takes 850ms on CF Servers...

Hello.

In this submission : http://mirror.codeforces.com/contest/682/submission/18657885

I'm getting a TLE verdict, however upon scrolling it says that my output is 27. ( Which is correct for this case).

Is this possibly a bug, or does this occur usually ? How can codeforces get my output if my code did not execute in time ?

Thanks.

Incase any of you would like to view the solutions, they are posted here on YT with discussions. I found this when navigating my YT so thought I'd share on CF.

Problem L : https://www.youtube.com/watch?v=LJtR7bFC8MU

Problem G : https://www.youtube.com/watch?v=-Y9xM_7gVGI

Problem F : https://www.youtube.com/watch?v=MlSByiE2yVU

Problem C : https://www.youtube.com/watch?v=FvppunbosmU

Problem K : https://www.youtube.com/watch?v=sLdzLvAqXxg

Problem D : https://www.youtube.com/watch?v=VP835B2Xb68

Problem B : https://www.youtube.com/watch?v=4xyhMgQnS88

Problem I : https://www.youtube.com/watch?v=3rLiyfvxVr4

Problem A : https://www.youtube.com/watch?v=ls5kkQlQJMA

Problem J : https://www.youtube.com/watch?v=LjXDfSby-G0

Problem E : https://www.youtube.com/watch?v=6-ijK43EkE0

Rest will be updated as they go up.

Link to problem : http://www.codeforces.com/problemset/gymProblem/100499/E

Idea: To solve this problem using a DFS, and maintaining a treap for each node, where it contains it’s corresponding binary-search tree.

Basically, recursively get the best BST of our right child, and best BST of our left child. ( If they exist ).

Ensure that the values added from each child node would not violate our corresponding binary search tree. If they do erase them, and get the best connected sub-tree you can get.

This approach gives a Wrong answer. Even though it’s very convincing.

Me and a friend of mine tried coming up with a test case to fail this but couldn’t find any.

Thanks !

Hello CodeForces!

Recently, I was participating in a gym contest, and came across a very interesting graph problem.

For each vertice of given undirected weighted graph calculate the length of shortest simple cycle, which contains this vertice.

The graph does not contain self loops or multiple edges.

Here it is : http://mirror.codeforces.com/problemset/gymProblem/100917/F

After the contest, I did some googling, but I can only find re-search papers discussing very complex algorithms, I'm pretty sure the author did not intend these solutions.

My solution is as follows :

Let's say edge e connect vertices u and v. Remove edge e from the graph, then re-run dijikstra from u to v. If there exists a path, then there exists a simple cycle containing both u, and v.

Repeat for each edge, and minimise over the shortest cycle for each node.

The idea really makes sense, and the problem is the time limit verdict, how can I solve this problem more efficiently?

Please keep in mind that the graph is un-directed, ( the problem becomes easier in-case it is directed )

Link to the problem : https://uva.onlinejudge.org/index.php?option=onlinejudge&page=show_problem&problem=2740

The approach:

Looks like a shortest path problem, but from possible multiple sources. N is very low so it's sufficient to just use floyd.

First we will create two 2D arrays, dis_brothers[][] and dis_police[][].

dis_brother[][] will include all shortest paths having the "Police" vertex blocked. ( Not relaxing nodes via it by modifying floyd).

dis_police[][] is the normal Floyd, containing all pairs shortest paths.

After we run floyd 2 times, our solution should be :

Iterating through all exits, and minimizing our answer on dis_brothers[brothers][exit]*160 / dis_police[police][exit].

Getting the answer in O(1), it's also possible to use binary search.

The above approach gets WA. Why is this? It works fine with many test cases. It's based on the following idea, we will not approach the edges the police can wait us on, as he can always wait there, after this we take the minimum speed that makes us sure that we are faster on every possible path.

Link to Code : https://ideone.com/jKFfNb

https://uva.onlinejudge.org/index.php?option=onlinejudge&page=show_problem&problem=2482

It asks for the shortest path, yet to get AC you must allow vertices on the graph to be repeated, isn't that contradicting the problem statement itself?

Consider this example :

2
AC
B#

There is no shortest path as you would have to go through 'A' twice, yet the AC solution is 3.

I've the problem accepted, but I want to avoid this confusion in future, why are non distinct vertices allowed in the shortest path in this problem?

Link to problem : http://mirror.codeforces.com/problemset/problem/543/A

DP solution with 501*501*501 memory (MLE but gives correct results when tested on PC) : http://ideone.com/edQhJr

DP solution with 2*501*501 memory ( dimension compressed) : gives WA on sample? : http://ideone.com/YNbwRO

Anyone has an idea why? Thanks.

Yes, I know there is a simple detection algorithm using DFS, but assume for a certain application, I'm interesting in doing via breadth first search traversal, is it possible to do so? I've only seen confirmations about that on quora but without psuedo code or any details.

What is the most efficient way to do so? and if possible, can someone please supply a code? ( A simple short pseudo code is enough).

Thanks.

I have no idea, I find them really the same. I spent quite sometime debugging, but I can't reach anything.

Link to problem : http://www.spoj.com/problems/ACODE/

It's a dp problem.

Link to AC Solution ( C++ ): http://ideone.com/qYpw2x

Link to WA Solution (C++) : http://ideone.com/KxpmuI

If the code is not clear, or the logic. I can add more details.

Thanks.

link to problem : http://uva.onlinejudge.org/index.php?option=onlinejudge&page=show_problem&problem=1301

Link to my solution : https://ideone.com/4rRdS9

I'm basically precomputing the input, and for each cell that lies in x-d<=i && y-d<=j, I'll add it's cost to killed[i][j].

It's a classical problem, if there is anything that's not clear within my code. I'm willing to provide a more detailed explanation.

I estimated the complexity to be N*d^2. Isn't that ok enough for 3 seconds?

Thanks.