Topcoder Open Algorithm Round 2B

9 years ago, # |

+22

Spent >10 minutes starting my computer and opening arena while found out the registration period is just over. Much frustrated orz

→ Reply

i4018

9 years ago, # ^ |

That's why you should not use windows

→ Reply

9 years ago, # ^ |

True bro, windows sucks

→ Reply

ha1vanka

9 years ago, # ^ |

used linux, but still missed it ;(

→ Reply

9 years ago, # ^ |

+15

Honestly, I would be happier had the same happened to me :P

→ Reply

9 years ago, # |

Huh, those were not easy tasks :P. 500 is very nice, so sad I was not able to come up with final piece during contest. Btw, isn't 1000 just easy LP? Can LP solution be not integral?

→ Reply

9 years ago, # ^ |

They can.

→ Reply

9 years ago, # ^ |

Great, so this is not another stupid LP problem, that's consoling :D.

→ Reply

9 years ago, # ^ |

Actually algorithm of integer LP is same, just substantially harder to implement :)

→ Reply

9 years ago, # ^ |

And definitely slower, so there is little chance it can get AC :P

→ Reply

jcvb

9 years ago, # ^ |

:) Does anybody know the solution of 1000?

→ Reply

matthew99

9 years ago, # ^ |

← Rev. 29 →

+45

1000 can be solved with this very simple algorithm based on network flow.

Let num_i be the number of opens(left parentheses) lying on the path from node i to root. dep_i be the number of edges of the path from node i to root. Then bal_i = 2num_i - dep_i is the balance i.e. the number of opens substract the number of closes(right parentheses).

So for a restriction of path $\text{[math]}$ , we have:

bal_u = bal_v

bal_w - bal_u ≥ 0, for any node w that lies on the path from u to v.

Why? Because if $\text{[math]}$ is open, then $\text{[math]}$ is close. So we needn't care about the LCA.

Besides, obviously dep_u + dep_v must be even.

Thus, we've got two kinds of restrictions:

$\text{[math]}$

OK, now let's build a graph. We know the maximal flow is equal to the minimal cut, so we'll just talk about the cut. For any node in the tree, we make n new vertices, and connect the source to the first vertex, and connect the last one to the sink with capacity ∞, and connect adjacent vertices with capacity 0(actually we don't connect them, it's just for better-understanding), then, we have to cut one edge, if we cut the edge connecting the k-th vertex and the (k + 1)-th vertex, then we consider that num of the tree node is k.

So for each edge connecting one node and its father. num of the node mustn't be smaller than its father's and mustn't be bigger than its father's by more than 1. If cost_open is smaller, then we add the cost of open to the answer, and if the node's num is equal to its father we have to pay cost_close - cost_open, otherwise we'll do the similar thing.

So how to deal with those restrictions? For example, if num_u ≤ num_v - Δ, for all k, if k - Δ ≥ 0 then add an edge from the (k + 1)-th node of v to the (k - Δ + 1)-th node of u, or if k - Δ < 0, then num_v ≠ Δ, we can simply add an edge from the k-th node of v to the (k + 1)-th node of v. All these edge have a capacity of ∞.

Finally, add the minimal cut of this graph, which equals the maximal flow, to the answer.

→ Reply

matthew99

9 years ago, # ^ |

← Rev. 2 →

If you can't see the formulas, this is the text:

Why? Because if $\text{[math]}$ is open, then y \rightarrow x is close. So we needn't care about the LCA.

Besides, obviously dep_u + dep_v must be even.

Thus, we've got two kinds of restrictions:

(num_v — num_u) \ge ceil(\frac{dep_u — dep_v}{2})

(num_v — num_u) = \frac{dep_u — dep_v}{2}

I can't get why Codeforces can't demostrate it properly :(

→ Reply

Jakube

9 years ago, # |

What was the idea behind Problem 300? I was able to code a solution with runtime O(A+B+C), but it was too slow.

→ Reply

9 years ago, # ^ |

First idea that you want to count number of non triangles, instead of triangles. It can be proven that if A ≥ B ≥ C and A ≤ B + C then this number is f(A) + f(B) + f(C) - f(A - B) - f(A - C) - f(B - C) where f(X) = 0 + 1 + ... + X(X - 1) / 2

→ Reply

9 years ago, # ^ |

For C = 1, B = 3, A = 3 we got:

f(3) + f(3) + f(1) — f(0) — f(2) — f(2) = 6 + 6 + 0 — 0 — 1 — 1 = 10 non triangles, but it is almost 1*3*3 = 9 combinations of al possible length values...

Something wrong..

→ Reply

9 years ago, # ^ |

← Rev. 2 →

f(3) = 3

→ Reply

9 years ago, # ^ |

f(3) = 0 + 1 + ... + 3*(3-1)/2 = 0 + 1 + 2 + ... + 3 = 6 =)) LOL

