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

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

Привет всем! Совсем скоро начнется Codeforces Round #254.

Главным героем раунда будет клёвый парень по имени DZY. DZY очень любит решать самые разнообразные задачки. К сожалению, не со всеми задачами он может справиться, поэтому вам придётся немного помочь ему.

Традиционно благодарим Gerald за его советы по подготовке раунда, а MikeMirzayanov за создание замечательной платформы для проведения соревнований по программированию.

Задачи готовили FancyCoder и я. Отдельное спасибо пользователям vfleaking, jqdai0815 и lsmll за тестирование задач контеста.

Не упустите свою возможность помочь клёвому парню DZY.

Желаем удачи и удовольствия от решения задач!

Распределение баллов по задачам будем анонсировано совсем скоро.

UPD

Разбалловка для первого дивизиона: 500-1000-2000-2000-2500.

Разбалловка для второго дивизиона: 500-1000-1500-2000-3000.

UPD

Соревнование завершено, всем спасибо заучастие!

Поздравляем победителей!

Победители Div. 1:

  1. subscriber

  2. flydutchman

  3. uwi

  4. Egor

  5. stevenkplus

Победители Div. 2:

  1. lost3030

  2. laekov_

  3. JongMan

  4. Daumilas

  5. nnahas

Разбор задач уже опубликован.

Условия задач Codeforces Round 254 (Div. 2)
  • Проголосовать: нравится
  • +262
  • Проголосовать: не нравится

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

Finally :D

A contest announcement,after almost 20days.

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

I wish DZY to be a MERCIFUL guy ..... Everyone Good Luck and Have FUN :)

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

From my point of view,the problems are all very interesting.Wish you high rating!

PS:DZY's CF handle is dzy493941464.

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

Hmmm chinese contest. Brave yourselves guys!!

Actually all we need is bravery :))

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

Sounds great! I love cute boys (and girls)!

»
10 лет назад, # |
  Проголосовать: нравится -8 Проголосовать: не нравится

this is the contest after more half month. FUNNY ! :D

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

the Chinese IOI team 0_0

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

Brace yourselves, DZY loves desert (http://vfleaking.blog.163.com/blog/static/174807634201422485914893/) incoming...

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

You had no decrease in your rating chart!

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

I hope I will get expert in this contest http :D

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

hope the testing system will testing quick after the contest

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

Probably won't be able to participate in the contest cause here in Bangladesh its the time for iftar(time to break fasting in the holy month of Ramadan) :( :( BTW best wishes for other participants....

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

    That doesn't prevent you from participating you can put a lot of dates with water beside you :) and continue eating after the contest.

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

      Taking food is not the problem!! The important thing is magrib prayer. Besides there is Isha prayer as well as tarawih prayer which starts within one and half hour of iftar. After all its ok cause, "To get something u have to lose something". Inshallah will enjoy plenty of contests in later days :) :)

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

How to register this competition?

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

hey DZY please grow up and try to solve your problems by yourself ! :)

»
10 лет назад, # |
  Проголосовать: нравится -8 Проголосовать: не нравится

please how i can register to the contest i'm new here

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

    Registration will be open in 3 hours. It always starts 24 hours before the start of the contest.

    • »
      »
      »
      10 лет назад, # ^ |
        Проголосовать: нравится -6 Проголосовать: не нравится

      it's now 24 hours before the start of contest, but the Contests page says that registration for the round will open in 9 more hours only.

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

Please don't use such silly names; they confuse us.

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

Why are we having so few rounds these days? Even TopCoder has only 2 SRMS planned this month :/

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

sad its timing clashes with the timing of wimbeldon finals

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

hey DZY take it easy !

»
10 лет назад, # |
Rev. 3   Проголосовать: нравится +17 Проголосовать: не нравится

WARNING: Mathy round approaching!

