# | User | Rating |
---|---|---|
1 | tourist | 4009 |
2 | jiangly | 3773 |
3 | Radewoosh | 3646 |
4 | ecnerwala | 3624 |
5 | jqdai0815 | 3620 |
5 | Benq | 3620 |
7 | orzdevinwang | 3612 |
8 | Geothermal | 3569 |
8 | cnnfls_csy | 3569 |
10 | gyh20 | 3447 |
# | User | Contrib. |
---|---|---|
1 | awoo | 161 |
2 | maomao90 | 160 |
3 | nor | 157 |
4 | atcoder_official | 156 |
4 | cry | 156 |
6 | -is-this-fft- | 155 |
7 | maroonrk | 154 |
8 | adamant | 153 |
9 | Um_nik | 151 |
10 | djm03178 | 146 |
Name |
---|
Why the main site isn't working ? UPD : Fixed now
How to solve 140?
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 edge2-6
and3-6
wouldn't your idea only consider edge2-3
instead??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.
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?
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?
Just decided to elaborate more on it.
This works in
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".
The sum
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)
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.
It should be log2(cnt). Also you can calculate cnt by sorting.
If you are counting arr[i] too, then log2(cnt)
RESULTS ARE OUT NOW!!
LOOOOOOOOOL! First place :D, how could it be?
Achievement unlocked :P
I think tests for fifth are weak.
How did you solve it then?
Code
For 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.
Can someone create an anti-test?
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 ase[j + r]
may returnTRUE
forj + 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[]
toM + 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:
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
Hello, I need you help guys Please give any ideas how could this code for C problem and this code for B problem
get 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 ofmaxn = 1048576
, that is2^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.
For problem B, change the size of
s
array bymaxn*5
and get AC. I know, that's sad :'( Maybe withmaxn*4
also worksmaxn*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..)
see
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 120
http://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?
Won't your code TLE on this case?
UPD By submitting your code and the input to http://evaluator.hsin.hr/, your code results in TLE:
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
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
.
With counting sort it can get accepted, http://ideone.com/iqBChI
UPD: Actually, I was bit late :(