Tutorial is loading...

Tutorial is loading...

Tutorial is loading...

Tutorial is loading...

Tutorial is loading...

Tutorial is loading...

Tutorial is loading...

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

1 | Petr | 3353 |

2 | fateice | 3306 |

3 | Syloviaely | 3274 |

4 | tourist | 3235 |

5 | OO0OOO00O0OOO0O0…O | 3181 |

6 | Um_nik | 3158 |

7 | V--o_o--V | 3148 |

8 | dotorya | 3145 |

9 | LHiC | 3115 |

10 | mnbvmar | 3096 |

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

1 | tourist | 178 |

2 | rng_58 | 168 |

3 | Petr | 158 |

3 | csacademy | 158 |

5 | lewin | 150 |

6 | Swistakk | 149 |

7 | Errichto | 140 |

8 | ko_osaga | 139 |

8 | matthew99 | 139 |

10 | adamant | 138 |

Tutorial is loading...

Tutorial is loading...

Tutorial is loading...

Tutorial is loading...

Tutorial is loading...

Tutorial is loading...

Tutorial is loading...

Tutorial of VK Cup 2018 - Round 1

↑

↓

Codeforces (c) Copyright 2010-2018 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: May/23/2018 21:36:46 (d2).

Desktop version, switch to mobile version.

User lists

Name |
---|

On Div1C/Div2D:

The same approach can be also implemented using multiset, which is probably faster to write, but has an extra multiplicative factor, which may or may not fit into TL.My solution got AC with maximum execution time of 2917ms. Let's say that I was lucky, or I have to send a dearest thank-you to pragma and synced C++ I/O for making that happened...

Sorry. Deleted.

for div1a/div2b

