VK Cup Round 3 + неофициальные интернет-трансляции

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

← Rev. 2 →

+145

Why should strong div2 participants have better chances for a t-shirt than medium div1 participants? Also, t-shirts for div2 may cause cheating (div1 guys participating with other accounts).

→ Ответить

Fast_and_Furios7

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

+98

At least making a combined round makes more sense , bringing everyone to compete for t-shirts is a better choice.

→ Ответить

C137

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

+54

become div.1

→ Ответить

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

+32

I agree that combined rounds are good when it comes to prizes. Though, there are other factors then. Two important ones are that (1) problems may not fit such a round at all, and (2) hacking is more random.

Maybe div2 participants should treat usual rounds as a fight for t-shirts — good results will allow them to compete in div1 contests with prizes.

→ Ответить

Um_nik

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

+78

Ehm, yes. The idea is the 50 best guys gaining T-shirts. If you are in div.2, you cannot be the best by definition.

→ Ответить

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

+33

You can have 1899 rating, after a failed contest, where you got -250

→ Ответить

-Wave-

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

+10

If you are good enough to get top 50 in div 1, it's extremely unlikely that you would ever drop to div 2.

→ Ответить

WasylF

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

+12

but a lot of strong div1 coders take part in official Round3:)

→ Ответить

Um_nik

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

+24

Unlucky man. But it is your fault.

→ Ответить

I_love_Tanya_Romanova

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

← Rev. 2 →

+23

Just curious — if someone qualified for round 3, but decided to participate in div1 mirror instead of main round, in case of making into top50 there he'll get two VK Cup t-shirts?

→ Ответить

Infoshoc

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

← Rev. 2 →

Thought about it, if only I were powerful enough :) :(

→ Ответить

WasylF

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

← Rev. 3 →

+19

bug or feature?

there is 88 teams and 168 participants...

UPD: for now 73 teams and 134 participants, looks real:)

→ Ответить

egor.okhterov

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

No, there are teams with a single participant.

→ Ответить

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

← Rev. 3 →

+30

Or some participants are in many teams.

EDIT. Maybe as an organizer I shouldn't make fun in comments. To make things clear: my comment isn't serious. #politicalcorrectness

→ Ответить

noelnadal

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

I already reported that "bug" (also seeable in unofficial contests). I once thought that the number in the "Contests" page also involves people that unregistered later, but I may be wrong.

→ Ответить

Deathly_Hallows

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

i'm already registered in DIV2 round but my name doesn't appear in registrants list ?

→ Ответить

Ahmad

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

← Rev. 2 →

Is there a problem with the registrants page? Cause on the contest page it says:

But on the actual page it says:

Hoping the 2500 number is accurate but would there be a problem with contestants that aren't on the registered page? Would they be able to submit in the contest?

→ Ответить

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

← Rev. 2 →

I was outvoted to post the scoring. So, check out a new update (in the blog).

EDIT: someone is working on the registration issue.

→ Ответить

ballon

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

← Rev. 2 →

+12

Зарегистрировался.
Через несколько часов обнаружил, что мы больше не зарегистрированы.
Зарегистрировался ещё раз.

Только у меня так ?

→ Ответить

Guliash

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

Нет. Точно помню, что регистрировался с утра. Но пришлось зарегистрироваться заново сейчас.

→ Ответить

Amareelez

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

→ Ответить

http://codeforces.net/blog/entry/4088

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

+26

There is a bug with showing participants list, and may be it's something legated with teams

→ Ответить

eatmore

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

+46

Я понимаю, что участники не читают соглашение об участии, но почему его не читают те, кто его пишут?

Текст

Регистрируясь на соревнование, вы подтверждаете, что каждый член вашей команды:

* удовлетворяет правилам чемпионата со страницы http://codeforces.net/blog/entry/23607;
* ознакомился с правилами соревнований на по ссылкам http://codeforces.net/blog/entry/456 и http://codeforces.net/blog/entry/4088;
* не будет нарушать правила, описанные в http://codeforces.net/blog/entry/456 и/или http://codeforces.net/blog/entry/4088;
* не будет общаться с кем-либо кроме членов команды, обмениваться идеями решений, взломов;
* будет использовать только полностью написанный командой код за исключением кода, попадающего под исключения, описанные в http://codeforces.net/blog/entry/8790;
* не будет пытаться осуществлять намеренные попытки по дестабилизации процесса тестирования и пытаться взломать систему соревнований в любой форме;
* не использует несколько аккаунтов, а в соревновании принимаете участие со своего личного и единственного аккаунта.

Во-первых, адреса всё ещё ведут на codeforces.ru, с которым мы попрощались уже почти год назад. Во-вторых, какое отношение ко мне имеет первый пункт, если я регистрируюсь на интернет-трансляцию? И вообще, когда это "соглашение" наконец сделают нормальным шрифтом и с кликабельными ссылками?

→ Ответить

cdkrot

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

Там ещё две ссылки одинаковые =)

→ Ответить

MPeti

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

+35

The difficulty jump from Div2 D to E and F seems huge... Kinda sad that speed and hacking is going to determine most of the Div2 results, even if it seems like I'll be at the top of the 4-task-solvers.

→ Ответить

Omar_Mekkawy

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

Yes E so hard :'(

→ Ответить

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

Yea, same feelings.

→ Ответить

anh1l1ator

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

+10

I think every VK round has erratic jump of difficulty due to the fact they aren't originally meant for Div2.

→ Ответить

harryapotter

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

Complete problem D and thinking about sleep :)) :))

→ Ответить

Emruz_Hossain

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

+30

I made someone angry and then...

→ Ответить

prrateekk

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

Yup we were in the same room.... I don't know what was on his mind....he tried to hack mine too a lot of times!

→ Ответить

-is-this-fft-

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

Likely one of those guys like .o..

→ Ответить

aurinegro

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

-15

I think it's clear he wasn't happy with his perfomance and he "hacked himselft out of the contest". If you have negative score, the contest is unrated for you, or at least it used to be that way.

→ Ответить

kpw29

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

+26

It's not true. I've checked it today? Effect? -120 :)

→ Ответить

aurinegro

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

-15

