Пожалуйста, подпишитесь на официальный канал Codeforces в Telegram по ссылке: https://t.me/codeforces_official. ×

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

Автор Vovuh, история, 4 месяца назад, По-русски,

<copy-pasted-part>

Привет!

В 31.07.2018 17:35 (Московское время) начнётся Codeforces Round #501 (Div. 3) — очередной Codeforces раунд для третьего дивизиона. В этом раунде будет 6 или 7 задач, которые подобраны по сложности так, чтобы составить интересное соревнование для участников с рейтингами до 1600. Наверное, участникам из первого дивизиона они будут совсем не интересны, а для 1600-1899 покажутся простыми. Однако все желающие, чей рейтинг 1600 и выше могут зарегистрироваться на раунд вне конкурса.

Раунд пройдет по правилам образовательных раундов. Таким образом, во время раунда задачи будут тестироваться на предварительных тестах, а после раунда будет 12-ти часовая фаза открытых взломов. Я постарался сделать приличные тесты — так же как и вы буду расстроен, если у многих попадают решения после окончания контеста.

Вам будет предложено 6 или 7 задач и 2 часа на их решение.

Штраф за неверную попытку в этом раунде (и последующих Div. 3 раундах) будет равняться 10 минутам.

Напоминаем, что в таблицу официальных результатов попадут только достоверные участники третьего дивизиона. Как написано по ссылке — это вынужденная мера для борьбы с неспортивным поведением. Для квалификации в качестве достоверного участника третьего дивизиона надо:

  • принять участие не менее чем в двух рейтинговых раундах (и решить в каждом из них хотя бы одну задачу),
  • не иметь в рейтинге точку 1900 или выше.

Независимо от того являетесь вы достоверными участниками третьего дивизиона или нет, если ваш рейтинг менее 1600, то раунд для вас будет рейтинговым.

Спасибо MikeMirzayanov за платформы, помощь с идеями для задач и координацию моей работы. Спасибо моим очень хорошим друзьям Михаилу PikMike Пикляеву, Максиму Ne0n25 Мещерякову и Ивану BledDest Андросову за помощь в подготовке и тестирование раунда.

Удачи!

</copy-pasted-part>

Также хочу сказать, что участники, намеренно отправляющие неверные решения и взламывающие их после окончания соревнования (пример), не будут показаны в таблице лидеров по взломам.

UPD1: Разбор опубликован.

UPD2:

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

Rank Competitor Problems Solved Penalty
1 Wavyn 7 245
2 delete4 6 168
3 mafagafogigante 6 212
4 dongshunyao 6 214
5 jiaangk_ 6 217

Поздравляем лучших взломщиков:

Rank Competitor Hack Count
1 halyavin 354:-66
2 test616.cpp 66:-7
3 OlaAdel 18
4 antguz 21:-7
5 wanderer163 20:-5

Всего было сделано 604 успешных взлома и 446 неудачных взломов!

И, наконец, поздравляем людей, отправивших первое полное решение по задаче:

Problem Competitor Penalty
A 314rate 0:01
B 314rate 0:06
C garipov.roma 0:07
D shanghaiKingCsl 0:12
E1 Ka55un0 0:30
E2 Ka55un0 0:30
F shanghaiKingCsl 0:48

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

»
4 месяца назад, # |
  Проголосовать: нравится -26 Проголосовать: не нравится

First Div-3 contest in 5th century. :P :D

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

31 July is my birthday. Thank you codeforces for this gift on my birthday :)

»
4 месяца назад, # |
Rev. 5   Проголосовать: нравится -24 Проголосовать: не нравится

Please reduce the duration of hacking phase.

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

    maybe 6 hrs.

  • »
    »
    4 месяца назад, # ^ |
    Rev. 2   Проголосовать: нравится -32 Проголосовать: не нравится

    Don't play ...................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................

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

I am also would like to say that participants which which will submit wrong solutions on purpose and hack them afterwards (example) will not be shown in the hacking leaders table.

"which which"

Please correct it!

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

that moment when you are join virtual get high score then join real contest and get very bad score , why this life is so cruel ?

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

forget to remove something ? , lol

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

Is this div3 or as usual “div3” is just a hidden div2?

»
4 месяца назад, # |
  Проголосовать: нравится -41 Проголосовать: не нравится
»
4 месяца назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

