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

1 | tourist | 3434 |

2 | OO0OOO00O0OOO0O0…O | 3280 |

3 | Syloviaely | 3274 |

4 | Um_nik | 3248 |

5 | Petr | 3233 |

6 | fateice | 3230 |

7 | mnbvmar | 3096 |

8 | anta | 3053 |

9 | FizzyDavid | 3050 |

10 | LHiC | 3047 |

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

1 | rng_58 | 162 |

2 | tourist | 160 |

3 | Petr | 152 |

4 | csacademy | 151 |

5 | Swistakk | 147 |

6 | Vovuh | 145 |

6 | Um_nik | 145 |

8 | Nickolas | 142 |

9 | PikMike | 141 |

10 | 300iq | 137 |

Codeforces (c) Copyright 2010-2018 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Aug/14/2018 13:37:38 (d3).

Desktop version, switch to mobile version.

User lists

Name |
---|

Can we submit our solutions after the contest?

Yeah, you just have to wait for a while. When you know your score, there's an "analysis mode" and you can submit again for practice.

Thank you

Damn, got stuck for like 90 minutes on the fourth problem, while the fifth was a piece of cake to solve :(

How to solve it?

Let the height of a strip be 1. The cuts are at heights , for 0 <

k_{i}<a_{i}, and we want the number of distinct fractions among those.Let there be a fraction , with coprime

x,yandx<y. If there's , then must be an integer; for coprimex,y, it means thatydividesa_{i}; this condition is also sufficient, and the number of satisfyingxfor the givenyis φ(y).That means we need to sum up φ(

y) for all distinct divisorsyof at least onea_{i}. For sufficiently smalla_{i}, computing φ(y) for all 1 ≤y≤ 100000 is easy, and to check a divisor's existence, we can use an array of bools denoting the existing values ofa_{i}and try the multiples of everyy.But yeah, 4 and 5 should've been swapped. I think I spent about an hour or more on this.

I also have similar solution, except when computing the number of distinct irreducible (

removed) fractions, I just used O(N^2 * log N) precomputation and then just pasted the array in the code, since the limit is 1 MB.Coprime

x,ymeans irreducible fraction.Precomputation: nice! It'd be funny if some future problem of COCI could be solved in

O(1) like this :DOh, OK, sorry, I misread the first paragraph, I thought it was needed mentioning there as well.

But yeah, I was surprised when I found out the source limit is 1 MB, usually it's limited by 100 KB.

Why can't we simply use this f(a * b) = f(a) * f(b) for coprime a and b? Am I missing something?

Also we can count number of irreducible fractions using Inclusion–exclusion principle. My code

I think this problem (problem D) is similar to SGU 370.

Oh yeah, 618 points! My best result so far, ever!

Short ideas of some tasks:

SUMO: binsearch the smallest

ksuch that the graph formed by the firstkedges isn't bipartite; bipartiteness can be checked with BFSUTRKA: DP on (number of edges,vertex

i,vertexj) gives the maximum advantage (can be negative) out of all paths fromitoj, stopping the computation when there's a negative cycle and only adding edges to existing paths gives me 80% of pointsCOKOLADE: there only ways of how the array of "candies per capita" can look; iterate over the smallest

k-s corresponding to them — for a givenk, find the smallestk' >ksuch that some ; for a givenk, only the tables with equal (candies per capita, integer division) socializeI have

O(n^{3}*log^{2}(n)) for last problem (pretty sure it is solvable inO(n^{3}*log(n))) time. I have 80% of points for this problem as well.Let i-th edge's weight be m[i]-s[i]. So we have to find shortest cycle with negative weight in this graph. Lets precalculate all minimal distances for n=1,2,4,8,16... edges using Floyd-Warshall algorithm. Then let's do binary search by the answer. Using precalculated information we can find shortest disctances between every pair of vertexes with exactly M edges between them in

O(n^{3}*log(n)) time. If distance from i to i is negative for some i, than we have cycle of negative weight for current value of M.And for the reference, if you just use matrix multiplication, incrementing the size by 1 (so no need for binary search), you get 70% of points. Which seems quite a lot.

How do you assume if there is a negative cycle with lenght M there have to be with lenght M + 1?

There probably is some misunderstanding.

`If distance from i to i is negative for some i, than we have cycle of negative weight for current value of M.`

In this sentence I meant, that we have cycle with length not greater than M. If we have negative cycle with length M, than, obviously, shortest distance from i to i will be negative also for values bigger than M.

Also, SUMO can be solved with DSU. For each component

c, store the number of a component that should be colored in a different color than this component inadj[c]. Suppose an edge (a,b) comes in. Ifgroup(a) =group(b), then we output the number of the current edge. Otherwise mergegroup(adj[a]) withgroup(b), andgroup(adj[b]) withgroup(a).I think binsearch is the simplest solution for this. At least, I don't see any completely obvious greedy solution, although that was my initial guess. DSU is just unnecessarily much to code.

No, not at all: http://ideone.com/OIgU8Y.

Challenge accepted: http://ideone.com/wcbbCN

You may have fewer lines, but those lines are much more complicated.

It might look complicated, but it's based on a BFS, which is really simple to code when you know it (which probably anyone does before DSU). I also don't use typedefs and extensive defines, and don't put every variable in a static array, which would probably make it clearer, but I wouldn't be able to write it instantly.

