RAD's blog

Codeforces Beta Round #25 (Див. 2)
By RAD, 14 years ago, translation, In English

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.

  • Vote: I like it
  • +35
  • Vote: I do not like it

Comments Comments (47)
| Write comment?
14 years ago, # |
  Vote: I like it 0 Vote: I do not like it
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
→ Reply
  • 14 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    May be this is about UNUSED CODE?
    I'm also very interested about this verdict.
    → Reply
  • 14 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    Or it's just another Time Limit answer?
    → Reply
14 years ago, # |
  Vote: I like it +4 Vote: I do not like it
FAQ really needs a link from main page. The amount of failed submissions because of %lld %I64d issue is huge.
→ Reply
  • 14 years ago, # ^ |
      Vote: I like it +1 Vote: I do not like it
    Aaargh, problem C, WA#38!..
    Well, but why does my gcc-4.4.3 work with "%lld" just fine?
    → Reply
14 years ago, # |
  Vote: I like it 0 Vote: I do not like it
Any ideas for problem C?
→ Reply
  • 14 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    If query cost is less then current cost then enumerate every pair of verticies and try to update cost betwen
    them like if the shotest path go through according edge. So update cost for any query is O(N^2)
    → Reply
  • 14 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    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.
    → Reply
  • 14 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    The one really mean thing to watch out for is that you need to use a 64-bit integer to hold the output.
    → Reply
14 years ago, # |
  Vote: I like it +14 Vote: I do not like it
Marek, welcome to codeforces
→ Reply
14 years ago, # |
  Vote: I like it 0 Vote: I do not like it

I got a PE for problem D!!!!  Is there something wrong with the judge? 

→ Reply
  • 14 years ago, # ^ |
      Vote: I like it +12 Vote: I do not like it
    I've got PE on 8 test, and you?
    → Reply
    • 14 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it
      Maybe you don't output line breaks?
      → Reply
      • 14 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it
        when I correct : if (col = Used[i1]) 
        on : if (col == Used[i1]) 
        I get AC(((
        stupid bug((

        ЗЫ: интересно, какая разница между = и ==?


        → Reply
        • 14 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          "=" means assignment, so your expression can be written this way:

          col = Used[i1];

          if (col ){...}

          → Reply
          • 14 years ago, # ^ |
              Vote: I like it 0 Vote: I do not like it
            if (col = Used[i1]) { ... }

            col will equal Used[i1]  and thereafter
            expression will true if col not equal zero
            → Reply
  • 14 years ago, # ^ |
      Vote: I like it +1 Vote: I do not like it
    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.
    → Reply
14 years ago, # |
  Vote: I like it 0 Vote: I do not like it
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.
→ Reply
  • 14 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    Test 8 in problem D:
    10
5 9
8 5
7 6
7 9
3 9
2 1
7 2
3 6
7 1
    → Reply
    • 14 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it
      Thank you!! :) Found the error :)
      → Reply
      • 14 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it
        Just wondering, what was the problem?
        → Reply
        • 14 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it
          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.
          → Reply
    • 5 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      thank you !

      → Reply
14 years ago, # |
  Vote: I like it 0 Vote: I do not like it
i also got presentation error in test case 8..
→ Reply
14 years ago, # |
  Vote: I like it 0 Vote: I do not like it
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...
    }
}
→ Reply
  • 14 years ago, # ^ |
      Vote: I like it +5 Vote: I do not like it
    Elements of g may be more then 1000, because they are not lengths of edges but lengths of minimal paths
    → Reply
14 years ago, # |
  Vote: I like it 0 Vote: I do not like it
Is it also possible to get test case 10? :)
→ Reply
  • 14 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it 
    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
    → Reply
14 years ago, # |
  Vote: I like it 0 Vote: I do not like it
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.
→ Reply
  • 14 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    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.
    → Reply
    • 14 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it
      Maximum value is 3*10^5, but there is about 45000 elemnts
      → Reply
      • 14 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it
        my bad!
        → Reply
      • 14 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it
        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 :(
        → Reply
        • 14 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it
          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
          → Reply
        • 14 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it
          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.  
          → Reply
14 years ago, # |
  Vote: I like it 0 Vote: I do not like it
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.
→ Reply
  • 14 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    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
    → Reply
14 years ago, # |
  Vote: I like it +1 Vote: I do not like it
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
→ Reply
  • 14 years ago, # ^ |
      Vote: I like it +1 Vote: I do not like it
    using KMP is a correct approach.
    → Reply
  • 14 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    The 44th test is some big random test, every string contains letters 't' and 'y' only.
    → Reply
  • 14 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    Robin karp can also make it.But it is a little bit slow.
    → Reply
  • 14 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    Thanks =), I will try to find the bugs
    → Reply
14 years ago, # |
  Vote: I like it 0 Vote: I do not like it
You should learn about KMP, if you don't already know it.
http://en.wikipedia.org/wiki/Knuth%E2%80%93Morris%E2%80%93Pratt_algorithm
Using 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..).
→ Reply