dalex's blog

By dalex, 3 years ago, translation, In English,

Hello everyone,

Some days ago there was an annual programming contest in Samara University, and yet again we copy it into Codeforces Gyms. The gym contest takes place on Saturday, 8 April, at 9:30 MSK. Site clist.by says that there are no intersections with something important that day.

Second time in a row it is a personal contest. So we ask everyone to participate solo. It must be very interesting for yellow and lower guys, and, who knows, maybe for reds too. You can start virtual participation at any time.

And as usual,

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

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Carry on!

»
2 years ago, # |
  Vote: I like it +3 Vote: I do not like it

Finally, I have some time to write an editorial.

A
B
C
D
E
F
G
H
I
J
K
L
M
  • »
    »
    2 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Can you please explain the linear algebra part for the Matrix God problem.

    • »
      »
      »
      11 months ago, # ^ |
        Vote: I like it +18 Vote: I do not like it

      If we want to check whether A x B = C, we can check whether A x (B x T) = (C x T). (*)

      The multiplication of two matrices of size (n x m) and (m x k) produces a matrix of size (n x k). Let T be a matrix of size (n x 1). Following that property, (C x T) is a matrix of size (n x 1). Since (B x T) is a matrix of size (n x 1), (A x (B x T)) will be a matrix of size (n x 1) as well.

      Comparing two (n x 1) matrices takes O(n) time. Hence we can try randomizing T and check whether (*) is correct. Obviously, we want to check (*) with different T's as many times as possible.

      The total time complexity is O(n^2 * number of checks). Hence, to fit the time limit, you have to choose an appropriate number of checks.