I used to think so, coded it in 36171159 and got TLE :( Perhaps I should learn a normal language

It can be much faster.

Let the largest prime factor of

Xbep(X), andq(X) =X/p(X). GivenX_{1},X_{0}=X_{1}-p(X_{1}) + 1 =X_{1}(1 - 1 /q(X_{1})) + 1. Notice that leaglX_{1}'s are always composite (not prime) andq(X_{1}) is at least 2. If we find aX_{1}such thatq(X_{1}) = 2, all largerX_{1}'s will not produce better answer, and we can stop searching.X_{0}' =X_{1}'(1 - 1 /q(X_{1}')) + 1 ≥X_{1}'(1 - 1 / 2) + 1 >X_{1}(1 - 1 / 2) + 1 =X_{0}, whereX_{1}' >X_{1}andX_{0}' corresponds toX_{1}'.q(X_{1}) = 2 is actually quite common. It just meansX_{1}is double of a prime, and prime is quite common. Since the distance to the next prime afterNis roughly , we only need to searchX_{1}'s. Therefore, the overall complexity is .My solution runs in 15ms: http://codeforces.com/contest/947/submission/36159299

"Clearly, we can obtain N from any number in interval [N - (P(N) + 1), N] by picking P(N) as the prime, and we cannot obtain N from any other number."

I agree with that, but why is P(N) always the best choice for the prime? Why is not possible to pick a smaller prime factor for X2 and then P(X1) for X1?

And you meant [

N-P(N) + 1,N], right?The largest prime factor gives the widest range of possible solutions. For example, if N = 14, the largest prime is 7 so the range is [8, 14] but if you choose the prime 2 the range is only [13, 14].

I also think it is a typo in authors' range formula.

You can prove it that if you will pick some prime divisor smaller than the largest prime divisors the range, which you will get, of numbers from which we can obtain N will lie in the range given by the largest prime divisor.

Ad first question: The interval of the previous value is always [

N-p+ 1,N], wherepis a prime divisor ofN. For any prime, this interval would be contained in the interval [N-P(N) + 1,N], hence it is optimal to consider only the largest prime divisor.Ad second question: Yes, I'll fix it.

"Clearly, we can obtain N from any number in interval [N - (P(N) + 1), N] by picking P(N) as the prime, and we cannot obtain N from any other number."

Can you please explain this statement

The solution for B has an error in it, the range will be [N-(P(N)-1),N] and not +.

here

X(i)>=X(i-1)not just greater than so value should be strictly greater than its previous multiplex2 = k2p2 — (1) x2 >= x1 — (2) (k2-1)p2 < x1 -> k2p2 — p2 < x1 -> x2 — p2 < x1 by (1) — (3) By (2) & (3) Range of x1 is (x2 — p2, x2] -> [x2 — p2 + 1, x2] where p2 is largest prime factor of x2.

Auto comment: topic has been updated by majk (previous revision, new revision, compare).can someone please explain the idea behind this solution : http://codeforces.com/contest/948/submission/36161437

If you have X2 and want to know the range of X1 then you do the following.

Factorize X2 = p1^k1*p2^k2...pn^kn (p1,p2..,pn are primes), then the range of X1 is (X2-pn+1, X2). Because if you choose a bigger range then we can not obtain X2.

For example think about X2 = 14 = 2^1*7^1

The range for X1 will be (14-7+1, 14) = (8,14).

If we choose the range (7,14) then when we peek x1 = 7 and the prime less then x1 (2 or 5) we can not get the X2.

the same process is done for finding X0.

majk Excuse me, about problem E. How can I figure out the eigenvectors v (and Q, Q^-1) using eigenvalues only rather than proof it after knowing it. Is there any material about this? Thanks.

Answer to Bonus of Div1A/Div2B:

We can precompute

P(X) for allXin [1..N] with slightly modified Eratosthenes Sieve in : Each time we run a primepthrough the sieve, mark all multiples ofpwithp. In the end, all numbers are marked withP(X)!Now, for each query

X_{2}, we can find the range ofX_{1}inO(1) by looking at the precomputed table ofP(X). According to my another comment, we only need to searchX_{1}'s. And, for eachX_{1}, we can also findX_{0}inO(1) by lookup.Putting things together, this algorithms works in .

can anyone explain me the solution of problem c

The second solution:

If we make a new pile of snow and subtract all pile of snow, obviously, we will get TLE.

So, we don't do the subtraction.

We can use a variable called

sumwhich means the accumulated temperature until now.If

v[i] < =sum+t[i], then it will disappear and we can calculate the total volume of melted snow. For thosev>sum+t[i], we just addt[i] *numto the answer.And there is another problem, the new pile of snow may

v[i] < =sum+t[i], but actually it doesn't disappear. So, we can addsumto every pile of snow in the begin.Finally we can use multiset to remove element in

log(N).Here is my submission 36189438

UPD: num means the number of pile in the multiset, becausev>sum+t[i], so it won't disappear, the volume of melted snow ist[i] *numthanks got it

what do you mean by this " add t[i] * num " .

here num means???

sorry, I didn't define it clearly. It means the number of pile which v > sum + t[i](already in multiset) And multiset has already sorted all element, so we can do it from the being of the set.

Why you add sum+t[i] always???

Because

summeans the accumulated temperature. Instead of subtracting all piles every time, we can just seesumto decide whether the pile disappear or notOK,,I got it.

Thanks..

Thanks for your explanation and submission, they were very clear!

In

Primal Sportproblem shouldn't the answer be 14 for input of 20.Assume

X0= 14If

P1= 4 thenX1= 16 (X1>X0)If

P2= 5 thenX2= 20 (X2>X1)Since we got answer 20 with X0 = 14 shouldn't that be the answer.

Here you are choosing p1 = 4 which is not a prime number

My Bad Sorry and Thanks gaurav569singh

Problem F can be solved by randomized algorithm:

If you just try random permutation and check if it meets the condition, (as you may know), it fails in test case around 96. However, if you modify this algorithm a bit, you’ll get accepted!

Details are as follows:

•Pick up vertex A which has biggest degree

And repeat this until you find the answer:

•Take one leaf B from the other tree (that is, the tree which doesn’t contain A) randomly and map A to B

•Take Vertex C which belongs to the tree with A and doesn’t connect to A randomly, and Vertex D which connect to B (B is a leaf, so D will be uniquely determined), and map C to D

•Just try random permutation for remaining parts and pray for judge :)

Code :36183744

Good job!

What you described is equivalent to the correct way of solving the case where the the highest degree vertex has N-2 neighbours. This was the case that the most "naive" random solutions struggled with — and the antitests were usually of the form G = "almost star", H = "almost path".

Part of the reason why there weren't too many strong pretests against random solutions is that this might help you tweak the meta parameters until you get accepted. In retrospect, I would put the test 96 in the pretest, so that contestants are at least given a chance to realize that we do not expect randomized to pass.

In other words, if the contest was full feedback, we would probably require solution by increasing

Nto 100000. We felt that the task was difficult enough and implementing the required operations on the graph on sublinear time just added implementation time, but was more or less standard.Thank you for replying.

Yes, I know it's very hard to implement this solution and pass system test within contest time.... (partly because we only know the result from pretest)

I'll check O(N log N) solution later, thank you for interesting problem!

Can Div2 C is done by segment tree? if Yes please explain it.

It can solve by segment tree, we only need to maintain the snow that melts every day for a volume equal to the temperature of the day.

I get WA on test case 4 for question "producing snow"...Please help...Thanks in advance... Here's the link to my solution (http://codeforces.com/contest/923/submission/36195419)

Can anyone please tell me what is the problem in my 948A: https://imgur.com/a/DYoBP. Judge says Changed (1,2) from S to D. But it doesn't look like that. UPD: I found it. I considered it as a 1 based indexing first. Sorry!

Can anyone elaborate on how to add 1 to a segment by two additions using prefix sums in Div2C/Div1B Producing Snow?

You add 1 to the start of the segment, and add -1 to the end of the segment. When processing points, you add the value in the previously created array to a

currvariable, which will always indicate current element.By using a

difference array. You can perform the updates in constant time and access all the updated values at the end in linear time.In the formula I think there must be

`T[j]`

not`T[i]`

. Correct me if I am wrong.Problem 923B producing snow.

Should be fixed now.

Can anybody explain how to do this?

Adding 1 to the range by 2 additions?

Check the previous comments. It has just been asked.

Can anyone explain the correctness of the trie/multiset solution of 923-C Perfect Security ? I just don't seem to understand why the algorithm mentioned in the editorial is correct.

The question wants the minimum sequence. This means we should find the j that minimizes a[0] ^ b[j], remove b[j] from our list and continue. The structure with operations "minimize a[i] ^ x" over all x in a set and add/remove x is the binary trie.

36157666

Why

RE?Could anyone find out what is wrong with my program for Div. 2 D? I used a trie like the editorial, but I seem to be off by one for some answers and I have no idea why. Could someone help me out? thanks 36214710

There might be a typo in the editorial for problem f.

The editorial says,

"Assume that one of the graphs is 1-star. Without loss of generality let it be G. Denote v the vertex that can be removed to turn G into star, u its only neighbor, and w be the vertex of degree N - 2. In graph H, find any leaf and denote it w'. Let its only neighbour be

u'. Furthermore, pickv'a vertex that is not adjacent tou'(such vertex always exists as H is not a star). "It seems that

v'andu'should be swapped.why my code is giving WA.

http://codeforces.com/contest/948/submission/36241274

Ya Got Accepted no need of help

In 923D — Picking Strings, transforming BAAB to BBAABB is possible, as per ac solutions, can someone demonstrate how the transformation is done?

`B.A.A.B -> B.BB.A.B -> B.BB.A.AB ->B.BB.A.AAB = BBBB`

`B.B.B.B -> B.B.AB.B -> B.B.AAB.B = BBAABB`

I hope you understand my transitions :)

Yes I get it, and thanks a lot.

What is the tricky case in Test case 11 in Div1D — 923D Picking Strings?

AAA BBAAA 1 1 3 1 5

Answer is 0.

How would you solve Div2A if you were to minimize the number of walls being built?