Single Round Match 633

→ Обратите внимание

До соревнования
Codeforces Round 986 (Div. 2)
05:23:23
Зарегистрироваться »

*есть доп. регистрация

→ Трансляции

Codeforces Round 986 (Div 2) - Solution Discussion

Shayan

До начала 07:28:22

Всё →

→ Лидеры (рейтинг)

№	Пользователь	Рейтинг
1	tourist	4009
2	jiangly	3821
3	Benq	3736
4	Radewoosh	3631
5	jqdai0815	3620
6	orzdevinwang	3529
7	ecnerwala	3446
8	Um_nik	3396
9	ksun48	3388
10	gamegame	3386

Страны | Города | Организации

Всё →

→ Лидеры (вклад)

№	Пользователь	Вклад
1	cry	164
1	maomao90	164
3	Um_nik	163
4	atcoder_official	161
5	-is-this-fft-	158
6	awoo	157
7	adamant	156
8	TheScrasse	154
8	nor	154
10	Dominater069	153

Всё →

→ Найти пользователя

→ Прямой эфир

Детальнее →

Блог пользователя chrome

Single Round Match 633

Автор chrome, 10 лет назад, перевод, По-русски

Сегодня состоится Single Round Match 633 в 19:00 по Московскому времени.

Давайте обсудим задачи после контеста.

UPD: Задержка на 15 минут

srm, single round match, topcoder

chrome
10 лет назад
54

Комментарии (54)

Написать комментарий?

ErzhaNN

10 лет назад, # |

Удачи всем! Думаю что все напишет хорошо.

→ Ответить

EG0R

10 лет назад, # ^ |

Фантазия закончилась?

→ Ответить

ErzhaNN

10 лет назад, # |

сорри напишут :D

→ Ответить

Madiyar

10 лет назад, # |

SRM 633 — Brought to you by Google :).

→ Ответить

Gogis

10 лет назад, # |

Anyone's going to compete in Div. II ?

→ Ответить

Killever

10 лет назад, # ^ |

Most of Div2 users will compete in Div2 :D

→ Ответить

Gogis

10 лет назад, # ^ |

← Rev. 2 →

Glad to hear it :D I asked, because I have only seen Div.I problems discussed in this posts (most of the times).

→ Ответить

Insectophob

10 лет назад, # |

Есть ли там dead-line для регистрации, вроде запрета регистрации в последние пять минут на CF?

→ Ответить

chrome

10 лет назад, # ^ |

Вроде 5 минут до контеста

→ Ответить

kolesov93

10 лет назад, # |

+10

У меня у одного не запускается арена с диагностикой:

Attempted to download http://www.topcoder.com/contest/classes/7.0/log4j-1.2.17.jar, but failed to connect!

Ubuntu 14.04.

→ Ответить

nic11

10 лет назад, # ^ |

+19

Я обычно в таких случаях пробую почистить кэш

$ javaws -Xclearcache

и заново скачать арену.

→ Ответить

kolesov93

10 лет назад, # ^ |

Спасибо, помогло.

→ Ответить

Lord_F

10 лет назад, # ^ |

← Rev. 5 →

arena.topcoder.com ?
Почему все это не нормальная ссылка, а на несуществующий блог CF?

→ Ответить

bayleef

10 лет назад, # ^ |

Попробуйте вставить в начале http: Topcoder arena

→ Ответить

EG0R

10 лет назад, # |

Спасибо что напомнил. А то я и забыл как-то.

→ Ответить

ivplay

10 лет назад, # |

Is there anyone facing problem with launching arena or doing registration? I can't launch my arena. I have downloaded the latest one. it shows a lot of exceptions when I try to launch it :(

→ Ответить

Gogis

10 лет назад, # ^ |

Try to clear your java cache.

→ Ответить

I_love_tigersugar

10 лет назад, # |

← Rev. 2 →