So, further Div.3 rounds / Educational rounds' hacking phase will not count self-hacks as well? :D

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

    Hmm, they do count for now, like we manually delete users from the top-5 table who hack themselves too much. Though, I believe, it's easy to fix the tool to exclude these hacks, I'll check what I can do with it.

    They count for the standing page but it seems a pretty fair solution to not count them in top-5, all in all.

    Edit: Oh, forget about it) I coded this tool in a most disgusting way possible, too much effort needed to fix it now. Maybe when I finally decide to refactor all of it, I'll take that issue in a consideration.

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

      Alright, I thought it was implemented into the system. Well, would be a nice idea for Mike to consider?

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

        Well, not every hack of yourself is a way to cheese the standings. It still might be possible that user knows where his solution fails despite passing all the tests and wants to add the test to the final testset.

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

Please Decrease hacking time, Hold the Contest intime, Tests have strong arm(s), Check servers for downtime, Hope you enjoyed this rhyme.

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

contest back2back hip hip array!

»
4 месяца назад, # |
  Проголосовать: нравится -30 Проголосовать: не нравится

What's the penalty for wrong submission?

»
4 месяца назад, # |
Rev. 3   Проголосовать: нравится -27 Проголосовать: не нравится

it should be ..

copyed-semi_edited-posted

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

No more rounds on the weekends?

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

"register for the contest" link in email leads to Codeforces Round #498 (Div. 3), don't copypaste this part next time :)

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

    Wow, the funniest thing that this link is copy-pasted not by me :D I don't know but I think Mike sends email manually or using some script/this is automatic process

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

hacking yourself on purpose to get on the hacking leaders table... that's pretty dirty...

»
4 месяца назад, # |
  Проголосовать: нравится -59 Проголосовать: не нравится

I don't know how about other participants but i definitely hate when contest held by Vovuh or PikMike, especially when it comes to div3 or (this is hot one) Educational. From the first sight it seems to be much more easier then regular contests, but when you open the first problem, it's hard as hell just to understand what the hell is going on. Maybe i'm to stupid to complain but I think div3 mainly maintained for GREY or GREEN guys, not for RED. Please make the rounds more doible for us not for them.

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

    TBH, I have an opposite opinion. I'm not sure why, but I feel that Vovuh usually does fairly easy problem (for me anyways). I'm kinda looking forward to his contest now

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

      I don't think this problem for div3 contest

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

        Do you have any other examples? Anyway, I don't think it is fair to judge me for such infrequent (I think) mistakes (remember that I am human too and I could be wrong), but you do it and it really makes me sad. But I am also sad by the fact that I can't prepare all my rounds without any mistakes.

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

        If Div.3 was only cakewalk problems then what is the purpose of it!! How newbie and pupil users will get the advantage of div.3 rounds if Vovuh didn't put a little bit harder problems than usual from a time to time:) Anyway if you want to improve your level then you have to solve problems with different difficulties, solving div.3 A won't even make you pupil, I think even a red user won't improve his level if he didn't change the difficulty level of the problems that he solves.And for sure everything happens gradually.

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

    Do you have an example of a problem that would be good as Div3A?

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

    It seems to me you are expecting this site to teach you competitive programming from scratch ("scratch" being not knowing how to code, or how to code competitively). Codeforces is not for that. It's for any level, but you have to master trivial problems to even have a level in the first place (I'm not trying to offend you, I'm just saying you need to try studying before competing). Not even Div3A (and definitively not Div2A) is a "trivial educational problem" such as "sum a and b, a,b <=1000", which you imply would make a good Div3A.
    And please, don't shake it out on excellent problem setters such as Vovuh or PikMike because you don't like their style or had a bad day.

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

Однажды я понял, что мое решение неверно только после окончание раунда, и взломал его. Я и не думал, что это будет расцениваться как сдача намеренно неверного решения

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

    Можешь просить других участников взламывать себя)

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

    Я не понимаю, как можно подобное подогнать под формулировку "сдача намеренно неверного решения". К счастью, подобных случаев не очень много, мы вполне можем разобраться, что было сделано специально для попадания в топ-5, а что являлось разумным взломом себя.

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

      Но если бы я попадал тогда в топ-5, то по нынешним правилам, меня бы просто не показали в таблице лидеров! Несправедливо, может лучше если взломы себя не будут учитываться?

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

        Да пускай полезные взломы себя считаются, почему нет. Раз разработчиками кф такой функционал предусмотрен, то они по-видимому согласны с этим. А участники с намеренно неверными решениями и упоминания даже не заслуживают. Не думайте, что мы там собираемся какие-то сильно жёсткие правила придумывать, просто стараемся более справедливый топ сделать.

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

        Если мы будем сомневаться в намерениях, то решение будет принято в пользу участника, разумеется.

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