"DZY loves math xxx"

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

    DZY loves many things, we can even say everything.

    so he also loves DP, probability, graphs, geometry, data structures (and many more concepts) in addition to just math. ;)

    • »
      »
      »
      10 лет назад, # ^ |
      Rev. 2   Проголосовать: нравится +3 Проголосовать: не нравится

      It seems that my prediction was wrong :p

      However, round #255 was indeed a very mathy round :D

      PS: authors of round #255 is the same as "DZY loves math" series in BZOJ(a Chinese online judge contains only very tough problems)

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

I don't have my library currently and my last contest was more than 2 months ago. My question is can I do it as a virtual contest during the same time as the official contest?

PS: For all coders who don't have an online backup for their library, do it ASAP. My laptop's HDD crashed recently and I don't even know yet if the data can be recovered.

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

    I don't think that I notice virtual contest button appear after final system test.

»
10 лет назад, # |
  Проголосовать: нравится -6 Проголосовать: не нравится

And, what about the unusual contest time??

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

From the "Urban Dictionary":

DZY

1)Complementary definition of a person, place, or thing..that epitomizes the elements of sheik, classy, cool,or just downright unique.

2) An intensifier

3) Kastration technique (????)

4) Generally used to describe a very cool person

5) Nondescript term that can be used to define anything that is awesome, over the top, and dope.

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

    4) Generally used to describe a very cool person

    Now i understand ..

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

There was a few consecutive contests without delay but I think it's back! Good Luck

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

Extended by 5 minutes.!

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

Или я стал тупее, или раунды сложнее..

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

    Вроде все китайские раунды такие

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

      Сегодня вообще был более-менее нормальный раунд. Я бы даже сказал — лучше большинства не китайских. Раунд, в котором каждую из 5 задач решило больше 10 людей, а не популярное в последнее время "а еще вот вам задача Е, которую вообще никто не сдаст, это чтобы вы не забывали, что еще есть куда расти и нет предела совершенству; мне ведь нужно было чем-то занять последний слот в проблемсете".

      И действительно сегодня нужно было сдавать все 5, ничего убийственного там не было — в то же время, все 5 не сдал никто, что тоже хорошо. Таблица выглядит интересно, нету банального "1 человек сдал А-Е, 5 человек сдали А-D, 50 человек сдали А-С, 500 человек сдали А-В..." столбиками, на лицо едва ли не все возможные комбинации решенных участником задач:)

      И при этом задачи по сложности расставлены более-менее правильно — об этом можно судить по числу АС (хотя не уверен, что здесь не сыграл ключевую роль эффект "надо решать по порядку").

      В общем, хороший контест получился)

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

Pretty tough competition, but great fun!

I liked B a lot, though using the randomness of the simple generator felt a bit risky.

Was problem A greedy somehow?

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

    Yes; choose the edge that gives the maximum density. (The induced subgraph will have two vertices.)

    • »
      »
      »
      10 лет назад, # ^ |
      Rev. 5   Проголосовать: нравится +6 Проголосовать: не нравится

      Oh...

      Because if we have already picked some nodes vs and edges es, and we want to add node u with e being the sum of edges from vs to u, then we must have (vs+c)/(es+e) > vs/es, but that implies c/e > (vs+c)/(es+e) so clearly just picking c and any node from vs would be a better choice.

      Thanks :D

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

        Exactly. I went on and proved that first before submitting my solution to ensure correctness. :P

        Of course, you have to pick the node in vs that is connected to c, but that's why you inspect each edge (instead of any pair of vertices) to ensure the connectivity.

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

    for A, we always had to choose two nodes and one edge. adding more edges will make the density lower.

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

Please can anyone tell me how to do Div2 C ?

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

how to solve Div-1 B?
also, why my code 7029179 gives WA#9?

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

Problem E uses Inteval Tree (Segment Tree) ?

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

Oh God, a stupid mistake, in problems B div 1 I use ios::sync_with_stdio(false) but then I use print("%d"). May my code will fail system test because that mistake ?

»
10 лет назад, # |
  Проголосовать: нравится -6 Проголосовать: не нравится

Contest is difficulty with me !

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

How solved problem B ?

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

    Put chemicals in order of DFS then caculate danger. I learnt to code DFS when contest is running LOL.

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

Fast system :D

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

Good Contest ... Thanks Authors ...