I'm not talking about lines — if I wanted to, I could cut down on them significantly, and so could gen on his. If you look at any BFS I've coded, it looks like this (with the "part" array and the few operations with it added). If you look at any binsearch I've coded, it also looks like this, and same with reading+graph construction in my codes. And I don't copy-paste.

agree with Chortos-2 and besides it is also worth mentioning that at least I have DSU prewritten.

upd: and also, BS is notoriously tricky XD

Imagine you go to a competition where pre-written code is not allowed. You can solve the problem in theory, but coding it takes too long or you make mistakes there, and so you can't solve the problem in question. Moral lesson: prewritten code = potential fail.

On the other hand, why not have pre-written binsearch, too, if it's so tricky? You pose a problem and one solution in your post. And once again, if you can write it quickly and correctly in any situation, it's not tricky.

I'm not saying people should write codes the same way I do. Everyone has their own style, but if you're able to instacode basic algorithms, it can give you a large edge.

Actually I have prewritten BS too

http://pastebin.com/MLXTSmuv

But, in fact I am not the "script-kiddie" kind of man :D. I don't use prewritten codes any more (excluding on CF and TC maybe where rating kinda matters). What I meant by my previous comment was that DSU is one of the data-structure you can type w/o thinking and quickly, while BS needs a special treatment (for me).

Lastly, I think ur right, for ambitious algorist implementation should be of no problem.

I guess it varies from person to person. Binsearch is just about getting the ± 1 correct, which is easy if you use half-open intervals, and it's short. When coding DSU, I still need to think for a while sometimes.

I agree with Xellos. By the way, I haven't thought about binsearch at all, so at the time was wondering why they have put DSU in the first place in a COCI contest.

Is DSU that unusual for COCI?

DSU was my second idea (first was an obvious greedy, which, as I soon realized, was obviously wrong :D), but it seemed strange for a 3rd problem, so I tried to find some other way to solve it.

No, I mean, it is only a 100p problem on a high school contest, surely it should not require any advanced algorithm. ;D

True that. DSU is not really hard, but still.

i think gen's DSU solution is very shorter than your binary search code.

I believe that binary search is the tougher way to go, I tried to think of a binary search solution in the beginning but I couldn't find any, thumbs up for your idea I really liked it! I ended up coding a DSU solution and I don't even complete scanning the input when I get the answer :D :D

http://ideone.com/ud4foP

UTRKA for 100%:

Let

D(i,j,k) be maximum advantage out of all paths fromitojusing at mostkedges.If we know

D(i,j,h) for somehand eachi,jand we also knowD(i,j,l) for someland eachi,j, we can computeD(i,j,h+l) inO(n^{3}) time.At first we compute

D(i,j,k) forkequal to powers of two and after that we construct binary representation of the optimalkdigit by digit (starting with most significant digits).Total time complexity is

After computing

Dfor all powers of two, how do you search for the optimalk?Got full score in upsolving with this idea:

1) Calculate D for all powers of 2.

2) Calculate D for all powers of 2 decreased by 1 (lets call this array Prefix).

3) Find the smallest i, that Prefix[i] contains negative cycle. Out current answer is 2

^{a}- 1, where a == i+14) Lets try not to use some particular bit in our current answer (from the most valuable to less valuable). For this we will keep track of our current suffix. Suppose we are looking for i-th bit. We need to join our current suffix and Prefix[i-1]. If the result of join contains negative cycle — we do not use i-th bit, otherwise — we use it and update current suffix.

My code is ugly, but maybe it will be helpful.

In fact, I search for optimal

k- 1 (that is, the maximum number such that there is no negative cycle using this number of edges, or less). What I do is binary search, where I keepDfor actual lower bound. In the beginning my lower bound is 0 and upper bound is the smallest power of twoU, such that there is a negative cycle withU(or less) edges. Therefore the size of interval where I search is power of two and it always will be (as it halves in each iteration).The number

Win the middle of my interval is lower bound + some power of two, so I can computeDforWinO(n^{3}) usingDs for lower bound and for that power of two. If there is a negative cycle using at mostWedges, we can set upper bound toW. Otherwise we can set lower bound toW. We have already computedDforW, so we still knowDfor our lower bound.i think the problem Utrka was very similar to 147B - Smile House

Yeah, it is. Just the time limit is larger. But that one seems quite difficult, too — less than 200 successful solutions.

i don't solve this problem because i read the problem after the end of contest. :(

in the next contest i will do what sereja always recommend (reading ALL the problems)

Can anyone explain the solution of task "cokolade" ? My solution is sqrt(10^8) * 100, I simply consider all the divisors of the numbers, but this seems incorrect!

Before asking a question, check if it's been answered already. For example here

If this doesn't work for you, you're coding it wrong.

Thanks for replying, I'll check your comment.

I'm not allowed to log in from my location. Is there any other way I might participate?

I guess you are trying to log into "HONI 2013./2014. — 4.kolo". Try logging into "COCI 2013./2014. — Round #4".

i m asking this question to who used this idea(described below) while binary search. I and Fcdkbear could not come up with answer. Here is question :

Why dist[i][i] with using exactly M edges have to be less then using exactly M — 1 edges. I'm talking abouth coci last problem.

Could you please look that example :

if we have 4 nodes and this edges between them :

1 to 2 with -1 weight

2 to 3 with -1 weight

3 to 1 with -1 weight

2 to 4 with 1000 weight

4 to 3 with 1000 weight

when M = 3 dist[1][1] = -3 and when M = 4 dist[1][1] = 1998