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

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

Привет всем!

Не хотите ли Вы потренироваться перед предстоящим контестом ACM/ICPC Finals?

Codeforces Round #190 пройдет в пятницу, 28-го июня, в 19:30 MSK. Это последний шанс потренироваться перед финалом, не упустите его!

Я cgy4ever из Китая, и это мой первый раунд Codeforces. Я надеюсь, он понравится вам.

Как обычно, будет 7 задач: 2 для Div2, 2 для Div1 и 3 для обоих дивизионов. Я готовил эти задачи. Хотелось бы поблагодарить Gerald и sdya за тестирование задач, и MikeMirzayanov за проект Codeforces и Polygon.

Удачи и фана вам на раунде!

Update 1: The score distribution for Both Division is regular (500-1000-1500-2000-2500). The main character of all problem will be: Fox Ciel. (See here for more info)

Update 2: Also thanks Aksenov239 for helping prepared this round, including translate the problem statement into Russian. And I'm sorry for the delay of judgement at the beginning of this round. Fortunately it goes better now.

  • Проголосовать: нравится
  • +347
  • Проголосовать: не нравится

»
13 лет назад, скрыть # |
 
Проголосовать: нравится +75 Проголосовать: не нравится

Hope it will be a successful Chinese round. \^o^/

cgy4ever is also a writer for topcoder, you can find problems authored by him here.

»
13 лет назад, скрыть # |
 
Проголосовать: нравится -185 Проголосовать: не нравится

Hello World!

It's my first comment on this article.
I'll write some interesting experiences and academic articles there.
I'm an OIer and maybe I'll be an ACMer latter.

»
13 лет назад, скрыть # |
 
Проголосовать: нравится +26 Проголосовать: не нравится

This is your website http://cgy.ac/ :P ;)

»
13 лет назад, скрыть # |
 
Проголосовать: нравится +21 Проголосовать: не нравится

Thank you cgy4ever for the contest! I love contests that have been made in china!

»
13 лет назад, скрыть # |
← Rev. 2  
Проголосовать: нравится +11 Проголосовать: не нравится

So many cheaters participate :D

about 250 fakes now

»
13 лет назад, скрыть # |
← Rev. 3  
Проголосовать: нравится +26 Проголосовать: не нравится
»
13 лет назад, скрыть # |
← Rev. 2  
Проголосовать: нравится 0 Проголосовать: не нравится

On seeing many fake entry I doubt of contest being rated.

»
13 лет назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится

Someone's gonna cheat today XD (look at the list of registrants)

»
13 лет назад, скрыть # |
← Rev. 2  
Проголосовать: нравится 0 Проголосовать: не нравится

If all fakes will downvote all somebody's comments he'll look like JKeeJ1e30 or worst :)

»
13 лет назад, скрыть # |
 
Проголосовать: нравится +13 Проголосовать: не нравится

All this users will be banned before the contest.

»
13 лет назад, скрыть # |
 
Проголосовать: нравится -7 Проголосовать: не нравится

I think all these fake accounts have a goal that they want to tell to MikeMirzayanov that there must be captcha or e-mail activation system at the beginning of creating account. It's completely right. Codeforces has a bad log in system too. If you want to find someone's password, it's enough to using brute force scripts or programs. Because there isn't any security protection in the log in system. In my opinion, Headquarters must build a security system to the log in part. Simply, it can be captcha or anything that can block the attackers.

PS: Sorry for my bad English. Thanks...

»
13 лет назад, скрыть # |
← Rev. 2  
Проголосовать: нравится +9 Проголосовать: не нравится

I do not like fakes, we should use codeforces to learn programming, algorithms ... in a good way.

»
13 лет назад, скрыть # |
 
Проголосовать: нравится -14 Проголосовать: не нравится

You need to look into the registration system!

»
13 лет назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится

with reference to this comment i think codeforces should set a limit of participants.

»
13 лет назад, скрыть # |
← Rev. 2  
Проголосовать: нравится 0 Проголосовать: не нравится

