By DBradac, history, 4 years ago, , Click to see where the coding begins in your timezone.

We can discuss the problems here after the contest. Comments (52)
 » 4 years ago, # | ← Rev. 2 →   Why the main site isn't working ? UPD : Fixed now
 » How to solve 140?
•  » » 4 years ago, # ^ | ← Rev. 3 →   Edit: wrong algorithm. It's actually possible to end up with a cycle.
•  » » » Not 100% sure but can you explain how your idea works on something like 2 3 6 where it's optimal to choose edge 2-6 and 3-6 wouldn't your idea only consider edge 2-3 instead??
•  » » » » No, I'd incrase cnt 3 times, so 6 would find an edge with 2*3 and cost 0, and then with 3*2 and also cost 0.
 » When the results will be published?
•  » » Currently there is a backlog of submissions waiting to be judged. Results will be published when the submission queue is empty. That will take approximately 1h.
•  » » I think that in less of a half hour, because in the judge, them published this:"Currently there is a backlog of submissions waiting to be judged. Results will be published when the submission queue is empty. That will take approximately 1h."
 » It seems that the problemsetter likes the sieve of Eratosthenes.How to solve the last problem?
•  » » 120 can solved by prime factorization yes?
•  » » » 4 years ago, # ^ | ← Rev. 2 →   Yes. Still no idea why they would put this as a 120-pointer.
•  » » » I used a modified sieve of Eratosthenes:http://paste.dy.fi/ME9
•  » » » » What's the complexity of that algorithm?
•  » » » » » where M = 107
•  » » » » » 3 years ago, # ^ | ← Rev. 5 →   Just decided to elaborate more on it. for (i = 1 .. M) for (j = i .. M, j += i) This works in The sum is known as Harmonic series 1, and it is known that partial sums of these series have a "... logarithmic growth" and "... sum of the first 1043 terms is less than 100".So, you can assume that this works, as pllk said, in . 1 https://en.wikipedia.org/wiki/Harmonic_series_(mathematics) (just copy the link)
•  » » » » » » Pretty cool, thanks for the explanation :D
•  » » My solution is not that fast, but whatever...Calculate DP[i][j] = min cost to make number j to number 1, by i step of operation (no lucky number). This takes O(maxA * lg(maxA) ^ 2) time.for each query from a to b, we use at most one lucky number when making a move. With that observation, we can reduce each Q * M queries as a minimum y-intercept at position L_i, which can be solved with CHT. This whole operation takes O(maxA * lg(maxA)^2 + QM + QT * lg(maxA)^2 ). It runs under 1.21s in analysis mode. code (In the contest it got 0 points because my code was quite bugged)
 » 4 years ago, # | ← Rev. 2 →   How to solve 100? My algorithm is: count elements which equal or less than arr[i], then print log2(cnt+1). I could do it in O(n) time, but I started 1 hour late, so I did in O(n 2). But I don't know if my solution is correct or not.Sorry for bad English.
•  » » It should be log2(cnt). Also you can calculate cnt by sorting.
•  » » » If you are counting arr[i] too, then log 2(cnt)
 » RESULTS ARE OUT NOW!!
 » 4 years ago, # | ← Rev. 3 →   LOOOOOOOOOL! First place :D, how could it be? Achievement unlocked :P I think tests for fifth are weak.
•  » » How did you solve it then?
•  » » » 4 years ago, # ^ | ← Rev. 2 →   CodeFor N ≤ 104 I did Prim's O(N 2) algo (for safety) and for bigger I just connected all components (via DSU) with edges of cost 0, then with edges of cost 1, ... until the graph gets connected. :P Look at the code.
•  » » » » 4 years ago, # ^ | ← Rev. 3 →   Can someone create an anti-test?
•  » » » » » 4 years ago, # ^ | ← Rev. 4 →   As your array size of bool e[] was too small (M + 9 which is 107 + 9), it is quite easy to hack your solution with a case that the maximum weight of an edge in the MST is greater than 10, your solution may connect some incorrect vertices like 107 + 13 as e[j + r] may return TRUE for j + r is greater than your array size.Meanwhile, I originally want to make your solution TLE on some cases instead of WA, so i change your array size of bool e[] to M + M which is sufficient.Finally, your code will TLE in cases that number of unique elements is greater than 104, and the weight of an edge in the MST is quite large, as the time complexity of your solution is .For instance, your code will TLE on this case: 100000 9999999 7999999 5000000 4999999 . . 4900003 Anyway, i found it not easy to create such a case that your code(assuming the problem of illegal access to array is fixed) will TLE. But, I think the official data set does not contain any max cases with big is quite disappointing.
•  » » » » » » Yeah, I got TL on your test. :P I thought that tests maybe weak and not include such test. :D
 » 4 years ago, # | ← Rev. 3 →   Hello, I need you help guys Please give any ideas how could this code for C problem and this code for B problemget SIGSEV on some of the tests??! I am just sick of getting this verdict, I get it almost every contest!