Contest delayed 15 minutes :((

→ Ответить

JohnPaulII

10 лет назад, # |

← Rev. 2 →

+27

Good job Topcoder!

numerOfScrewedUpContests++;

→ Ответить

HandIeNeeded

10 лет назад, # ^ |

I considered this contest a good one for me. Happy to go back to yellow. :)

→ Ответить

Swistakk

10 лет назад, # ^ |

He meant that some contestants weren't assigned a room, contest was delayed and challenge phase was delayed even more.

→ Ответить

ilyakor

10 лет назад, # |

← Rev. 2 →

Awesome problems! How to solve 600? I've tried iterating over the node which is then called "root" in both trees, taking "tree1 + inverse_arcs(tree2)" and solving "max-weight strongly connected subset problem" there. It seems that this should somehow be reduced to max-flow, but I didn't figure out how :(

→ Ответить

yarrr

10 лет назад, # ^ |

Is is possible to solve "max-weight strongly connected subset problem" in poly time?

→ Ответить

ilyakor

10 лет назад, # ^ |

I don't know about general case. But in this case, it is apparently possible, because (as pointed out below by azizkhan and Petr), if we also reverse the arcs of the first tree, we'll get max-weight closure problem.

→ Ответить

azizkhan

10 лет назад, # ^ |

← Rev. 2 →

+13

After you fix the root, the problem is finding the max weight subset which contains that root. Now you have 2 rooted trees. Let's build a network as follows: For each vertex v add a directed edges from it to its parents with infinite capacity in both trees. For each vertex v, where score[v] >= 0, add an edge from S to v with capacity score[v]. For each vertex v, where score[v] < 0, add an edge from v to T with capacity -score[v]. It can be shown that the answer is sum of positive scores minus minCut between vertices S and T.

P.S. My solution is failed because I have a bug in MaxFlow algorithm

→ Ответить

Petr

10 лет назад, # ^ |

+29

After we've picked the root, then our condition boils down to: if we take a vertex, we need to take its parents in both trees.

If we have a set of conditions "if we take X, we must take Y" we can apply min-cut by adding an infinite edge from X to Y — this way if we take X, we must take Y :) The only remaining part is choosing weights for edges from S and to T so that the weight of the cut is const+answer.

→ Ответить

add1ctus

10 лет назад, # |

+28

Woah, I just finished first in Div 2, had to share this somewhere.

I solved 250 and 500 (but not very fast), and then in the challenging phase I noticed a guy has only return "Solution exists" in this code. One guy tried challenging him, but accidentally entered a "solution exists" test and got a wrong challenge. I did that mistake too, but I was faster for the second challenge and got 25 off him. Then I noticed his 500 was also a return, I challenged it, and for the 250 he tried entering all possibilities manually, but only did it until 19, so I challenegd that one for a total of 125 from that guy.

Then I found two more wrong 500 solutions (one timed out, one had a flaw) for 100 more points.

→ Ответить

Gogis

10 лет назад, # ^ |

Did you advance to Div. 1 ? I spent most of the time debugging my 250 and got only something like 100 points for it and then there was no time left to solve 500...

→ Ответить

add1ctus

10 лет назад, # ^ |

I sadly didn't. My first SRM was a complete blowout (two wrong solutions with very dumb mistakes and two wrong challenges) so I started with 300-ish rating. I advanced from 771 to 1136 this round.

→ Ответить

Gogis

10 лет назад, # ^ |

That's quite a jump anyway, congrats :D I'm like much more stable, my rating is always >= 900 && <= 1100.

→ Ответить

nic11

10 лет назад, # |

← Rev. 4 →

Правда ведь в див1 250 множество достижимых за K шагов точек — окружность/бублик/круг? Что тогда с тестом?

3)
-10
{2,3,4,500,6,7,8}
Returns: 11
Когда вроде 4 прыжка достаточно вполне. В чем же подвох?

UPD. Все, понял. Надо уметь пересчитывать внутренний радиус, он не всегда тривиально считается.

→ Ответить

beatoriche

10 лет назад, # |

I wonder which is Div 1 Easy which has the least % accepted. I remember Nickolas' AgeEncoding had very low acc rate.

→ Ответить

I_love_Tanya_Romanova

10 лет назад, # ^ |

AgeEncoding had 9.17% — very low AC rate; at least it should be lowest one during last few years:)

And sometimes all 6 problems have low AC rate, like in SRM 438.

→ Ответить

selfcompiler

10 лет назад, # |

Would anyone like to explain the problem of DIV-2 ,500 POINTS, 1000 POINTS how to solve both of these problem ?

→ Ответить

add1ctus

10 лет назад, # ^ |

Div 2 500 :

Let's look at the first test sample : We need to get to (5,4) with steps of distance 2 and 5. Using Euclidean distance we find the distance from the goal (5,4) to the start (0,0). In this case, the distance is 6.4. We also take a sum of all the steps. In this case, the sum is 7. If the sum is less than the distance, then you are not able to reach it in any way. Also, if the sum is equal to the distance, you are 100% able to reach it (just jumping directly towards the goal). Otherwise, we have this situation :

