majk's blog

By majk, 5 years ago,
• +178

| Write comment?
 » 5 years ago, # |   +62 It was hard to see that D can't be solved with Rho, and I've seen a problem like G before (so I knew what ifs are needed). Other than that, nice problems! E was very very cool.
•  » » 5 years ago, # ^ |   +25 Thanks!I was worried that D would be solvable by Rho, but tests suggested that it just wasn't. It's difficult to rely on algorithm with unproved complexity.
•  » » » 5 years ago, # ^ |   +9 Random question from a person who's not an expert in fancy factorization algorithms: can we get stuff done by using something more advanced than algorithms typically used in competitive programming (like it has been indirectly suggested in this comment), and if we can — do you have any information about contestants actually doing so? Was it a popular approach or not? :)
•  » » » » 5 years ago, # ^ |   +24 We can use Shank's SQUFOF. It factors N in around O(N1 / 4), but its main advantage is that SQUFOF doesn't need 128-bit multiplication and uses only 32-bit integers for the most part. I don't fully understand the algorithm and the implementation needs quite a few tricks to even work at all, but it is really fast, passing in 62 ms.
•  » » » » » 5 years ago, # ^ |   +4 Please don't do that. I would have to set ai ≤ 10100 next time :)
•  » » » 5 years ago, # ^ | ← Rev. 2 →   +29 Personally, I thought the bad performance of Rho is due to the huge amount of calls to gcd function, which may cause the time complexity to become . However, it can be optimized if you adjust that to call gcd function once during a considerable period. Besides, a fast algorithm for modular multiplication such as Montgomery Modular Multiplication may help a lot.Maybe an accepted solution of Rho: 43964647
•  » » 5 years ago, # ^ |   +3 I wish u gonna discuss those in next live stream.
 » 5 years ago, # |   0 When will the problems be available in practice
•  » » 5 years ago, # ^ |   0 Shortly after system test finishes.
 » 5 years ago, # |   +64 Why did you cut the limit to 20000 on E? Is it because of the time limits or are you afraid that some solutions with bad asymptotic could pass? To me, i think that it would be cool if solutions with correct asymptotic and bad constants could pass too.
•  » » 5 years ago, # ^ |   +50 To me solution described in editorial sounds like the one having bad constant :)One can find a spanning tree by running DFS from any vertex. We can implement a function "find if there is an edge from v to unused vertex" using trick from the first paragraph, but with only 2 queries instead of 3 (your set A consists of single vertex, so you know that e(A) is equal to 0). Now let's wrap it with binary search: first you check that at least one edge exists (asking it against whole set of unused vertices), and then you can bisect with one call of our function instead of two: split your set into two parts and check if there is a good edge in one of them; if it is not there, we know for sure that it is in the other part. It means that we'll do roughly N * log(N) + N calls of helper function, and each such call is 2 interactive queries. Therefore we can estimate that we are somewhere at 12-13k queries worst case (sorry, I'm lazy to actually calculate it precisely), which is significantly better than 20k.So this problem actually doesn't look bad in terms of constants; it is way better than typical "You are allowed to perform at most 73 queries (so now you know how many queries model solution will need)".
•  » » » 5 years ago, # ^ |   0 One can do bipartite check using the same idea; then, caching is not needed at all. The solution passes all tests with ~11k queries.
 » 5 years ago, # |   +17 thank you very much for this contest it was very good but i solved ( b ) problem only i wish to be good in the future like you and other professional contestant
 » 5 years ago, # |   0 Nice Contest this!!!!
 » 5 years ago, # |   0 My Solution of problem D couldn't able to pass the sys-test as I have used Shanks's square forms factorization to get one prime p from the form p*q. It returns wrong output for the number 1184554290421768229. Can anyone enlighten me about this bug? Actually I have copied the exact code from wiki for this algorithm and it produces wrong output. So is it happening because of the code or the algorithm itself has some bugs?