Segment Tree range updates in problem E/Div2 C/Div1 was very similar to UVA12436


if(l<=x<=r) You need to find where updates is zero ... Then you have one A query and one B query else You have one query like UVA-12436 A or B and one value update on segment-tree

UPD : ok ok ... DownVoters i got ... in case colors was fixed this kind of solution would be correct , but in this problem, it wont work ... I hope some days we only DownVote to rude speeches, NOT WRONG IDEAs

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

Very quickly system testing :D

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

very fast system testing! :)

»
10 лет назад, # |
Rev. 4   Проголосовать: нравится 0 Проголосовать: не нравится

I liked the round a lot. C was super nice , I solved it on paper with sets and an segment tree. ( but I'm not sure it's ok ) I got WA on B for something that I thought it works in O(N log N) , but got TLE. Overall , very nice round even though I think I'm going to be div2 after it. :)) Congrats for the authors !

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

Definitely, fastest system test!

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

Following my previous blog post on ranking submissions as a collaborative wisdom for picking good reference solutions, i.e. http://codeforces.me/blog/entry/12917, you can now vote your favourite submissions for this contest at:

Div1: http://hiukim.com/cfsubmissions/contest.php?contestId=444

Div2: http://hiukim.com/cfsubmissions/contest.php?contestId=445

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

Damn it. One character and I'm the first:

- if (sz(it1->second) < sz(it2->second)) swap(...)
+ if (sz(it1->second) > sz(it2->second)) swap(...)

What's even more painful is that I wrote right at first, then changed it for testing purposes and then forget to change it back.

»
10 лет назад, # |
  Проголосовать: нравится -8 Проголосовать: не нравится

