By RAD, 11 years ago, translation, Welcome to Codeforces Beta Round #25 (Div. 2)

Authors of today's round problems are Mike Mirzayanov and me. I want to thank to Dmitry Levshunov for technical assistance in organizing the contest, as well as Gerald Agapov and Nikolay Kuznetsov for writing alternative solutions.

I wish you all good luck!

UPD: The contest is over, thank you to everyone for participating. Announcement of Codeforces Beta Round #25 (Div. 2 Only)  Comments (56)
 i write a code for problem B but when i wanna submit it doesn t going to go accept.....and say "Idleness limit exceeded on test 1"..what sahould i do????????????????i run this program correctly
•  Or it's just another Time Limit answer?
 I get "Presentation error on test 10". Please explain it!
 FAQ really needs a link from main page. The amount of failed submissions because of %lld %I64d issue is huge.
•  Even better, why not just scan incoming source code that tries to scanf a long long and immediately print out that they're making a mistake (with no penalty)? So many WAs could be saved this way... :P
•  Aaargh, problem C, WA#38!.. Well, but why does my gcc-4.4.3 work with "%lld" just fine?
•  put long longsorry for my bad English
 Any ideas for problem C?
•  If query cost is less then current cost then enumerate every pair of verticies and try to update cost betwenthem like if the shotest path go through according edge. So update cost for any query is O(N^2)
•  Let (u, v) be a new road with length d.First, see if this new road is actually better than the shortest path from u to v. It may not be :)Assuming it's an improvement, set a[u][v] = a[v][u] = d. Then, run Floyd-Warshall to update the shortest distances. Normally this would be O(n^3), but because only the distance between u and v changed, it suffices to use only u and v as midpoints, reducing the time to O(n^2). Given 300 roads, the total runtime is 300 * O(n^2) ~= 300^3 which is quite fine.
•  The one really mean thing to watch out for is that you need to use a 64-bit integer to hold the output.
 Marek, welcome to codeforces
•  Hello Egor :)
 I got a PE for problem D!!!!  Is there something wrong with the judge?
•  I've got PE on 8 test, and you?
•  Maybe you don't output line breaks?
•  when I correct : if (col = Used[i1]) on : if (col == Used[i1]) I get AC(((stupid bug((ЗЫ: интересно, какая разница между = и ==?
•  "=" means assignment, so your expression can be written this way:col = Used[i1];if (col ){...}
•  if (col = Used[i1]) { ... }col will equal Used[i1]  and thereafter expression will true if col not equal zero
•  thX
•  There are no special cases for PE in this problem. You can get PE if you either output not an integer or output city index that violates range [1, n] or your number of days is negative.
 Is there any way to see test case 8 for problem D? It cries "presentation error" everytime and I've ran out of ideas what to do.
•  Test 8 in problem D:10 5 9 8 5 7 6 7 9 3 9 2 1 7 2 3 6 7 1
•  Thank you!! :) Found the error :)
•  Just wondering, what was the problem?
•  One of the problems was that I didn't erase the edge from the graph after deleting the road, the second was I re-colared the components in the wrong way. Something still isn't working though now I'm getting presentation error on case 10 :S.
•  Thank you!
•  thank you !
 i also got presentation error in test case 8..
 In problem C, I think that road length over 1000. The following code is runtime error on test 4.const int N = 310;int main() {  int n;  scanf("%d", &n);  int g[N][N];  for (int i = 1; i <= n; i++)    for (int j = 1; j <= n; j++) {      scanf("%d", &g[i][j]);      assert(g[i][j] <= 1000); // runtime error...    }}
•  Elements of g may be more then 1000, because they are not lengths of edges but lengths of minimal paths
•  Thank you, egor. I understand.
 Is it also possible to get test case 10? :)
•  39 6 13 15 39 10 35 31 28 4 21 12 39 3 7 3 13 6 1 5 14 36 28 12 15 18 38 30 29 19 34 36 16 20 22 8 13 38 32 26 39 21 37 1 7 15 27 12 26 8 3 6 14 29 2 25 23 32 21 5 16 32 25 6 8 13 10 23 30 34 37 29 33 28 14 36 5
 Can somebody tell me the maximum range for integer(int) in gnu c++. I got WA for problem C,but when i submitted using long long it accepts. But the sum could be as maximum 9*10^7. that could be in 32 bit integer!!!!sorry for my poor english.
•  no.each edge on the original graph can be at most 1000.So, the maximum value of an element in the shortest path matrix is 9*10^7, as you said.So, the sum of the elements may be greater than the integer range ( ~[-2^31, 2^31], if I am not mistaken )hope it helps.
•  Maximum value is 3*10^5, but there is about 45000 elemnts
•  The total number of elements are 45000,that is ok,but you are telling that the maximum value is 3*10^5 for each element..I don't know how,because the given matrix it is not the edges from i to j, it is the shortest distance from i to j and it is within 1-1000,so the sum cannot be more than 4.5*10^7. i am confused :(
•  Shortest distance from i to j may be up to 299 * 1000 - for example if graph is path with 300 verticies and each edge costs 1000
•  sorry, i found my mistake, i"a given matrix is a matrix of shortest distances for some set of two-way roads with integer lengths from 1 to 1000, such that from each city it is possible to get to any other city using these roads." i misunderstood the last part.
 i'm getting WA in testcase 26 in problem E. is there some trick in this testcase?and if it is a small testcase (post-able) i'd be really grateful if anyone can post it.
•  I get Time limit exceeded in test 26. After some optimizations result was the same. Can anybody help with this problem?
•  The 26th test:The first string consists of 92235 letters. Letter in position 81200 (1-based) is 'z', the others are 't'.The second string consists of 68546 letters. Letter in position 40450 (1-based) is 'z', the others are 't'.The third string consists of 92026 letters 't'.The answer is 120123
•  thanks a lot :)
•  Thanks!
 Is the problem E solvable by KMP? I'm getting WA on test 44. But, I don't know if I have some bugs in my program or I'm taking a wrong approach.Thanks
•  using KMP is a correct approach.
•  The 44th test is some big random test, every string contains letters 't' and 'y' only.
•  Robin karp can also make it.But it is a little bit slow.
•  Thanks =), I will try to find the bugs
 How can I solve problem E? What is the algorithm or approach to solve this problem? Can any one give me some material or link to solve this problem?Thanks in advance :).
 You should learn about KMP, if you don't already know it.http://en.wikipedia.org/wiki/Knuth%E2%80%93Morris%E2%80%93Pratt_algorithmUsing KMP, it's easy to find for 2 given strings the longest suffix of the first one that is a prefix for the second one.After that you simply try all posible permutations of the 3 strings given in the problem(watching for degenerate cases, when one of the strings is a substring of one of the other two..).
•  Thanks a lot :)
 Hi ! Can somebody tell me that when is the next Contest ????????Thanks