By DBradac, history, 17 months ago, ,

Click to see where the coding begins in your timezone.

We can discuss the problems here after the contest.

•
• +59
•

 » 17 months ago, # | ← Rev. 2 →   +5 Why the main site isn't working ? UPD : Fixed now
 » 17 months ago, # |   +56 How to solve 140?
•  » » 17 months ago, # ^ | ← Rev. 3 →   +27 Edit: wrong algorithm. It's actually possible to end up with a cycle.
•  » » » 17 months ago, # ^ |   0 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??
•  » » » » 17 months ago, # ^ |   0 No, I'd incrase cnt[6] 3 times, so 6 would find an edge with 2*3 and cost 0, and then with 3*2 and also cost 0.
 » 17 months ago, # |   +3 When the results will be published?
•  » » 17 months ago, # ^ |   +3 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.
•  » » 17 months ago, # ^ |   +6 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."
 » 17 months ago, # |   +39 It seems that the problemsetter likes the sieve of Eratosthenes.How to solve the last problem?
•  » » 17 months ago, # ^ |   +3 120 can solved by prime factorization yes?
•  » » » 17 months ago, # ^ | ← Rev. 2 →   0 Yes. Still no idea why they would put this as a 120-pointer.
•  » » » 17 months ago, # ^ |   +3 I used a modified sieve of Eratosthenes:http://paste.dy.fi/ME9
•  » » » » 17 months ago, # ^ |   0 What's the complexity of that algorithm?
•  » » » » » 17 months ago, # ^ |   +3 where M = 107
•  » » » » » 17 months ago, # ^ | ← Rev. 5 →   +3 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)
•  » » » » » » 17 months ago, # ^ |   0 Pretty cool, thanks for the explanation :D
•  » » 17 months ago, # ^ |   +8 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)
 » 17 months ago, # | ← Rev. 2 →   0 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(n2). But I don't know if my solution is correct or not.Sorry for bad English.
•  » » 17 months ago, # ^ |   +3 It should be log2(cnt). Also you can calculate cnt by sorting.
•  » » » 17 months ago, # ^ |   0 If you are counting arr[i] too, then log2(cnt)
 » 17 months ago, # |   0 RESULTS ARE OUT NOW!!
 » 17 months ago, # | ← Rev. 3 →   +18 LOOOOOOOOOL! First place :D, how could it be? Achievement unlocked :P I think tests for fifth are weak.
•  » » 17 months ago, # ^ |   +6 How did you solve it then?
•  » » » 17 months ago, # ^ | ← Rev. 2 →   +13 CodeFor N ≤ 104 I did Prim's O(N2) 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.
•  » » » » 17 months ago, # ^ | ← Rev. 3 →   0 Can someone create an anti-test?
•  » » » » » 17 months ago, # ^ | ← Rev. 4 →   +32 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.
•  » » » » » » 17 months ago, # ^ |   +5 Yeah, I got TL on your test. :P I thought that tests maybe weak and not include such test. :D
 » 17 months ago, # | ← Rev. 3 →   0 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!
•  » » 17 months ago, # ^ |   0 In the code for problem C, you have a bad limit, because you have maxn = 500009 instead of maxn = 1048576, that is 2^20.
•  » » » 17 months ago, # ^ |   0 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..
•  » » » 17 months ago, # ^ |   0 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.
•  » » » » 17 months ago, # ^ |   +1 I sent the code with the correct limit, and it works perfectly.
•  » » 17 months ago, # ^ | ← Rev. 3 →   0 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
•  » » » 17 months ago, # ^ |   0 maxn*4 is enough.
•  » » » » 17 months ago, # ^ |   0 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..)
•  » » » » » 17 months ago, # ^ | ← Rev. 2 →   0
•  » » » » » 17 months ago, # ^ |   0 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
•  » » 17 months ago, # ^ |   0 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).
 » 17 months ago, # |   +19 I'd like to share my (approximately) O(N) solution to 120http://pastebin.com/n0eXg04q
•  » » 17 months ago, # ^ |   0 Omg!!! o_O
•  » » 17 months ago, # ^ |   +3 O (N) is compilation time here :D
 » 17 months ago, # |   0 Will there be any editorial ?
 » 17 months ago, # |   0 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
•  » » 17 months ago, # ^ |   +3 My approach was the same as yours. After reading pllk's solution I also feel extremely stupid.
 » 17 months ago, # |   +14 How to solve E?
•  » » 17 months ago, # ^ |   -10 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
•  » » » 17 months ago, # ^ |   +14 Weak tests or there is some legit proof that this works fast?
•  » » » 17 months ago, # ^ | ← Rev. 2 →   +39 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:
 » 17 months ago, # | ← Rev. 3 →   +22 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 nextx 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 = kPi, we will only add the edge (i, nextm). Finally, we build the MST for the graph.Why we can ignore all edge that connect index i and all index a1, a2, ..., ak such that Pnextm + 1 ≤ Pa1 ≤ Pa2 ≤ ... ≤ Pak ≤ m + Pi - 1? Because, the algorithm will eventually add edge (nextm;a1), (a1, a2), (a2, a3), ..., (ak - 1, ak). So, for each j in [1;k], instead of using edge (i;aj) with cost Paj - m, we can use edges (i;nextm), (nextm;a1), (a1, a2), ..., (aj - 1, aj) with the same cost and more benefit. So, we only need to consider edge (i, nextm).The maximum number of edge in the graph is , which is about .UDP: My code
•  » » 17 months ago, # ^ |   +5 It's enough to change std::sort to countsort. I've modified your code a bit and it got accepted.Modified code
•  » » 17 months ago, # ^ |   +5 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[100000], nxt[10000001], p[10000001]; vector > w[10000001]; 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); } 
•  » » 17 months ago, # ^ | ← Rev. 2 →   +5 With counting sort it can get accepted, http://ideone.com/iqBChIUPD: Actually, I was bit late :(