•  » » 5 years ago, # ^ |   0 You get a runtime error. Perhaps some undefined behaviour in your code? If you resubmit with "Clang diagnostics" compiler, you might get some more information.
•  » » » 5 years ago, # ^ |   0 Actually, the Shanks algorithm is producing 0 even if it is taking a semiprime as an input. I think the algorithm has some bug in it. I am not using it anymore in future or if you have some better implementation of this algorithm I could use that in the future.
•  » » » » 5 years ago, # ^ |   +13 Your code has a few issues. Squfof doesn't handle small factors well, so it's a good idea to run trial division up to ~5000 first. (Your code fails on 177967104912459682 = 2·88983552456229841and 388444698056365523 = 67·5797682060542769for example). You seem to find a lot of trivial factors. I'd suggest you to take a look at the Squfof implementation of msieve here, mainly for the part with coarse_cutoff and cutoff (Just note that the msieve code fails for n = p3.). My implementation is based on that code and the cutoff part makes a huge difference. (Your code fails on 422497460091096893 = 481512587·877438039 and 51104449379303477 = 656561·77836559557.) In my code, I also dynamically increase the iteration limit, but I'm not sure if thats needed. You can find my practice submission here, but be warned: The code is ugly, I was learning templates at the time I wrote it. (On the other hand, it is really fast: 62 ms.) Here's the code I used to generate the above test cases (I ran it with T ≈ 15'000). Generator codeimport random as rng # next_prime function from https://codegolf.stackexchange.com/questions/10701/fastest-code-to-find-the-next-prime/10702#10702 # legendre symbol (a|m) # note: returns m-1 if a is a non-residue, instead of -1 def legendre(a, m): return pow(a, (m-1) >> 1, m) # strong probable prime def is_sprp(n, b=2): d = n-1 s = 0 while d&1 == 0: s += 1 d >>= 1 x = pow(b, d, n) if x == 1 or x == n-1: return True for r in range(1, s): x = (x * x)%n if x == 1: return False elif x == n-1: return True return False # lucas probable prime # assumes D = 1 (mod 4), (D|n) = -1 def is_lucas_prp(n, D): P = 1 Q = (1-D) >> 2 # n+1 = 2**r*s where s is odd s = n+1 r = 0 while s&1 == 0: r += 1 s >>= 1 # calculate the bit reversal of (odd) s # e.g. 19 (10011) <=> 25 (11001) t = 0 while s > 0: if s&1: t += 1 s -= 1 else: t <<= 1 s >>= 1 # use the same bit reversal process to calculate the sth Lucas number # keep track of q = Q**n as we go U = 0 V = 2 q = 1 # mod_inv(2, n) inv_2 = (n+1) >> 1 while t > 0: if t&1 == 1: # U, V of n+1 U, V = ((U + V) * inv_2)%n, ((D*U + V) * inv_2)%n q = (q * Q)%n t -= 1 else: # U, V of n*2 U, V = (U * V)%n, (V * V - 2 * q)%n q = (q * q)%n t >>= 1 # double s until we have the 2**r*sth Lucas number while r > 0: U, V = (U * V)%n, (V * V - 2 * q)%n q = (q * q)%n r -= 1 # primality check # if n is prime, n divides the n+1st Lucas number, given the assumptions return U == 0 # primes less than 212 small_primes = set([ 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97,101,103,107,109,113, 127,131,137,139,149,151,157,163,167,173, 179,181,191,193,197,199,211]) # pre-calced sieve of eratosthenes for n = 2, 3, 5, 7 indices = [ 1, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97,101,103,107,109,113,121,127,131, 137,139,143,149,151,157,163,167,169,173, 179,181,187,191,193,197,199,209] # distances between sieve values offsets = [ 10, 2, 4, 2, 4, 6, 2, 6, 4, 2, 4, 6, 6, 2, 6, 4, 2, 6, 4, 6, 8, 4, 2, 4, 2, 4, 8, 6, 4, 6, 2, 4, 6, 2, 6, 6, 4, 2, 4, 6, 2, 6, 4, 2, 4, 2,10, 2] max_int = 2147483647 # an 'almost certain' primality check def is_prime(n): if n < 212: return n in small_primes for p in small_primes: if n%p == 0: return False # if n is a 32-bit integer, perform full trial division if n <= max_int: i = 211 while i*i < n: for o in offsets: i += o if n%i == 0: return False return True # Baillie-PSW # this is technically a probabalistic test, but there are no known pseudoprimes if not is_sprp(n): return False a = 5 s = 2 while legendre(a, n) != n-1: s = -s a = s-a return is_lucas_prp(n, a) # next prime strictly larger than n def next_prime(n): if n < 2: return 2 # first odd larger than n n = (n + 1) | 1 if n < 212: while True: if n in small_primes: return n n += 2 # find our position in the sieve rotation via binary search x = int(n%210) s = 0 e = 47 m = 24 while m != e: if indices[m] < x: s = m m = (s + e + 1) >> 1 else: e = m m = (s + e) >> 1 i = int(n + (indices[m] - x)) # adjust offsets offs = offsets[m:]+offsets[:m] while True: for o in offs: if is_prime(i): return i i += o rng.seed(123932) T = int(input()) print(T) for _ in range(T): #a = rng.randint(1, 100) #b = rng.randint(10**15, 10**16) #a = rng.randint(1000, 2000) #b = rng.randint(10**13, 10**14) a = rng.randint(10**5, 10**6) b = rng.randint(10**9, 10**11) print(next_prime(a) * next_prime(b)) 
•  » » » » » 5 years ago, # ^ |   0 Thanks for your reply. I have learnt so many things from you today. And I will use your code in future for factorizing large numbers and that cool SQUFOF algorithm. And again, thanks.
 » 5 years ago, # |   0 In problem C , can any one tell me what's wrong on my approach ? why does it give wrong answer on Test 23 ?http://codeforces.com/contest/1033/submission/43970251