Yes, it seems they changed that. I think this a much more reasonable policy. But there should have been a notification about this (I searched and didn't find it anywhere).

→ Ответить

Zlobober

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

It never was like you describe. Even having an ultra-negative score always affected your rating.

→ Ответить

aurinegro

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

← Rev. 2 →

Okay. Sorry for mixing things up. I was definitely mistaken. Don't know how I came up with that, I was sure I had read it somewhere.

→ Ответить

kpw29

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

I've also heard about it. Maybe there was such a bug (feature :D) a long time ago. We should probably ask Mike whether it's just a social myth

→ Ответить

Kvark161

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

Прикольно, когда пытаешься взломать чувака, получаешь "Неудачная попытка взлома"

Time: 1981

Memory: 2465792

Переписываешь его решение, запускаешь в "запуске", а там стабильно 2100 мс =(((((

→ Ответить

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

What is the hack for Div2D?

→ Ответить

Kvark161

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

← Rev. 2 →

4 5

1 2 3 4

→ Ответить

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

Answer is -1?

→ Ответить

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

Yep.

→ Ответить

Kvark161

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

yes

→ Ответить

eanacra

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

My hack was n=4. The answer should be -1.

→ Ответить

hloya_ygrt

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

n == 4

→ Ответить

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

What was the hacks for Div2A and Div2B?

→ Ответить

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

+14

Some guy in my room was outputting 2^(max — min — 1) and that passed pretests.

→ Ответить

arpn

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

I didn't even submit a single problem and there it was the lock button for problem B. Must be a bug.

→ Ответить

Lo_R_D

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

+17

"Простые задачи? Зачем!"

→ Ответить

I_Love_Tina

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

What's the idea for div1 C?How to calculate the expected value on a interval?

→ Ответить

Nezzar

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

← Rev. 3 →

+19

P.S. didn't get AC on C, but I think the cost function is correct

cost(L, R) = cost(1, R) — cost(1, L — 1) — sum_of_1/a(L, R) * sum_of_a(1, L — 1)

idea: cost(L, R) = t_L / t_L + (t_L + t_(L+1)) / (t_(L+1))... =t_L * (1 / t_L + 1 / t_(L+1) + ..) + t_(L+1) + ...

which then becomes much easier to see

→ Ответить

anh1l1ator

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

And then do a segment tree or something?

→ Ответить

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

The editorial is posted.

→ Ответить

ace_pocket

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

how to divide them in K regions??

→ Ответить

Noureldin

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

← Rev. 2 →

let :

S1[k] be sum of T[i] for i = 1:k

S2[k] be sum of 1/T[i] for i = 1:k

S3[k] be sum of S1[i]/T[i] for i = 1:k

then the expected time to finish the interval s->e is S3[e] — S3[s — 1] — S1[s — 1]*(S2[e] — S2[s — 1])

from that we can turn it to a dp + convex hull optimization problem ...

PS : my code fails test 14 — I should practice convex hull optimization more :'(

→ Ответить

SaveVMK

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

How do you avoid floating point errors with 1C/2E?

→ Ответить

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

Don't use any epsilons. Use long doubles if you want to be more precise.

→ Ответить

satyaki3794

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

Why not epsilon? Is this a common problem (that you shouldn't use epsilon)?

→ Ответить

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

+15

Why would you use epsilon here? What would you try to avoid/achieve?

→ Ответить

DmitriyH

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

+37

На мой взгляд, очень не хватало подзадачи DIV1 C, в которой бы проходил k*n*n.

→ Ответить

dush1729

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

Please allow practice.

→ Ответить

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

After the system testing.

→ Ответить

I_love_Hoang_Yen

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

+57

Please start system testing =)

→ Ответить

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

Mike and/or Gleb must work a bit after each round, to manage hacks and any issues. I'm sure they don't try to be slow to annoy all participants. You must wait a bit. In the meantime, you can check the editorial.

→ Ответить

DoubleNy

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

The B,div 2 is maximum bipartite matching?

→ Ответить

areke

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

← Rev. 2 →

Nope, it's much simpler! The lower problem in each pair must be the div 2 problem. You just need to find the maximum div 2 problem and the minimum div 1 problem, then take the difference.

→ Ответить

wineColoredDays

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

In div2 D, input :

7 11
2 4 7 3

output
2 7 1 3 5 6 4
7 1 2 4 6 5 3

Why is this output incorrect ?

→ Ответить

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

There can't be road between a and b.

→ Ответить

eduardische

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

Edge 2 — 4 is present in the second line.

→ Ответить

areke

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

In the second line, the 2 and 4 are directly connected by a road (right next to each other). The problem statement said that was not permitted.

→ Ответить

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

You can't have roads between A and B or C and D.

You have road between A and B in second route.

→ Ответить

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

There can't be direct edge from 2 to 4.

→ Ответить

giraffeh

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

There shouldn't be a road between towns a and b. In your second line of output you has got such road.

→ Ответить

allllekssssa

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

← Rev. 3 →

After one hour and solving the first four tasks, next two hours were like a fishing. I was trying to catch some wrong submission and I didn't manage in it :)

→ Ответить

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

+10

I'm sure you are all wait for the system testing. So maybe you have time to give the feedback. Which problems were good/bad and what could be better? Something too easy or hard? Too mathy? Too not-mathy?

Someone already said that there was a big gap between div2D and div2E. It may be true. Do you agree? Other opinions?

Seriously, your feedback will make future contests better.

→ Ответить

notAboAlmanalAnyMore

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

I think B problem shall be C and C shall be B in div 2 contest .. thx at all

→ Ответить

IHaveInt

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

yeah , there was a big gap ... but I liked the div2 E problem :D

→ Ответить

areke

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

Yeah, it seems as though there was a ginormous gap between the two. I didn't really think much about the E problem though because I've never been able to solve an E problem during a contest. I went straight to try hacking :P (although I wasn't very successful).

In general, I liked all the other problems though!

→ Ответить

DmitriyH

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

← Rev. 2 →

+21

Duplicating my russian comment in english: it would be nice to have a DIV1 C subproblem, which could be solved in O(nnk).
There were a huge difficulty jump between AB and the others.
UPD: so, if you are not red, then after solving AB problems in 30-60 min, there is nothing to do in remaining 2 hours, except reading other problem statements and trying to hack someone :)

→ Ответить

Noureldin

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

it would be great if you lower the accuracy of DIV2E/DIV1C and rejudge all submissions :'D

→ Ответить

Enchom

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

I was stuck at Div1 C so I didn't read Div1 D, however it seems that Div1 D was seriously underestimated. Before system test, judging by successful submissions amount — it seems to be the hardest problem.

→ Ответить

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

I was also thinking that Div1 D is simpler that C, and started it, but only 10 persons solved it so far in all 3 contests >.<

→ Ответить

kpw29

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

+76

[TL;DR] => too many queries / expected value ;)

[Div 1] Two first problems were like a warmup, almost everyone solved them.

But then? [A, B, . . . . . . . . . . . . . E, C, F, G, D(wtf) ]

Looking at the problems :

*easy problems *

-Shieet, expected value.

-Oh god, queries.

-Expected value!!!11

-Hidden queries.

-Even more queries!!!

My opinion: Too many queries and expected value :) And almost every one of the C — G problems required DP (maybe with maths) , it is always nice to see a varying problemset with flows / graphs / strings (or even geometry ^^).

This is only my opinion, please don't dovnvote just because you don't agree with it ;)

→ Ответить

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

← Rev. 2 →

+10

The number of upvotes you got means that many agree with your comment. I see that there was too much DP, and maybe too much expected value. But I don't understand one thing — what is wrong with queries? Is it that they make a problem less elegant and nice? Because not all problems with queries are about the same topic.

Would the following version of 643E - Bear and Destroying Subtrees be better? It has no queries (does it make the problem nicer?). The tree is given and there are no queries at all. We consider removing each edge with prob. 1/2. What is the expected value of the height after the process, modulo 10⁹ + 7.

solution

→ Ответить

greedyTaiga

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

Yeah,there was huge gap between these problems.In addition C was too easy , I think it would be better if it was problem B.

→ Ответить

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

Imo C is harder than B. Only problem with B was a bit overcomplicated statement :)

→ Ответить

FatalEagle

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

+54

In my opinion, the pretests for problems which greatly affect standings (for today's contest, it's all problems after div1B) should be nearly identical to final tests, that is to say all corner cases should be present. It's definitely a frustrating bug to drop 70+ places because

for(int j=1; j<i; j++)

should be

for(int j=i-1; j<i; j++)

Before you say "but what about hacks", I'd like to point out pretty much nobody is going to hack a problem with more than a few lines of code. Indeed, there were no hacks on C, D, E, F, or G of div1 contest.

→ Ответить

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

I think that we tried to make pretests strong in hard problems. I think that the only exception was a problem about the expected height of partly-destroyed subtree. (There, I thought there would be hacks requiring big value of MAX_H.) About which problem are you talking?

→ Ответить

FatalEagle

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

I failed Div1 C because my DP formulation considered splitting n levels into more than n parts, which obviously causes bad things to happen. Any test where n = k and n >= 3 will cause my program to output a value smaller than n. Adding two characters would fix this :(

→ Ответить

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

+20

It's hard to be so careful about pretests. Still, I see your point and I'll try to consider it in the future. Thank you.

→ Ответить

rhezo

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

In division 2 C, why was index written in brackets. All the while I thought only about index of the lowest tied color :| Rank dropped by at least 200. :(

→ Ответить

desert97

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

+20

This isn't that important, but I would prefer if the problem statements seemed more "natural" in some sense, maybe something that I would naturally be interested in, not too contrived statements, etc.

I thought A was OK in this respect. B was ehh, the condition that ab, cd aren't edges is slightly unnatural. C was pretty unnatural, in the statement of the game, etc. I didn't try D, E, G so no comments here.

F is a decently natural statement I thought, if you think about the problem mathematically.

Tell me if I confused you...

→ Ответить

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

+14

It's a very important thing in my opinion. Statements are a huge part of the contest. Initially, in B there was something like "Limak wanted to get from a to b. Unfortunately, there was no direct connection. So, he will be late anyway for some event and at least he will take a long nice walk. He then went to b, visiting all cities during his walk. On the other day, ...". It's easier to understand the story but the cost is that the statement is (much) longer. The current version is much shorter than the previous one, with some background. I was advised not to write long statements for this contest and I think it's better. For example because some people aren't fluent in English. So, maybe shorter precise statement is better than longer natural one. But still, I left some story. I will gladly hear more opinions about it.

But generally, it's hard to invent only natural problems. I can do nothing about the fact that C was unnatural for you. I thought it's still better that only definitions ("split sequence to maximize the score defined as ..."). But some problems are just artificial. I know I will never be able to produce only non-artificial stories and problems (enough of them to make contests).

→ Ответить

Diego1149

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

-10

I was expecting to solve more of the problems and it just feels bad to solve 2 and one of them didn't pass system tests, so I got a beautiful 1 problem accepted. I think that is because the difficulty gap between first 2 and all others was too high, if there are going to be 7 problems, I would expect the average to solve 3-4, if there are going to be 5, then 2 or 3 is nice, I just think that a minor mistake shouldn't move you more than 100 places, or 170 in my case, around half of the people that participated in div1.

→ Ответить

DmitriyH

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

-10

It would be interesting to know: is "34 accepted solutions for D-G problems" near with expected estimation of AC ratio for this problems before contest?
What is ideal AC ratio in your opinion? (e.g. A 50%+, B 25%+, C 12%+, ...)

→ Ответить

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

+15

It's hard to estimate these numbers before the contest. I'm only sure that we considered div1C (CHT) and div1D (Fanpages) to be easier than they turned out to be. I think that the number of AC's in other problems is fine.

→ Ответить

adamant

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

Please enable upsolving immediately after systests...

→ Ответить

DoubleNy

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

How to solve div 2, C ?

→ Ответить

noelnadal

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

Editorial : http://codeforces.net/blog/entry/44754

→ Ответить

Fcdkbear

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

Can anyone explain the idea of recalculating all of the probabilities in Div1 E? Thanks

→ Ответить

ko_osaga

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

+17

Impressive performance of .o. in Div2! My NBHEXT expects +401 for him >_<

→ Ответить

gfonn

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

-12

Wow! So accurated! He did +411! O.O

→ Ответить

sinhashubham95

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

-16

round was rated or unrated ??

→ Ответить

satyaki3794

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

It is mentioned in the blog post. "All of them are rated"

→ Ответить

kefaa

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

← Rev. 3 →

My solution in Div1C adds each of n lines in CHT after calculating DP for some k.
How to prove that the best line for i (when I calculate dp[i][k + 1]) will not have some index j > i?
It is not obviously for me but it passed systests. I even tried to change the order of addings but it didn't pass pretests :D. Or maybe weak testcases are the reason of my Accepted :D? 17793170

→ Ответить

polingy

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

We have dp[i][k + 1] < dp[i][k], and $\text{[math]}$ . I'm not sure this is sufficient to show more rigorously that adding further indices will not affect the answer, but it seems to make it intuitively clear.

→ Ответить

kefaa

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

Thanks, I've got it.

→ Ответить

Stetsyk

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

For your CHT you need to put lines in increasing by angle of line order.

→ Ответить

Sun_For_Life

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

А знает ли кто-нибудь, почему так долго пересчитывается рейтинг?(уже после компиляции)

→ Ответить

anubhav94

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

My Div1-C timed out since I was using cin for input. Changed it to scanf and passed. :(

cin : http://codeforces.net/contest/674/submission/17792111

scanf: http://codeforces.net/contest/674/submission/17797745

→ Ответить

saisumit

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

Its happened first time with me this is my Div2 D soln which was hacked — > http://codeforces.net/contest/673/submission/17796235 after contest i submitted this code again — > http://codeforces.net/contest/673/submission/17798097 ( which got accepted ! and the test case on which my code was hacked seems to give correct result ) Am i missing some thing or is it just my hard — luck ??? → Reply

→ Ответить