qswa серьезно подготовился к раунду)

upd: их всех удалили! от почти 5 тысяч осталось только 1,5

»
13 лет назад, скрыть # |
 
Проголосовать: нравится +37 Проголосовать: не нравится

Please stop spamming with your comments about fake accounts. Make a blog about it so that others could skip reading it. I want to read interesting info about the round here. Minuses to all spammers.

»
13 лет назад, скрыть # |
 
Проголосовать: нравится -29 Проголосовать: не нравится

why so much new ????

»
13 лет назад, скрыть # |
 
Проголосовать: нравится -34 Проголосовать: не нравится

Изначально хотел ответить на этот комментарий в той же ветке, но потом передумал писать, потому что та ветка не на русском языке.

И как, собственно, вы сможете понять, какие из аккаунтов фейковые? Вы обратили внимание на эту "акцию" (не мою). И каков ваш ход? БАН ВСЕМ? Окей, может быть все они зарегестрированы с одного ip-шника, и отследить это будет просто. Но это в этот раз. Что будет в следующий, когда вы не сможете этого отследить? Много раз поднимался вопрос, наиболее актуальный сейчас. НИ РАЗУ вы (администрация) адекватно на него не отреагировали. Вам наплевать, что каждый див2 контест, половину верхушки таблицы занимают новые участники. Ну а что, это же второй дивизион, правда?

Собственно, к чему я веду. Ваша реакция — бан всех "этих" участников перед контестом (дословно). Да и что значит "этих"? Каких этих? Вам не кажется, что реакция не адекватна? Может все-таки стоит поделиться с сообществом мыслями на счет происходящего? Ведь нам небезразлично то, что происходит с одним из наших любимых мест в интернете.

»
13 лет назад, скрыть # |
← Rev. 12  
Проголосовать: нравится +1 Проголосовать: не нравится

О, уже забанили. Но не всех. И его блог заблокировали.

Или у всех забаненных блоги автоматически блокируются?

»
13 лет назад, скрыть # |
 
Проголосовать: нравится -32 Проголосовать: не нравится

Вот в чем вопрос: решать или не решать — все-таки made in china =)

»
13 лет назад, скрыть # |
 
Проголосовать: нравится -27 Проголосовать: не нравится

STUPID JUDGING DELAY AGAIN!!!! DAMNNNNNNNNN

»
13 лет назад, скрыть # |
 
Проголосовать: нравится -15 Проголосовать: не нравится