•  » » 5 years ago, # ^ |   0 I solved it with DP , states are , Current State is to pick the optimal choice depends on transitions (For example :- currentTurn for Alice , Alice must search for any odd moves to Win and Bob must search for even moves to Win )
 » 5 years ago, # |   0 Related to D: what about pq^2, p^2q and p^2q^2 forms?
•  » » 5 years ago, # ^ |   +3 pq2 has six divisors (1, p, q, pq, q2 and pq2), so it cannot be part of the input.
•  » » » 5 years ago, # ^ |   +12  .-'----. ,' . | \ | \ \ _ \ ,\ _ ,'-,/-)\ ( * \ \,' ,' ,'-) ._,) -',-') \/ ''/ ) / / / ,'-' Thanks.
 » 5 years ago, # |   +26 How did you implement the interactor in E? What is the complexity of answering each query? I cannot see any method better than the naive O(n2) per query which will simply TLE.
•  » » 5 years ago, # ^ | ← Rev. 2 →   +28 I think optimizing the intersection count with bitset should be enough.
•  » » » 5 years ago, # ^ |   +5 + bitset. It is the reason why the time limit is so high.
•  » » » 5 years ago, # ^ |   0 can you please elaborate a little?
•  » » » » 5 years ago, # ^ |   +20 Refer to the interactor. interactor.cpp#include "testlib.h" #include #include constexpr int MAXN = 600; constexpr int MAXQ = 20000; using namespace std; int main(int argc, char ** argv){ registerInteraction(argc, argv); int n = inf.readInt(); int m = inf.readInt(); vector> E(n); for (int i = 0; i < m; i++) { int u = inf.readInt(); int v = inf.readInt(); --u; --v; E[u].set(v); E[v].set(u); } cout << n << endl; cout.flush(); for (int q = 1; q <= MAXQ + 1; ++q) { string S = ouf.readToken(); if (S == "?") { if (q > MAXQ) { cout << "-1\n"; quitf(_wa, "too many queries"); } bitset F; int k = ouf.readInt(); if (k < 1 || k > n) { cout << "-1\n"; quitf(_wa, "query %d: k=%d out of range", q, k); } for (int j = 0; j < k; j++) { int b = ouf.readInt(); if (b < 1 || b > n) { cout << "-1\n"; quitf(_wa, "query %d: v[%d]=%d out of range", q, j+1, k); } if (F[b-1]) { cout << "-1\n"; quitf(_wa, "query %d: vertex %d appears twice", q, b); } F.set(b-1); } int ans = 0; for (int i = 0; i < n; i++) if (F[i]) ans += (E[i]&F).count(); cout << ans/2 << endl; cout.flush(); } else if (S == "N" || S == "Y") { int r = ouf.readInt(); if (r < 0 || r > n) { cout << "-1\n"; quitf(_wa, "answer %d out of range", r); } tout << S << ' ' << r << '\n'; for (int i = 0; i < r; i++) { int v = ouf.readInt(); if (v < 1 || v > n) { cout << "-1\n"; quitf(_wa, "a[%d]=%d out of range", i+1, v); } tout << v << " \n"[i==r-1]; } tout << q-1 << endl; quitf(_ok, "answer returned"); } else { cout << "-1\n"; quitf(_wa, "invalid query"); } } }  inf is a stream reading from the file describing the test case (i.e. a graph) cout is an output stream towards the solution (this is the input you're reading from) ouf is an input stream towards the solution (this is the output you're printing) tout is the log written by the interactor. Afterwards, it is fed to the checker. E is the adjacency matrix F is the bitset representing the query
•  » » » » » 5 years ago, # ^ |   0 thanks for the reply! Can you please also answer this or provide an implementation based on the editorial.
 » 5 years ago, # |   0 Can anyone explain me problem C ?
