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

Автор vovuh, 6 лет назад, По-русски

Привет, Codeforces!

В 17.09.2018 11:05 (Московское время) состоится Codeforces Round 510 (Div. 2) для участников из второго дивизиона (участников с рейтингом до 2100). Участники первого дивизиона традиционно могут участвовать вне конкурса.

Раунд будет рейтинговый для участников второго дивизиона (с рейтингом менее 2100). Условия будут доступны как на русском, так и на английском языках.

Этот раунд проводится по задачам школьного этапа Всероссийской олимпиады школьников по информатике 2018/2019 года г. Саратова. Задачи для вас готовили awoo, fcspartakm, Neon, BledDest, Roms и vovuh. Огромное спасибо нашему координатору cdkrot за помощь в подготовке раунда! Также спасибо тестерам DavidDenisov, PrianishnikovaRina, Decibit и Vshining.

Участникам будет предложено 6 задач и 2 часа на их решение. Разбалловка будет традиционно объявлена ближе к началу раунда. :)

UPD: Разбалловка 500-1000-1500-2000-2250-2750.

UPD2: Разбор

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

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

Another wonderful time for Chinese users.

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

thanks codeforce for another round.

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

В 11:05 у меня начинается пара...
Писать контестик или идти на пару?

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

    писать контест на паре

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

      Мдэ я ноутбук дома забыл , придётся в уме решать

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

    Ну, я завтра кстати из-за этого контеста тоже пару пропускаю :)

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

Why so early?It's like choose what is more important some kind of study or cf.

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

Well, where is the thanks to MikeMirzayanov and polygon platform XD

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

A bad time for indian students :(

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

A bad time for Chinese student who need to study mathematics.

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

thank you for the back to back contest ...a contest in afternoon for Indian users after a long time ...will have to bunk class to give ....

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

Может быть перенесете начало попозже?

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

Its very good to have variety in the hours that contests start so as everybody can find a time that fits to their standards. I hope that codeforces will continue this logic in the future as well.

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

For a moment I thought this was an educational round announcement

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

Really?! 12:35 IRDT

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

Вспомнил прошлогодний раунд по задачам с Саратовского муниципального этапа...

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

Forgot to Thanks MikeMirzayanov for the wonderful codeforces and polygon platform.

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

Great time for Chinese CF users.

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

Wonderful time for Chinese users. So I am coming.

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

Hack for A.
3 1
1000 1 1
Answer 1000 1001.

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

you can simplify the problem C to this :

given a sequence of none negative numbers(n-th >= 0) get the maximum product.
so you will multiply the positive integers. then multiply the 0's and delete the last occurrence of the zeros
how to get this ?
if you have an odd number of negative numbers , convert the maximum negative number to zero , then take the absolute value for all the sequence.

could any one help me to understand the task D ? thanks in advance :)

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

    Consider the sum of segment [i,j] less than t is equals to prefix[i] - prefix[j-1] < t.

    For every prefix[i](1<=i<=n) calculate the number of j(0 <=j <i ) which satisfy prefix[j] > prefix[i] - t, and this number is the numbers of segments which endpoint is i and satisfy sum less than t.

    You can use the BIT to calculate the number of j (0<=j<i) which satisfy prefix[j]<=prefix[i]-t easily.Then what you need to calculate is i - the number of j . Sorry for my poor english.

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

the editorial is just after contest end.

WoW!

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

Such Tight limit constraints in Que-3 ,making it almost impossible to pass in pypy2/python2

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

why TLE using dp in problem D?

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

    For each i in [2..n] you iterate n - i times.

    The number of operations is

    Your solution is O(n2), that's why it gives TLE.

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

What is test 22 structure like on problem D?

P.S I found out the problem, try this test: 5 6 5 -5 10 -5 10

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

In problem C, there are no cases with only zeros and ones. This DP solution should fail: 42985876

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

~ B

~ N^3 (MAX_N = 1000)

~ ACCEPTED 1 SEC

~ Who can explain WHY???

42983122

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

    this is weird !

    i tried many tests to get the answer after 2s

    but this is the maximum time i got on the custom test!

    test case (long text)

    Test

    :

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

    Nowadays computers are fast enough to run 10^9 iterations in around 1s. Look at my code which runs around N^3/6 iterations in 234ms. http://mirror.codeforces.com/contest/1042/submission/42975128

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

    The following test case takes 2230ms on Codeforces (GNU G++14): 1000 AB and randomly appending C.

    Random Cs make a worse case than 1000 strings of ABC, most probably because of branch prediction.

    Here's the code with the case generated instead of being read: https://ideone.com/JRyp7j

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

Does CF Rating predictor gives completely wrong rating predictions for today's contest ? Because it seems to me it worked perfectly well in yesterdays contest

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

I'm getting the message "Ooops! Something has broken down in Codeforces" when I try to open problem C, does anyone else get this message? What's going on?

Edit: The editorial for problem C is also not loading, probably the problem's package is somehow broken.

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

    Yes I am also facing this problem , But i can submit it through problem id .

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

    I'm getting that too!!! What's going on?

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

    No idea, to be honest. The package itself seems ok, I rebuilt it just to be sure, nothing got fixed. And the previous revision was created like 3-4 hours ago, something broke after that. Just wait a bit, sorry, I have no better advice for now.

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

Я вот помню, как на школьном этапе писал что-то уровня A+B. Человек, сдавший больше половины на таком школьном этапе, должен на области набирать 400+ с закрытыми глазами.

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

    На школьной Д с раунда была самой сложной задачей. Часть более простых мы в раунд не взяли.

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

It is better to put some difficult problems. This round is extremely easy for me.

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

in task E in Div 2, what is the answer on test: 1 3 1 1 2 1 3 ?