→ Reply

rnsiehemt

9 years ago, # ^ |

← Rev. 2 →

"First idea that you want to count number of non triangles, instead of triangles." Seriously, there are only 2 sentences. Please don't downvote someone who is trying to help because you are so impatient you can't read more than 1 sentence (speaking to everyone).

→ Reply

9 years ago, # ^ |

But in my case number of non-triangles is MORE than maximum possible number of triple of lengths )))

→ Reply

rnsiehemt

9 years ago, # ^ |

← Rev. 2 →

-16

Okay a = 1, b = 3, c = 3. Number of triples = 1*3*3 = 9.

Number of impossible = 6 as you calculated.

9 — 6 = 3.

Correct answer is 3.

→ Reply

9 years ago, # ^ |

Number of impossible triples = 6+6-1-1=10 is MORE than 9, as I calculated.

→ Reply

rnsiehemt

9 years ago, # ^ |

Ok I understand. You think f(x) = triangular number x. Actually f(x) = sum of first x-1 triangular numbers. So f(0) = 0, f(1) = 0, f(2) = 1, f(3) = 4, f(4) = 10 etc.

So f(3) + f(3) + f(1) — f(2) — f(2) — f(0) = 4 + 4 + 0 — 1 — 1 — 0 = 6.

9 — 6 = 3

→ Reply

9 years ago, # ^ |

Thank you!

→ Reply

9 years ago, # ^ |

-19

My maths definitely needs improvement

→ Reply

TooDumbToWin

9 years ago, # ^ |

Can anyone provide me a proof/hint (intuitive/mathematical) for this?

→ Reply

meijun

9 years ago, # ^ |

+13

Interpolation of [0, 0, 1, 4] is f(x)=x(x+1)(x-1)/6

→ Reply

ho-jo-bo-ro-lo

9 years ago, # ^ |

Let A<=B<=C. My solution is O(C-B) and it passed system test in 1.8s :|
In practice session though :(

→ Reply

Um_nik

9 years ago, # |

How to solve 500?

→ Reply

Errichto

9 years ago, # |

+10

The challenge phase, I don't hate you anymore. (I got to top40 thanks to one challenge)

How to solve 500p.?

→ Reply

9 years ago, # ^ |

+22

I was first before challenge phase and had no opportunity to get points (only other solution in my room was correct) :(

→ Reply

http://artofproblemsolving.com/community/c6h1248018_number_of_side_triplets_satisfying_an_inequality

9 years ago, # |

← Rev. 2 →

+63

I read anta's code, so I am smart now and can tell how to solve 500 ;p.
1) Bag B is heaviest for permutation P if for every prefix of P there is no bag C which contains more gems from that prefix than B.
2) If bags are unique then heaviest bag is unique

For every bag B you can enumerate possible prefixes P can contain so that they do not violate B being heaviest and by subset dp you can count how many such permutations exist. Then you need to sum it over all B and check if that is equal to 16!.

→ Reply

winger

9 years ago, # ^ |

+25

My approach was to check 10000 random permutations. I don't have a rigorous proof, but it seems that probability of false-positive / one iteration is at most 50/51.

→ Reply

desert97

9 years ago, # |

← Rev. 3 →

+92

Look here!

EDIT1: Looks like he indeed deleted the topic. I'm glad I took the screenshot!

Also a screenshot in case he deletes it.

http://prntscr.com/b8nulc

→ Reply

9 years ago, # ^ |

← Rev. 5 →

-187

Yeah I made that. Didn't expect anyone to reply in contest. And exactly that happened..

EDIT: If you regularly use AoPS, you would know that replies start turing in at least a day from making the post..

EDIT2: Post was made in contest. Just around when 10 minutes or so of coding phase remaining.

EDIT3: Checked carefully. Post was made 12 minutes before end of coding phase

→ Reply

sampriti

9 years ago, # ^ |

+46

Why do you need replies on AoPS, you could have waited for the editorial :P

→ Reply

9 years ago, # ^ |

← Rev. 2 →

-124

Because that is a pure maths problem. And there can be much better discussion on a math forum. Either way, Topcoder problems are seldom discussed anywhere.

→ Reply

sampriti

9 years ago, # ^ |

+15

Legit.

→ Reply

I_love_Tanya_Romanova

9 years ago, # ^ |

← Rev. 2 →

+55

Why wouldn't you wait one more hour in order to create that AoPS topic after TCO round? :)

→ Reply

9 years ago, # ^ |

← Rev. 2 →

-33

Yeah, seems unfair. Topcoder admins could remove me if that seems more fair. Anyway, if my intent would have been to cheat, I wouldn't have posted it under my usual handle..

→ Reply

Errichto

9 years ago, # ^ |

+29

It's bad to intend to cheat. It's forbidden to cheat. You did the latter one, unfortunately.