•  » » 5 years ago, # ^ |   0 I'll try to explain my approach for the problem. It makes use of game theory. Game theory states that "if I am currently at X, and if I can move to states Y1, Y2 .. YK, if each of the state Y1, Y2 .. YK are winning states for me(i.e., if I would win the game if I was at Y1 or Y2 or YK..), then X is a losing state for me. If any one of Y1 or Y2 or .. YK was a losing state for me, then X is a winning state for me. Fill an array with values 1 if Alice has a winning position if she starts at i, else 0. So we can just fill the array from N to 1. for each value, go to all possible states where she can move next ( I — I, I — 2I, I — 3I , I+I, I+2I etc.) and check if any of those had values 0. If yes, I is a winning state for us. Else, I is a losing state. Complexity should be similar to that of Sieve, i.e, N * log (N) Code: 44012560
•  » » » 2 years ago, # ^ |   0 Can you explain the time complexity , why it is nlog(n)
 » 5 years ago, # |   +10 The second approach of F can be implemented in O(n + 3w + m·2w) time.
 » 5 years ago, # |   +6 Hello. I have been trying Problem D with the same approach as above,but getting WA on test case 15. Can someone help me out?? Here's the link: https://codeforces.com/contest/1033/submission/43976266
•  » » 5 years ago, # ^ |   +3 It is due to errors in accuracy. I got WA on the same test case and I therefore had to check within +-1 of the obtained sqrt (and for other powers too). For example I guess sometimes when the actual sqrt is say 100000, the sqrt function in c++ might return 99999.999 and since this gets rounded down, you lose out on accuracy. I hope you got the point.
•  » » » 5 years ago, # ^ |   0 Thank You.It worked!!
•  » » » 5 years ago, # ^ |   0 can we trust on pow(n,0.5) instead of sqrt(n) ? or we have to make our own function for calculating powers ?
•  » » » » 5 years ago, # ^ |   +3 I replaced sqrt with sqrtl and cbrt with cbrtl and my solution got Accepted.
•  » » » » » 5 years ago, # ^ |   +21 I replaced sqrt with sqrtl
•  » » » » » » 5 years ago, # ^ |   0 facepalm btw you replaced sqrt with sqrt(sqrtl)
 » 5 years ago, # | ← Rev. 2 →   0 In problem E can someone please help me to optimize my solution? I did the same as mentioned in editorial.