All the submissions are "In queue" :(

»
13 лет назад, скрыть # |
 
Проголосовать: нравится -12 Проголосовать: не нравится

длина очереди ужасает

»
13 лет назад, скрыть # |
 
Проголосовать: нравится +16 Проголосовать: не нравится

Очередь на тестирование прям как за колбасой при дефиците

»
13 лет назад, скрыть # |
 
Проголосовать: нравится -19 Проголосовать: не нравится

"In queue"... Classic Codeforces Round once again.

»
13 лет назад, скрыть # |
 
Проголосовать: нравится -24 Проголосовать: не нравится

The submission has been in queue for last 10 min or so....:(

»
13 лет назад, скрыть # |
 
Проголосовать: нравится +73 Проголосовать: не нравится

Div1 B /Div2 D is yugioh game :)

»
13 лет назад, скрыть # |
 
Проголосовать: нравится +9 Проголосовать: не нравится

Почти сразу после отправки Ашки нашел баг — переотправил, прочитал Б и... забил на контест и сделал 10 взломов :D

»
13 лет назад, скрыть # |
 
Проголосовать: нравится +22 Проголосовать: не нравится

Nice Contest!! Superb questions i love CF

»
13 лет назад, скрыть # |
 
Проголосовать: нравится +6 Проголосовать: не нравится

На каком тесте А ломали?

»
13 лет назад, скрыть # |
 
Проголосовать: нравится +8 Проголосовать: не нравится

Now that the contest is finished, how was Div2 B supposed to be solved?

  • »
    »
    13 лет назад, скрыть # ^ |
     
    Проголосовать: нравится +8 Проголосовать: не нравится

    This is based on my solution (which unfortunately fails for one single case, but fixed in this solution):

    Take as many mixed bouquets as possible, then take as many single-colored bouquets as possible. This gives the first answer, call it greedy.

    However, when there is at least one flower of each color, it's possible that if we give up one mixed bouquet, we can make more single-colored bouquets (example is 3 5 5). So we take all but one mixed bouquets, then take as many single-colored bouquets as possible. This gives the second answer, call it almostgreedy.

    Take the greater of these.

    If you're not convinced that this is the correct answer, you can proceed further by giving up two mixed bouquets if possible to get another answer. Take the greatest of these. (If you give up three mixed bouquets, you immediately get one bouquet of each color, so the net total is zero. So it doesn't worth trying.)

    For example:

    3 6 9 -> greedy = 3 + (3 - 3) / 3 + (6 - 3) / 3 + (9 - 3) / 3 = 6 and almostgreedy = 2 + (3 - 2) / 3 + (6 - 2) / 3 + (9 - 2) / 3 = 5, so the answer is 6.

    3 4 5 -> greedy = 3 + (3 - 3) / 3 + (4 - 3) / 3 + (5 - 3) / 3 = 3 and almostgreedy = 2 + (3 - 2) / 3 + (4 - 2) / 3 + (5 - 2) / 3 = 3, so the answer is 3.

    3 5 5 -> greedy = 3 + (3 - 3) / 3 + (5 - 3) / 3 + (5 - 3) / 3 = 3 and almostgreedy = 2 + (3 - 2) / 3 + (5 - 2) / 3 + (5 - 2) / 3 = 4, so the answer is 4.

    0 2 2 -> greedy = 0 + (0 - 0) / 3 + (2 - 0) / 3 + (2 - 0) / 3 = 0. We cannot do almostgreedy because there is no red flower; there's no mixed bouquet to give up. So the answer is 0.

  • »
    »
    13 лет назад, скрыть # ^ |
     
    Проголосовать: нравится 0 Проголосовать: не нравится

    Think about this case : 8 8 9 the correct answer is 8 not 7 . we make 2 red bouquets and 2 green bouquets and 2 blue bouquets and and 2 mixing bouquets. I think this is the critical case .

    • »
      »
      »
      13 лет назад, скрыть # ^ |
       
      Проголосовать: нравится +1 Проголосовать: не нравится

      Solutions that greedily takes mixed bouquets solve 8 8 9 correctly. The 3 5 5 hack fails both solutions that greedily takes mixed bouquets and solutions that greedily takes colored bouquets. All solutions must have a way to handle backtracking for that particular hack.

      However, the trick doesn't stop there. Solutions that implement the backtracking must also handle 0 2 2 correctly (it cannot backtrack).

      In my opinion, the critical cases are 3 5 5 and 0 2 2.

  • »
    »
    13 лет назад, скрыть # ^ |
     
    Проголосовать: нравится +1 Проголосовать: не нравится

    Simply, we can make mixing bouquet 0, 1 or 2. This is because that if we make 3 or more, it equals to we make 1 of each color. And '2 2 0' is a really strong hack data...

  • »
    »
    13 лет назад, скрыть # ^ |
     
    Проголосовать: нравится +3 Проголосовать: не нравится

    First, note that you never need to make more than 2 mixing bouquets. Because you can change every 3 mixing bouquets into 3 single-colored bouquets (1 red, 1 green and 1 blue). So if you decided to make 3a+b mixing bouquets (with b = 0, 1 or 2), then you can always leave b mixing bouquets and change 3a mixing bouquets into 3a single-coloured bouquets.

    So the entire solution requires you to check 3 cases: choose 0, 1 or 2 mixing bouquets first, then create the remaining single-colored bouquets in a greedy way.

»
13 лет назад, скрыть # |
 
