Codeforces celebrates 10 years! We are pleased to announce the crowdfunding-campaign. Congratulate us by the link https://codeforces.com/10years. ×

By RAD, 10 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.

• +35

 10 years ago, # |   0 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
•  10 years ago, # ^ |   0 Or it's just another Time Limit answer?
 10 years ago, # |   0 I get "Presentation error on test 10". Please explain it!
 10 years ago, # |   +4 FAQ really needs a link from main page. The amount of failed submissions because of %lld %I64d issue is huge.
•  10 years ago, # ^ |   0 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
•  10 years ago, # ^ |   +1 Aaargh, problem C, WA#38!.. Well, but why does my gcc-4.4.3 work with "%lld" just fine?
•  10 years ago, # ^ |   0 put long longsorry for my bad English
 10 years ago, # |   0 Any ideas for problem C?
•  10 years ago, # ^ |   0 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)
•  10 years ago, # ^ |   0 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.
•  10 years ago, # ^ |   0 The one really mean thing to watch out for is that you need to use a 64-bit integer to hold the output.
 10 years ago, # |   +14 Marek, welcome to codeforces
•  10 years ago, # ^ |   +8 Hello Egor :)
 10 years ago, # |   0 I got a PE for problem D!!!!  Is there something wrong with the judge?
•  10 years ago, # ^ |   +12 I've got PE on 8 test, and you?
•  10 years ago, # ^ |   0 Maybe you don't output line breaks?
•  10 years ago, # ^ |   0 when I correct : if (col = Used[i1]) on : if (col == Used[i1]) I get AC(((stupid bug((ЗЫ: интересно, какая разница между = и ==?
•  10 years ago, # ^ |   0 "=" means assignment, so your expression can be written this way:col = Used[i1];if (col ){...}
•  10 years ago, # ^ |   0 if (col = Used[i1]) { ... }col will equal Used[i1]  and thereafter expression will true if col not equal zero
•  10 years ago, # ^ |   0 thX
•  10 years ago, # ^ |   +1 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.
 10 years ago, # |   0 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.
•  10 years ago, # ^ |   0 Test 8 in problem D:10 5 9 8 5 7 6 7 9 3 9 2 1 7 2 3 6 7 1
•  10 years ago, # ^ |   0 Thank you!! :) Found the error :)
•  10 years ago, # ^ |   0 Just wondering, what was the problem?
•  10 years ago, # ^ |   0 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.
•  10 years ago, # ^ |   0 Thank you!
•  7 months ago, # ^ |   0 thank you !
 10 years ago, # |   0 i also got presentation error in test case 8..
 10 years ago, # |   0 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...    }}
•  10 years ago, # ^ |   +5 Elements of g may be more then 1000, because they are not lengths of edges but lengths of minimal paths
•  10 years ago, # ^ |   0 Thank you, egor. I understand.
 10 years ago, # |   0 Is it also possible to get test case 10? :)
•  10 years ago, # ^ |   0 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
 10 years ago, # |   0 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.
•  10 years ago, # ^ |   0 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.
•  10 years ago, # ^ |   0 Maximum value is 3*10^5, but there is about 45000 elemnts
•  10 years ago, # ^ |   0 my bad!
•  10 years ago, # ^ |   0 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 :(
•  10 years ago, # ^ |   0 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
•  10 years ago, # ^ |   0 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.
 10 years ago, # |   0 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.
•  10 years ago, # ^ |   0 I get Time limit exceeded in test 26. After some optimizations result was the same. Can anybody help with this problem?
•  10 years ago, # ^ |   0 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
•  10 years ago, # ^ |   0 thanks a lot :)
•  10 years ago, # ^ |   0 Thanks!
 10 years ago, # |   +1 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
•  10 years ago, # ^ |   +1 using KMP is a correct approach.
•  10 years ago, # ^ |   0 The 44th test is some big random test, every string contains letters 't' and 'y' only.
•  10 years ago, # ^ |   0 Robin karp can also make it.But it is a little bit slow.
•  10 years ago, # ^ |   0 Thanks =), I will try to find the bugs
 10 years ago, # |   0 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 :).
 10 years ago, # |   0 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..).
•  10 years ago, # ^ |   0 Thanks a lot :)
 10 years ago, # |   0 Hi ! Can somebody tell me that when is the next Contest ????????Thanks