Can someone explain codeforces' system of gaining rating points please (in talks, for example)

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

So, just checking — if I participate in this, it won't affect my rating?

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

    Regardless of whether you are a trusted participant of the third division or not, if your rating is less than 1600, then the round will be rated for you.

»
4 месяца назад, # |
  Проголосовать: нравится -26 Проголосовать: не нравится
Комментарий удален по причине нарушения правил Codeforces
»
4 месяца назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

Как решить D?

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

Great work with questions.

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

What is the third number test case for problem C??

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

What's in test 4 , on problem F ?

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

Dont copy whole announcement, copy just link from previous announcement.

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

how does hacking in div 3 affect the leader board for the hacker?

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

How to solve F?

  • »
    »
    4 месяца назад, # ^ |
    Rev. 7   Проголосовать: нравится -6 Проголосовать: не нравится

    You can solve it with dynamic programming approach.

    Let's DP(i, j, k) be the number of ways to form a regular bracket, we are at i-th position, degree of a regular bracket is j and we are at k-th position of string s.

    Answer is DP(2 * n, 0, s.length()).

    Passing state:

    Consider the i-th position we want to put a '(', if s[k] == '(' then dp(i, j, k) -> dp(i + 1, j + 1, k + 1)

    Otherwise we want to find such position l nearest with i and the part from k-l to k-1 is same as 0 to l-1 (we can precalculate it in O(n^3)). Then dp(i, j, k) -> dp(i + 1, j + 1, l)

    Same as ')'.

    For detail, you can see my solution: http://codeforces.com/contest/1015/submission/41048988

    Sorry for bad English.

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

    Edit: a problem using a similar technique having the "maximum prefix that is a suffix of the current string we are building" as a dimension for the dp is http://spoj.com/problems/PSTRING/

    We will try to count sequences by the first occurrence of s in the sequence.

    Pre-compute nxt[i][c='('/')'] which is the maximum prefix of s that is the suffix of (prefix of s of length i + c).

    dp1[i][j][k] = we built i letters, the "bracket depth" is j, and the maximum prefix of s that is a suffix of the current string we are building is k

    dp2[i][j] = we built i letters and the "bracket depth" is j

    Note that we start with dp1[0][0][0]=1, and instead of transitioning to dp1[i][j][s.size()], transition to dp2[i][j]. The answer will be dp2[n][0].

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

    Is there any suloition using inclusion/exclusion?

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

How come my N*M*500 Solution passed the pretest on problems E2 ?

»
4 месяца назад, # |
Rev. 3   Проголосовать: нравится -8 Проголосовать: не нравится

I can't hack , when I click to hack, it is loading and loading..

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

Are there more tests added at the end of open hacking phase? Vovuh

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

my solution for problem E1 is passing testcase1 on my System.But on codeforces it is giving wrong answer.

here is my solution link:

http://codeforces.com/contest/1015/submission/41059028

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

    Print format should be %lld.

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

      He didn't need long long in the first place. Nevertheless, format string for long long is %I64d as per Codeforces recommendation.

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

        Oh right, forgot about that. Does using %lld make trouble in CF btw?

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

        In fact, this is no matter, which format you will use when you print 64-bit integers. Codeforces accepts both I64d and lld for at least two years.

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

          Ah, ok. Probably have seen it while solving problems from old contests.

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

Issue resolved.

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

Помогите. Почему 9 тест в системе выдаёт WA, а на моём компьютере всё нормально? http://codeforces.com/contest/1015/submission/41053093

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

can someone plz tell me why this is wrong in E2. https://ide.geeksforgeeks.org/avFzCSv3v6

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

Problem D:

