galen_colin's blog

By galen_colin, 5 months ago, In English
A1
A2
B
C
D
E

Some notes/backstory about the round in general:

  • Sorry about the mistake in C! I hope it didn't affect you too much, if at all. You can blame this on my bad organization — a tester did actually catch this mistake, but somehow I forgot to correct it.
  • The only tester feedback I received besides corrections was to swap the problems C and D. Based on the solve counts, I guess it worked out.
  • A lot of people received WA17 or WA20 on D because of not making the default values in the array small enough. With $$$0$$$ as the default, you'd get WA17. Others, who used $$$-10^9$$$ or $$$-10^{10}$$$, got WA20. I actually made this mistake myself, and my brute-force didn't catch it because it only seemed to happen with large enough $$$n, k$$$.
  • I was skeptical about placing E at the end because of how simple the solution was, but that seems like it was a good choice now.
  • I understand criticism about the problems being too "standard" — in fact, I'm not really proud of having a problem like D, but I thought it was necessary for balance (turns out it wasn't anyway). At the very least, they could serve to teach people new algorithms.
Tutorial of Testing Round #XVII
 
 
 
 
  • Vote: I like it
  • +33
  • Vote: I do not like it

»
5 months ago, # |
  Vote: I like it +15 Vote: I do not like it

There is another solution for 102646A2 - Product of Triples (Hard Version)

Iterate $$$x$$$ over all numbers from $$$[1,n]$$$

For each number $$$x$$$, fix $$$i$$$ to be one of the divisors of the number $$$x$$$.

Calculate $$$y$$$ = $$$x/i$$$, now iterate $$$z$$$ over all divisors of $$$y$$$. The three numbers would be $$$i$$$, $$$z$$$, $$$y/z$$$. Just check for the $$$a≤b≤c$$$ and count them !

»
5 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Can someone explain task C? Explaining the output of the Sample TC is enough!

»
6 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

galen_colin

can any one tell me why WA in this problem https://codeforces.com/gym/102646/problem/E my code ---> https://ideone.com/yB1W29 my idea is to search about sccs inside the graph then remove all edges from this scc and so on till remains k edges

  • »
    »
    6 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    The entire input graph is already strongly connected. So removing edges from this isn't guaranteed to work, and is essentially equivalent to removing $$$m - k$$$ random edges, which has no guarantee of producing the maximum number of SCCs.