→ Reply

Errichto

9 years ago, # ^ |

+72

"Yes, I asked for help in the Internet during the contest. I didn't expect the answer though, so it's fine, right?"

→ Reply

9 years ago, # ^ |

← Rev. 2 →

-45

I am not sure how one would expect someone on a forum to be able to solve a problem in 12 minutes, post the solution, and then me to be able to read it, understand it, and then code it. I honestly just wanted to know the solution(and was also thinking of getting some contrib on AoPS). I don't know if there is some way I could prove my innocence. :/

P.S. Already had a lot of contrib-- on CF. Please don't down vote and understand my view point. :/

→ Reply

viesis

9 years ago, # ^ |

Whispering: I think you just wanted to get the solution idea for hacking purpose, which could lead you to qualify for next rounds.

→ Reply

9 years ago, # ^ |

← Rev. 4 →

I have nothing to say. I just applaud the ability of CF community to be completely biased against someone and not even think about this from someone else's perspective and de motivate them completely. If I really just wanted to cheat, why would I do so at the end of the contest. Using my own fucking handle. But this'll also probably just get down voted, so its no use trying to explain. I am just sorry about this. I won't do something like this again. Thats all I can say. :/

It's just really saddening for me. All of this happened because of my impatience. Lesson learned, be patient and wait for end of contest. I guess I was just frustrated of being unable to solve anything. Anything and everything I did do and will do in the future will simply be labeled as cheating. Even though I had no such intents. I feel really sad.

→ Reply

YourRatzon

9 years ago, # ^ |

I think you are great for apologizing publicly, you get my upvote :)

→ Reply

9 years ago, # ^ |

+47

That's one of the lamest excuses I have ever heard xD

→ Reply

9 years ago, # ^ |

← Rev. 4 →

+21

Correct me if I'm wrong, but it sounds like you think it's OK to post a problem from an active contest to a problem solving forum? Isn't that explicitly disallowed? From the topcoder rulebook:

Collaborating in any way with anyone else (member or not) during a rated event is considered cheating. This includes discussing problem statements or solutions between the time that the coding phase begins and the time that the challenge phase ends.

→ Reply

9 years ago, # ^ |

-26

No I do not. I am sorry if this comes of as cheating. It is actually a clear violation of rules, so I should rather just be disqualified. But I just wanted to be clear that I did not intend to cheat. Nor did I mean to break any rules. AoPS would never have replies in less than 24 hours unless topic is really hot.

→ Reply

moussai

9 years ago, # |

← Rev. 2 →

Check out LayCurse's 300 point solution. How can you write something out like that and not make a mistake? The lines aren't even the same structure where you just paste and change variable names.

→ Reply

zholnin

9 years ago, # |

← Rev. 2 →

+80

I start to like those rounds.

Round 2A — solved nothing, hacked nothing, rating goes 1395 -> 1398

Round 2B — solved nothing, hacked nothing, rating goes 1398 -> 1402

How more do I need to become red? :D

→ Reply

9 years ago, # ^ |

+31

Solved nothing, hacked nothing, 2606->2456

I fear that limit of that sequence is below red :P.

→ Reply

9 years ago, # ^ |

Can confirm. 1793 -> 1679 over the last two rounds.

→ Reply

eddy1021

9 years ago, # ^ |

+30

I'm also solved nothing, hacked nothing, 2091 -> 2153....

There's even no any submission in my room(in parallel round).

→ Reply

9 years ago, # ^ |

Seriously though, quality of problems aside, isn't it a bad contest if there is only differentiation between 122 contestants (of 734)?

→ Reply

zholnin

9 years ago, # ^ |

← Rev. 4 →

I would say "YES, it is a bad contest". But sometimes it is difficult to estimate difficulty. :). So sometimes it happens :)

And the first problem A proved to be simple — it's just (as posted by Egor above):

f(A) + f(B) + f(C) - f(A - B) - f(A - C) - f(B - C) where f(X) = 0 + 1 + ... + X(X - 1) / 2

How much simpler can it be? :) It's intuitive :)

→ Reply

9 years ago, # ^ |

There are a lot of hard problems with simple solutions. Anyway, I'm not saying the 300 was a bad problem. Quality of problems aside, the last two contests have only differentiated between the top 10% of participants.

→ Reply

zholnin

9 years ago, # ^ |

I agree — it was a good problem. And problem A should be submitted (doesn't mean solved) by at least 50-75% of participants. Didn't work out this time. Ok, last two times.

→ Reply

fruwajacybyk

9 years ago, # ^ |

For a regular SRM round — yes problems were too hard. But the main purpose of the contest was to choose top 40 to advance, and 500 people with 0 is OK.

It is defnitely better than 150 people with 300 and 500 solved, and the question is who codes faster.

→ Reply