In problem statement, it is written that we have to perform k moves to "other" house. Given that, preliminary test case 31 should have answer as "NO", while jury's answer is "YES ...". I am not sure what is the correct place for such doubts but it would be helpful if this is looked into.

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

    Test case 31 is 10 50 450. You can repeatedly move between 1 and 10 (of which the distance is 9) 50 times and reach 450. Not sure what made you think that the answer should be NO.

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

      At the end, The person is on house no 1; so he hasn't moved to "other" house in k moves, but came back to the same house

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

        Nowhere in the description says that you must end up somewhere else than the initial house. You just need to move to somewhere else than where you currently are. It even says it twice: You can't stay where you are (i.e., in each move the new house differs from the current house). and It is possible to visit the same house multiple times** (but you can't visit the same house in sequence).

        i.e. if you are at kth house at time t, you must be at another house that is not k, at time t+1.

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

          Its written in 2nd line :

          You have to perform k moves to other house

          It implies that after k moves, the person has moved to a different house than the original one.

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

            No, it implies that each move should make you be at a different house than where you currently are, not where you initially were.

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

    You wrote in your code:

    code

    if(prefixb[i]>=m) ans=-1 means that if sum of elements of array is equal to m then the answer will be -1, but the answer should be n.

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

      But prefixb[] is the prefix sum of the compressed sizes. If the sum of these compressed lengths till i exceeds m, there's no way to store the songs. So shouldn't the answer be -1?

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

        If the sum of the sizes of all compressed songs equals to m, it fits into the flash drive. It just needs to not exceed m.

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

          If it is impossible to copy all the songs (even if Ivan compresses all the songs)

          I read this as something along the lines of "Even if Ivan compresses all songs it can be impossible to copy all songs" :(

          so out here, if prefixb[n-1] == m, the answer is n, and if it's greater than m, it's -1, right?

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

Благодарю за контест Vovuh, у вас всегда отлично получается провести раунд.

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

Plz help. Why in system my solution get WA on the 9th test, but on my PC it gives correct answer? http://codeforces.com/contest/1015/submission/41053093

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

How to solve E2 efficiently?

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

    Let call S1[i][j] be the furthest contiguous "1" that can be reach from block (i,j) upwards,S2[i][j] is the same but downwards, S3[i][j] is the same but leftmost,and S4[i][j] is the same but rightmost.

    Its easy to see that with each (i,j) we need to greedily choose the longest star that we can create, and the longest one should be min(S1[i][j],S2[i][j],S3[i][j],S4[i][j]) — 1, note that if the min(..) — 1 = 0 then we can't create the star.

    After that you're good to go, but in order to check the impossible case efficiently like in O(N*M) time, you need to break the problems down a little bit, say you have N Pairs of [L,R] segments, find which block that is not covered by any original N [L,R] Segments. Then if you solve this problems then you'll be able to check the case in O(N*M)

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

      My code: 41053798

      I did same thing, except there no need to check impossible case separately.

      Basically you want to build another matrix, I call it b such that b = input.

      Naive implementation of this is O(nm*min(n,m)), we simply brute force every position, then place maximum sizes star by trying every star size.

      But we can make this O(nm), by placing stars in O(1).

      How? We use prefix sums across columns, and then rows. And to find star size in O(1) we use dp idea describes above.

      Something like pre[left]++; pre[right+1]--;

      And then sweep across and do pre[i] += pre[i-1] will allow you to do O(1) range updates, and then a single sweep to update them all at once in O(n).

      So for every row and column its O(nm). Look at my code for more details.

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

    My solution is O(N^2LogN). I might have overcomplicated some parts of it, would love to know if there can be improvements.

    Let the array a[][] be the input matrix, such that a[i][j] = 1 if there is a star on location, 0 otherwise.

    For starters, it is easy to see that for each point (x, y), such that the point (x, y) has a star on it, we should make the longest star possible on that node. We need to accomplish this step efficiently.

    We first create 2 arrays PrefixRight[][] and PrefixDown[][]. PrefixRight stores the row prefix sum over all (i, j) and PrefixDown stores the column prefix sum. We can do this with the following code —

    for(i = 1; i <= n; i++)
        for(j = 1; j <= m; j++) PrefixRight[i][j] = PrefixRight[i][j - 1] + a[i][j];
    
    for(i = 1; i <= m; i++)
        for(j = 1; j <= n; j++) PrefixDown[j][i] = PrefixDown[j - 1][i] + a[j][i];
    

    Now, we have to find the maximum height of the star at some location (i, j). Interestingly, we can binary search over the height and check in O(1) time if it is possible using the prefix arrays we created above. Our condition evaluates to true if some contingencies are met, specifically that the number of stars between our point to a point that is vertically/horizontally at a distance h should be equal to h. These points are (x + h, y), (x — h, y), (x, y + h) and (x, y — h).

    The following function check returns true if this condition is met.

    int check(int x, int y, int h)
    {
    	if(x + h > n || x - h < 1 || y + h > m || y - h < 1) return 0;
    
    	if(PrefixRight[x][y + h] - PrefixRight[x][y] != h) return 0;
    	if(PrefixRight[x][y] - PrefixRight[x][y - h - 1] != h + 1) return 0;
    	if(PrefixDown[x + h][y] - PrefixDown[x][y] != h) return 0;
    	if(PrefixDown[x][y] - PrefixDown[x - h - 1][y] != h + 1) return 0;
    
    	return 1;
    
    }
    

    After binary search-ing for the greatest height star we can make at a point, we have to find a way to store this result. We now create two arrays, DPRight[][] and DPDown[][]. We update our vertical results in DPDown and horizontal results in DPRight.

    We also store this (x, y, h) result in a vector ans.

    DPDown[x + h + 1][y]--;
    DPDown[x - h][y]++;
    
    DPRight[x][y + h + 1]--;
    DPRight[x][y - h]++;
    

    We can see that this is the prefix sum technique that allows updates in O(1) time. After doing this for all suitable points, we just need to take the row prefix sum for DPRight and column prefix sum for DPDown.

    Now we just go over all points (x, y) and check if either DPRight[x][y] or DPDown[x][y] is true. If not, then our answer is no. Otherwise, our answer is yes, and we can just print the contents of our ans vector.

    Code here: https://ideone.com/cPp2so

    Would love to know a better solution.

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

There is a problem that some of the E2 solution get the O(n^3),but we can't hack them. Because that a 1000 * 1000 square can't be saved as a test because it is higher than 256 KB:(

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

To me, Both E1 and E2 were 'easier' than D :( Somehow I messed up D after solving A, B, C. Read problem E1 and E2 after the contest ended only to realize they were easier for me. Lesson learned: Always read all the problems.

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

When does system test start ?

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

In question E2 if it would have asked to find the minimum possible stars too and if many multiple answers exist print any. Then how can we solve it any idea anyone?

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

I got two AC with the same code to E1,E2. I am regret not to do these two problem first

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

Messed up completely : B : Was printing C_(i+1) instead of C_(i) C : Taking input as a_1, a_2,....,a_n instead a_i b_i D : frustration after messing B and C

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

what has happened to the judger? it seemed that the test has stopped.

»
4 месяца назад, # |
Rev. 2   Проголосовать: нравится -15 Проголосовать: не нравится

У нас сломалась проверяющая система на системных тестах, поэтому этот раунд будет не рейтинговым. (Извините, я не знал в чем проблема)

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

Rip system tests :P

Did anyone else lose like 3 problems :/

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

спасибо за халяву в виде E2 :)

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

рейтинг будут зачислять или нет?

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

Hello,

  1. It says "_To qualify as a trusted participants of the third division, you must: take part in at least two rated rounds (and solve at least one problem in each of them),_", but, next paragraph says "_Regardless of whether you are a trusted participant..._" — so, which one is actaul?

  2. The following guys have participated just one contest and get rated, is it legal: http://codeforces.com/contests/with/Ka55un0

http://codeforces.com/contests/with/shanghaiKingCsl

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

    And why rating changes just for official differs from standings

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

    Basically, it's just that Trusted participants != Rated participants.

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

      Then the first paragraph is nonsense, right? What will be with non-trusted participants?

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

        Even if one is not a trusted participant of third division, they can still be rated. Non-trusted participants whose rating is less than 1600 will not be shown in the official standings table, but will be rated nevertheless.

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

          What does give/not give him and others not being shown in this table if he anyway affects others rating change? Do real cheaters care about it? The only thing they care is to get high rating change and feel himself as the most claver guy and decrease others rating. "Rating chage" shows them

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

            The point of the trusted participants is to exclude such multi accounts from the official standings table. Even though they still affect the ratings, yeah, but at least we are able to not see the top of the standings section full of multi accounts anymore.

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

Thank you Vovuh for the very nice contest :)

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

My Rank in Standing 799 But My Rank in Change Rating 902 I Think Something Wrong

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

    This is bcz of non-trusted participants :(. See above discussion for more info:)

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

I just want to know who is zhouenlai?

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

Hello, in problem F, why does this solution not work :

read n

read sring

get delta of string : delta"(("=2 ; delta")"=-1 like if you have "(" add 1 and if you have ")"

substract 1

get the minimum over all deltas :

code : 

int del=0;

int mi=del;

for(int j=0;j<sz;j++)

{

    if(a[j]=='(')

        del++;

    else

        del--;

    mi=min(mi,del);

}

than just fix where you want to fit it in

like [ poz, poz+sz-1 ]

I am giving you the code

link http://codeforces.com/contest/1015/submission/41118240 thanks in advance

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

Can someone tell me how to view GYM coming contests?

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

Почему в первых полных решениях только див 3, а во взломах все?

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

Conguratulations to halyavin of being the best hacker again!