•  » » 5 years ago, # ^ |   0 can someone please give link to the code of the solution mentioned in the editorial.
 » 5 years ago, # |   +18 In Problem F, the complexity O(w·3w) in one step is O(3w) in fact.When we calculate f(i, s, t): how many number satisfying that first i bits are equal to s, and last w - i bits matches t (, ), the total complexity is In Problem G, we only need to split the number into 2 parts: and , and then get the maximum number of the first part, the size, the maximum two numbers and the minimum number of the second part, then discuss some cases like the editiorial. It can get rid of the log factor.
 » 5 years ago, # |   0 in B , i am doing in O(sqrt(a+b)) time approx 10^5 operations ,but gives tle why??
•  » » 5 years ago, # ^ |   0 The line to blame isfor(int i=2;i*i<=a ;i++)Since int is 32-bit, you have an overflow when computing i*i`. If a is larger than 231 (which it can be), the condition is always true, hence the infinite loop.
•  » » » 5 years ago, # ^ | ← Rev. 2 →   0 i got it ..thanku so much..
•  » » » » 5 years ago, # ^ |   -32 please suggest me some ways how to practice competitive problems so that i can do D or E level problems..refer any link or share the way you did in beginning..
•  » » » » » 5 years ago, # ^ |   0 Keep solving lots of problems.Solve something just outside of your comfort zone, so you can keep expanding it.If you can't solve something after a lot of effort, read the editorial. Most important is not to just understand the solution, but to reflect on WHY you didn't come up with the solution, and how you could have got that solution if you were to do the problem over again. Make sure that next time you need a similar technique you won't miss it.Keep doing that and you will get better and better over time. There's no easy way but the journey is lots of fun.
 » 5 years ago, # |   0 Hello all, my code gives correct answer for CASE 4 (Problem D) in local machine but here it fails. Can someone help me with this. Link for submission: code
 » 5 years ago, # | ← Rev. 5 →   0 I have a doubt in Problem C Test Case 8:405 40 6 27 39 37 17 34 3 30 28 13 12 8 11 10 31 4 1 16 38 22 29 35 33 23 7 9 24 14 18 26 19 21 15 36 2 20 32 25 ANSWER : ABABBBABABAAAAAABAAABBBBBBAAAABABBABABBBindex = 40 -> ans = Bindex = 10 -> ans = BShouldn't answer for index 10 be A i.e opposite of its reacheable index(i.e 40).
•  » » 5 years ago, # ^ |   0 As 25 < 30, you cannot move the token from 30 to 25. There are thus no valid moves from 30, and Bob wins.
•  » » » 5 years ago, # ^ |   0 Thanks Sir, Finally got a AC. I just overlooked that condition.
 » 3 years ago, # |   0 In problem A queen can move diagonally so there should be 8 components?
•  » » 11 months ago, # ^ |   0 For example, if the queen was on a black square then it would move only along the black squares diagonally. The king can just move to a white square to avoid a checkmate in that direction. Hence, the queen can actually divide the board into only four quadrants(at most) and not eight.
 » 3 years ago, # |   0 Can someone tell at why 77478143 this code is failing. I am using DP with greedy and I am unable to figure out where it is failing.
•  » » 3 years ago, # ^ |   0 for problem C
 » 3 years ago, # | ← Rev. 2 →   0 In problem C, can someone prove that $\sum\limits_{i = 1}^n\lfloor{n/i}\rfloor$ is of order $O(n\log{n})$?
 » 3 years ago, # |   0 Does anyone here has used DFS in 1033A.