Проголосовать: нравится +7 Проголосовать: не нравится

Nice problems, both of them are good. I hope all get nice ratings ^^

»
13 лет назад, скрыть # |
 
Проголосовать: нравится +26 Проголосовать: не нравится
»
13 лет назад, скрыть # |
 
Проголосовать: нравится +6 Проголосовать: не нравится

Very nice!Clear and short problem statement, also the problems is interesting and nice, thank you :)

»
13 лет назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится

Can anyone tell me about the pretest 10 of div.2 — B ?

»
13 лет назад, скрыть # |
 
Проголосовать: нравится +25 Проголосовать: не нравится

2 points above second place...

I am too lucky :)

Also I think Problem E is much simpler than Problem D.

»
13 лет назад, скрыть # |
 
Проголосовать: нравится +3 Проголосовать: не нравится

Problem div2 D / div1 B can be solved with O(N log N + M log M) Why the constrains are too low?

»
13 лет назад, скрыть # |
← Rev. 3  
Проголосовать: нравится 0 Проголосовать: не нравится

Quite fast testing today in Div-2, especially in the beginning. Hope to see new rating to be fast-updated in the same way.

»
13 лет назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится

Я что-то очень туплю, но почему в Bdiv2 на тест 3 5 5 ответом является 4(тест 10)?

»
13 лет назад, скрыть # |
← Rev. 5  
Проголосовать: нравится +14 Проголосовать: не нравится

Will participants who used e-maxx.ru be banned? I saw some solutions where were used hungarian algorithm and mincostflow implementations from e-maxx.

Add: I suppose it will be honest, especially in case of last things on abbyy cup.

»
13 лет назад, скрыть # |
← Rev. 2  
Проголосовать: нравится 0 Проголосовать: не нравится

Deleted. Oops repeat, sorry.

»
13 лет назад, скрыть # |
 
Проголосовать: нравится +18 Проголосовать: не нравится

I think the user who sent the disgusting pictures should be banned.

»
13 лет назад, скрыть # |
 
Проголосовать: нравится +7 Проголосовать: не нравится

first time get blue color after waiting 29 contest :)

»
13 лет назад, скрыть # |
 
Проголосовать: нравится -14 Проголосовать: не нравится

How can [user:cgy4vever] participate in his own contest ?

»
13 лет назад, скрыть # |
← Rev. 2  
Проголосовать: нравится +10 Проголосовать: не нравится

Is there a way we can download test case or see entire data in a test case?

When I see the test case for which my program failed, it truncates the data and I am not able to see the complete test case.

»
13 лет назад, скрыть # |
 
Проголосовать: нравится -9 Проголосовать: не нравится

DIV1 A is awesome! But it would be more interesting, if moves count to reach the end point was also required to calculate.

»
13 лет назад, скрыть # |
 
Проголосовать: нравится +3 Проголосовать: не нравится

Hey friends....

When codeforces round 191 is going to commence...????

»
13 лет назад, скрыть # |
 
Проголосовать: нравится +2 Проголосовать: не нравится

good contest

»
13 лет назад, скрыть # |
← Rev. 6  
Проголосовать: нравится 0 Проголосовать: не нравится

How is Commander Ciel solved (Div2 E or Div1 C)? Am I right that after finding the optimal root, the build process looks like:

  • current = 'Z', highest = 'A'
  • If node has one child, just continue using&incrementing current rank until you come to the highest, then drop current to 'Z' and --highest ('B'), then repeat from 'Z' to 'C' ... and if you're not done after 'Z'-'Z', then it's impossible
  • If node has more than one child, use highest rank in this node, drop current to 'Z' and --highest for child subtrees

If this is correct, I think that the optimal root must be the tree center (the node which minimizes tree height), but I'm getting WA on case 13.

»
12 лет назад, скрыть # |
 
Проголосовать: нравится -14 Проголосовать: не нравится

Congrats to cgy4ever on qualifying for Facebook Hacker Cup onsite finals.. All the best :)