Как нормально решать D? Я посмотрел на ограничения до 50000 вместо 100 и целых 3 секунды TL — и заслал перебор за О(N) на запрос.

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

    Для начала выкинем одинаковые запросы (это важно). Потом на каждый запрос отвечаем за , где A — количество вхождений первой строки, а B — количество вхождений второй. Если поменять местами в правильном случае (так, чтобы A ≤ B), то получается .

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

      А чтобы в запросе получить этот логарифм — хранить все вхождения каждой строки в каком-нибудь сете?

      Спасибо)

      Вероятно, у меня примерно такое же решение, только ответ на запрос за A+B (два указателя).

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

        Нет, просто бинпоиск по отсортированному вектору. У меня он получается отсортированным автоматически.

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

        Двумя указателями не должно проходить по времени. Смотри http://codeforces.me/blog/entry/12923#comment-176810

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

          На таком работает 3.7. Хоть это и TL, но еще не самый кошмарный вариант.

          Во-первых, вхождений а не так уж и много, ~25к; во-вторых, из-за того, что буква а встречается очень часто — подстроки в запросах часто повторяются, и различных запросов получается значительно меньше 100к.

          Для строки, в которой первые 2/3 — символы а, а дальше рэндом, и запросы вида 1..4 буквы а + рендомная подстрока длины 3..4 из хвоста — работает дольше 10 секунд:(

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

      А почему получается такая оценка? (Я про корень).

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

        На запросы, в которых оценка, очевидно, не хуже, поэтому их сразу откидываем.

        Теперь в каждом запросе у нас . Заметим, что различных подстрок, каждая из которых встречается в строке длины N хотя бы раз не более . Применим немного амортизационного анализа: будем считать время выполнения не каждого запроса (которое состоит из X запусков бинпоиска, где X — количество вхождений одной из подстрок), а для каждой подстроки S считать, в скольки запросах мы по ней итерируемся и пускаем один бинпоиск. Так как у нас может быть не более различных подстрок в паре с текущей (одинаковые запросы мы давно выкинули, а всего часто встречающихся различных подстрок не более ), то получаем оценку в запусков бинарных поисков по массиву длины не более N.

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

      Я еще добавил оптимизацию, что если длины отличаются менее, чем в логарифм раз, то работать за сумму. Интересно, убирает ли это лог под корень?

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

 This bug has costed me 100 points.I have clicked once submit.

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

I wrote lots of code for C(div 2). Than I recognized we just need two nodes and an edge. :(

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

My code got wrong answer on pretest 5 div2 A. I see the test case but I think my output is also correct. Can someone check it for me please? http://codeforces.me/contest/445/submission/7032620

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

will there be any solutions posted?

  • »
    »
    10 лет назад, # ^ |
    Rev. 4   Проголосовать: нравится +1 Проголосовать: не нравится

    Editorial will be posted very soon. BTW,the contestants' solution for Div1 E was unexpected to us...Our solution was far more slower,that's why n is only 3000

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

Anyone who tried to exploit the random generator in 1B? Many solutions (including mine) depends on randomness. Problem statement blocked the unique fixed point, but there might be some small cycle which can hack these kinds of solutions.

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

How to get on the main page after the contest without actually participating. =)

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

I have used 4 Segment tree to get AC problem C (after the contest). Does anyone have better solution? Thank you.

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

waiting for editorials...

»
10 лет назад, # |
  Проголосовать: нравится -11 Проголосовать: не нравится

How to solve div2D? FFT?

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

A Div2 was harder than a usual A Div2

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

English Editorial has been posted!

»
10 лет назад, # |
Rev. 4   Проголосовать: нравится 0 Проголосовать: не нравится

interesting problem set, I wrote complicated solutions for C and E, and got very simple solutions after reading subscriber's code, cool!

3 bytes far from all clear orz.

- s+=(r-l+1)*abs(x-vq.back());
+ s+=(r-l+1LL)*abs(x-vq.back());
- int l=1,r=10000;
+ int l=0,r=10000;
»
10 лет назад, # |
Rev. 3   Проголосовать: нравится +8 Проголосовать: не нравится

Very nice round. I liked the problems even though i only managed to solve 1. Div. 1 A proved to be a nice revelation. I got the idea by thinking back to when i used to play online shooters when I wanted to maximize my kdr (Kill-Death Ratio). Say my current kdr was K/D and in a match i'd manage to get k kills and d deaths. Now if k/d > K/D then (K+k)/(D+d) > K/D and my kdr would grow or it would fall otherwise. The same thing applies to the problem at hand.

»
10 лет назад, # |
  Проголосовать: нравится -8 Проголосовать: не нравится

The TIme limit for problem C should have been 3s. My algo was correct (used sqrt-decomposition) but I had to reduce the size of each partition by a constant amount to get it accepted.

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

    What's the problem then? It's absolutely OK that some implementation details matter a lot, imho.

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

You can see the country wise standings for the contest here. In case you want to report bugs / suggest features, kindly use this blog.

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

В D слабые тесты. Это решение 7032235 валится по TL следующим генератором

#include <bits/stdc++.h>
using namespace std;
#define forn(i,n) for (int i = 0; i < int(n); ++i)
string s;
int main () {
	s.resize(50000);
	forn (i, 50000)
		s[i] = (rand() & 1) ? 'a' : 'b' + rand() % 25;
	puts(s.c_str());
	puts("99995");
	forn (i, 49998)
		puts(("a " + s.substr(i, 3)).c_str());
	forn (i, 49997)
		puts(("a " + s.substr(i, 4)).c_str());
}
»
10 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Сдал в B какую-ту глупую жадность, думал, что завалится, а в C сдал вообще бред, мне казалось, даже претесты не пройдет. Ан нет :)

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

Div1-B can be solved without regard to randomness in time. See 7031500

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

    I'm curious why do you use integers in your BitSet? For example my implementation with longs 7040099 works like 1.5 times faster than same with ints 7040106.

  • »
    »
    10 лет назад, # ^ |
      Проголосовать: нравится -24 Проголосовать: не нравится

    It seems to me that and O(n2) are same, therefore there is no reason to write 32 in the denominator.

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

      Formally, they are, but in this case, the /32 factor is used to denote that the constant factor will be that much smaller.

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

      Still my notation leads to a little bit better understanding of actual solution timing, isn't it?

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

How to solve div1 C using segment tree ?

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

"всем спасибо заучастие". Пофикси, пожалуйста.