We try to represent the path as a triangle, one side is the distance, the other sides are the steps you have in the input. For triangles, there's the following rule:

a < b+c

b < a+c

c < a+b

Otherwise stated : Every side of the triangle must be smaller than the sum of all other sides. If this is valid, then you return "Able", otherwise you return "Not able". This "theorem" is also valid for all other polygons. For example, if we had 4 sides, it would be :

a < b+c+d

b < a+c+d

c < a+b+d

d < a+b+c

So you just have to check this theorem. Here's my solution.

→ Ответить

selfcompiler

10 лет назад, # ^ |

thanx add1ctus

→ Ответить

Eibe

10 лет назад, # ^ |

There is another way to think about this problem.

If all reachable points after k jumps are a filled ring (true for first jump which is a circle). Where do all reachable points after k+1 jumps lie? Answer: A ring with a bigger outer radius (enlarged by k+1 th jump) and a smaller inner radius (diminished by k+1 th jump but not smaller than 0). And they also fill this ring completely.

I don't have a strict mathematical prove though (I used a sheet of paper and circle to get the idea)

→ Ответить

Eibe

10 лет назад, # ^ |

oops, left out something crucial: The above is only true if jumps are in diminishing length.

But one can convince oneself that the order of jumps doesn't matter so we can start with the largest jump. Again no proof (just pen and paper to get the idea)

→ Ответить

Insectophob

10 лет назад, # ^ |

I was looking on similar solution all the Challenging, but I had no idea how it should work. Thanks a lot for your explanation!

→ Ответить

xpertcoder

10 лет назад, # ^ |

I am always confused about this one.Can you tell me while you are comparing sum and distance why are you doing this

abs((double)sum-distance)<0.00001

and not this

abs((double)sum-distance)< numeric_limits<double>::epsilon()

How can one decide that factor while comparing two doubles?

→ Ответить

Mukit09

10 лет назад, # ^ |

← Rev. 3 →

We know, a triangle is valid, if
a < b+c
b < c+a
c < a+b
so, triangle with length {1,2,3} is not valid, as 3 < 1+2 isn't true. So in general, if a side is equal to summation of other side of a polygon, then this polygon isn't valid. Right ?

Now in your code:

double temp=sum+distance;
        for(int j=0;j<jumpLengths.size();j++)
            if(temp-jumpLengths[j]<jumpLengths[j])
                return "Not able";

Here, why you don't need to check if temp-jumpLengths[j]is equal to jumpLengths[j] ?
I coded like this comment(I returned "Not able" if temp-jumpLengths[j]<=jumpLengths[j]), but there is a input {1, 0, {100, 101}} for which my code returns "Not able", but judge says, "Able". From (0,0) to (1,0) distance is 1. If I think the input is a triangle with the length of {1,100,101} then 101 < 100+1 isn't true. So output should be "Not able". Shouldn't be it ? Please, clear me...

→ Ответить

add1ctus

10 лет назад, # ^ |

Woah, this is actually a mistake on my end, and a lucky one (because if I didn't do that mistake, my answer would have been wrong).

The problem with that theorem is that it is only valid for valid triangle. In the case of sides 1, 100 and 101, we have two angles of 0 degrees and one angle of 180 degrees. That is an invalid triangle, but it is a valid jump sequence. Removing the '=' will make sure that you count those jump sequences as well.

→ Ответить

Mukit09

10 лет назад, # ^ |

Humm got it... Thanks... :)
But it was really a tricky one and most probably the cause of too many system test failure is this case... :/
how lucky you are !!! :P :)
congratulation for division 2 winning ... :)

→ Ответить

akashdeep

10 лет назад, # |

Rank 3 goes to egor in both the divisons :)

→ Ответить

Swistakk

10 лет назад, # |

Div1-1000pts after considering each prime individually boils down to that problem
Is there an assignment for a[1], ..., a[n] such that some constraints of form max(a[i], a[j]) = c and min(a[i], a[j]) = d are fulfilled? If for particular vertex those constraints are contradictory, we return "NO". If not, then we can fulfill max edges with lowest label ot min edges with highest labels and we create a boolean variable for this. What is left to do is to check whether 2SAT is satisfiable (which can be very easily done since contraints are small — just check if there is vertex v such that there exist paths v->!v and !v->v)

→ Ответить