Before contest

Codeforces Round #492 (Div. 1) [Thanks, uDebug!]

17:22:38

Register now »

Codeforces Round #492 (Div. 1) [Thanks, uDebug!]

17:22:38

Register now »

*has extra registration

Before contest

Codeforces Round #492 (Div. 2) [Thanks, uDebug!]

17:22:38

Register now »

Codeforces Round #492 (Div. 2) [Thanks, uDebug!]

17:22:38

Register now »

*has extra registration

# | User | Rating |
---|---|---|

1 | tourist | 3434 |

2 | Petr | 3353 |

3 | OO0OOO00O0OOO0O0…O | 3314 |

4 | fateice | 3306 |

5 | Um_nik | 3286 |

6 | Syloviaely | 3274 |

7 | dotorya | 3145 |

8 | LHiC | 3114 |

9 | Radewoosh | 3098 |

10 | mnbvmar | 3096 |

# | User | Contrib. |
---|---|---|

1 | tourist | 178 |

2 | rng_58 | 166 |

3 | Petr | 155 |

3 | csacademy | 155 |

5 | Swistakk | 149 |

5 | lewin | 149 |

7 | Um_nik | 142 |

8 | Errichto | 140 |

9 | matthew99 | 138 |

9 | Vovuh | 138 |

Codeforces (c) Copyright 2010-2018 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Jun/24/2018 02:12:23 (d3).

Desktop version, switch to mobile version.

User lists

Name |
---|

Why the main site isn't working ?

UPD: Fixed nowHow 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 edge`2-6`

and`3-6`

wouldn't your idea only consider edge`2-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?

where

M= 10^{7}Just decided to elaborate more on it.

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 10^{43}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)

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 inO(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!!

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≤ 10^{4}I did Prim'sO(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.Can someone create an anti-test?

As your array size of

`bool e[]`

was too small (`M + 9`

which is 10^{7}+ 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 10^{7}+ 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 10

^{4}, 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 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.

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..)

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

ifcosts 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 formulaf(N) = product of f(p^i)wherepis every prime factor, andiis its exponent.f(p^i)can be calculated in logarithmic time, so the algorithm is aboutO(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?

UPDBy 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≤ 10^{5},p≤ 10^{6}), but I don't know how to deal withp≤ 10^{7}.First, remove all duplicate from array

P. Then, callnext_{x}the index of the smallest number inPthat is larger than or equal tox.Now, consider index

i. For each integerk, letm=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

iand all indexa_{1},a_{2}, ...,a_{k}such thatP_{nextm}+ 1 ≤P_{a1}≤P_{a2}≤ ... ≤P_{ak}≤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 costP_{aj}-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 codeIt'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≤ 10^{7}).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≤ 10^{7}, but since the weight of the edges are ≤ 10^{7}, you can create an array of vectors of size 10^{7}and add the edges to the corresponding vector, this way the complexity is .codeWith counting sort it can get accepted, http://ideone.com/iqBChI

UPD:Actually, I was bit late :(