•  » » In the code for problem C, you have a bad limit, because you have maxn = 500009 instead of maxn = 1048576, that is 2^20.
•  » » » Thank you. What can you say about the B problem? Does seg tree require limit of N*4? I thought N*3 is more than enough..
•  » » » Even though, it won't pass. Cause, utilizing map here takes more memory than intended. He should remove his map and use another way to compress.
•  » » » » I sent the code with the correct limit, and it works perfectly.
•  » » 4 years ago, # ^ | ← Rev. 3 →   For problem B, change the size of s array by maxn*5 and get AC. I know, that's sad :'( Maybe with maxn*4 also works
•  » » » maxn*4 is enough.
•  » » » » Guys, can anyone prove that N*3 is not enough? Because, in one tutorial, I have read, that N*2 is already enough (it wasn't seg tree built by loop, it was the same reqursive aproach..)
•  » » » » » 4 years ago, # ^ | ← Rev. 2 →
•  » » » » » I think that for find a correct limit you need to know that the Segment Tree will have a height of , now you know that for every level in the Segment Tree the number of nodes is equal to , then the total nodes in the Tree is .See this link
•  » » There's actually a really good implementation of segment tree that uses 2*N memory: click. It's iterative, and therefore much faster than the recursion based segment tree. There are some problems where recursive segment trees are required. However, this should work on most problems.For this problem you actually didn't need segment tree. There exists a very simple greedy solution (< 15 lines lol).
 » I'd like to share my (approximately) O(N) solution to 120http://pastebin.com/n0eXg04q
•  » » Omg!!! o_O
•  » » O (N) is compilation time here :D
 » Will there be any editorial ?
 » That feeling when one if costs you 120 points... and 11th place. I feel dumb anyways since I didn't use a basic Sieve of Eratosthenes in D, what I did was for every number in the interval I used logN prime factorization and used the formula f(N) = product of f(p^i) where p is every prime factor, and i is its exponent. f(p^i) can be calculated in logarithmic time, so the algorithm is about O(NlogN). (the solution passed in under 1s in analysis mode)Code
•  » » My approach was the same as yours. After reading pllk's solution I also feel extremely stupid.
 » How to solve E?
•  » » I used DSU to group the elements and applied greedy approach to find the minimum result.First group all the elements by finding whose modulus gives 0, then go for 1,then 2 and so on.. till you have grouped all.My Code
•  » » » Weak tests or there is some legit proof that this works fast?
•  » » » 3 years ago, # ^ | ← Rev. 2 →   Won't your code TLE on this case? 100000 9999999 7999999 5000000 4999999 . . 4900003 UPD By submitting your code and the input to http://evaluator.hsin.hr/, your code results in TLE: » 3 years ago, # | ← Rev. 3 →   I have a solution for problem Sirni that can solve up to Subtask 3 ( n ≤ 105, p ≤ 106), but I don't know how to deal with p ≤ 107.First, remove all duplicate from array P. Then, call next x the index of the smallest number in P that is larger than or equal to x.Now, consider index i. For each integer k, let m = kP i, we will only add the edge (i, next m). Finally, we build the MST for the graph.Why we can ignore all edge that connect index i and all index a 1, a 2, ..., a k such that P next m + 1 ≤ P a 1 ≤ P a 2 ≤ ... ≤ P a k ≤ m + P i - 1? Because, the algorithm will eventually add edge (next m;a 1), (a 1, a 2), (a 2, a 3), ..., (a k - 1, a k). So, for each j in [1;k], instead of using edge (i;a j) with cost P a j - m, we can use edges (i;next m), (next m;a 1), (a 1, a 2), ..., (a j - 1, a j) with the same cost and more benefit. So, we only need to consider edge (i, next m).The maximum number of edge in the graph is , which is about .UDP: My code
•  » » It's enough to change std::sort to countsort. I've modified your code a bit and it got accepted.Modified code
•  » » I used the same approach and got AC(worked for p ≤ 107).It seems that you're sorting the edges in order to create the MST(please correct me if I'm wrong), this works in which wont work for p ≤ 107, but since the weight of the edges are  ≤ 107, you can create an array of vectors of size 107 and add the edges to the corresponding vector, this way the complexity is . code#include using namespace std; #define ll long long #define f(i, x, n) for(int i = x; i < (int)(n); ++i) int x, nxt, p; vector > w; int P(int v){ if (p[v])return p[v] = P(p[v]); return v; } int main(){ int n; scanf("%d", &n); f(i, 0, n)scanf("%d", x + i), nxt[x[i]] = x[i]; sort(x, x + n); n = unique(x, x + n) - x; for (int i = 9999999; i >= 0; --i)if (!nxt[i])nxt[i] = nxt[i + 1]; f(i, 0, n){ int t = x[i], z = nxt[t + 1]; if (z && z - t < t)w[z - t].push_back(make_pair(t, z)); for (int j = t << 1; j <= 10000000; j += t){ z = nxt[j]; if (!z)break; if (z - j < t)w[z - j].push_back(make_pair(t, z)); } } ll an = 0; int k = 0; f(i, 0, 10000000){ vector > &v = w[i]; int s = v.size(); f(j, 0, s){ int x = P(v[j].first), y = P(v[j].second); if (x == y)continue; an += i; p[y] = x; if (++k + 1 == n)break; } if (k + 1 == n)break; } printf("%lld\n", an); } 
•  » » 3 years ago, # ^ | ← Rev. 2 →   With counting sort it can get accepted, http://ideone.com/iqBChIUPD: Actually, I was bit late :(