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

Автор Vovuh, история, 3 недели назад, перевод, По-русски,

<almost-copy-pasted-part>

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

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

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

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

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

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

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

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

Удачи!

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

</almost-copy-pasted-part>

UPD: Я также хотел бы поблагодарить Ashishgup и kocko за помощь в подготовке раунда и тестировании!

UPD2: Контест будет продлен на 15 минут, потому что задачи оказались более интересными, чем мы ожидали. Также мы советуем прочитать все задачи, потому что некоторые из них могут иметь одинаковую сложность и мы не можем знать, какая из них будет проще для Вас, чем другая.

UPD3: Разбор опубликован!

UPD4:

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

Место Участник Задач решено Штраф
1 MbahFaishol1937 8 248
2 bertmin 8 450
3 BaiBatyr 8 455
4 LJF007 7 305
5 proizvedenie 7 322

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

Место Участник Число взломов
1 Nazarbek_Baltabaev 120:-90
2 Radewoosh 75:-21
3 yzm10 36:-2
4 csegura 31
5 shaker007 30:-11
Было сделано 798 успешных и 492 неудачных взломов.

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

Задача Участник Штраф
A blast 0:01
B Kirill_Kudr22 0:04
C I_love_HellHoleStudios 0:04
D divya_rawat 0:10
E llbra9z 0:13
F FlyInTheSky 0:42
G MbahFaishol1937 0:27
H UMP45 0:25

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

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

Забавно, как после недавнего блога о слишком большой сложности Div3 раундов с copy-pasted-part исчезла строка

"Наверное, участникам из первого дивизиона они будут совсем не интересны, а для 1600-1899 покажутся простыми".

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

why I m struggling in Div.3 ? how can I improve my DP & graph solving ability?

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

Hoping for a good contest!! Was awaiting Div3 eagerly.

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

"You will be given 6 or 7 (or 8) problems and 2 hours to solve them." It is so vague. Though It'll be decided later.

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

Div.Vovuh xD

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

I hope to become purple after this round!

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

you can safely stop doing these, they are useless. stop spamming the website

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

I find difficulties of problems from Div 3 are as same as Div 2!

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

    Why do u think so?

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

      It's from my experience from Div 2 and Div 3 contests I've participated.

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

        I dont think so. Probably, u cant solve 3 problems sometimes even when u`re blue, but in div3 u can

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

        I used to think the same when I was around your rating, but once you reach somewhere around 1500, you will notice you are able to solve 4 or more problems in Div 3.

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

        experience ?!!!! you mean solving at most 1 problem in more than 15 minutes in less than 10 contests ? are you sure you know what the meaning of experience is ?

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

        maybe it's right when you solve only 1 problem. My experience: 3 div.2 / 4 div.3 (year ago) 4-5 div.2 / 6-7 div.3 (now)

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

          OK, I got it. If I go to advance level I will get the difference. Thank you guys

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

    because you're so bad at coding. if you aren't advancing, why do you keep trying and wasting your time with this cp bullcrap? move on kid....

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

      I know what I'm doing. Didn't ask for your advice. Piece of shits everywhere

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

    The creators of the contests have sufficient intelligence to differentiate problems of Div 2 from Div 3. Trust them.

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

    That's because you solve only one problem during the contest regardless of whether it is Div2 or Div3. So you find both of them same.

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

Vovuh can stay on top of the contributors table just by organizing 1/2 Div. 3 rounds per month xD

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

Hope I will turn pupil after the round :)

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

Good luck everyone, i hope for a good contest for all of us.

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

Div 3 after long time.

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

Tired of helping Vasya and Petya !

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

when these persons are testing the round , the chance of hack comes down a lot !

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

The winner of this contest name will start with 'g'.

MyPrediction

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

DIV-3 contest is always missed by Vovuh. :D :D :D

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

Does the countdown work correctly? It says 7:05 before start!

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

wow new contest from vovuh

i love you man

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

The temperature is higher than my meme contribution

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

good luck everyone,hope your rating will increase

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

where are the problems

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

Unable to see the problems.

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

Not able to see problems. Is it only me ?

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

question is not opening

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

what is going on with interface?

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

why i can't ask an question????????????

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

Anyone else not seeing problem statements??

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

WTF

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

But where are the problems. Contest is running without any problem set

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

Oh time is running although there aren't any questions!

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

what's happening codeforces..

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

i can't see any problem

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

I cannot see the problems.

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

no questions?

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

Задач нет, а вопрос нельзя задать, потому что вопрос должен относиться к какой-то конкретной задаче :)

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

Problems??

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

problems aren't visible.. lol

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

Where are all problems? Are we a joke to you?

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

Hello, there is some issue. The problem set is not loading.

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

Why everyone is writing same comment of not able to see the problems ?

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

are there any hidden questions :(

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

I can't see any problems in contest main page.

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

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

can't view any problems??

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

Where are the problems, I can not see them

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

I cant enter in this round.Help plz

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

Why problemset is invisible?

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

Problems?!!!

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

So many submissions already and i am just receiving the problems... Will it be rated?

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

The problems were not visible and suddenly I saw 3000 people have already solved the first question

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

will there be extra time for the delay?

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

unexpectedly ez round...wish u guys good luck.

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

Yet another internet speed round XD

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

Queryforces

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

problem C is easy but hard to implement...

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

    < 10 lines in python for me

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

      Could you please explain the solution. I mean pseudo code

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

        You can consider the formula for how much additional charge you will need, where "out" is the number of days you don't charge: neededCharge = (out*a) + ((n — out)*b) — k + 1 Specifically, we need neededCharge to be less than or equal to 0, so we can set out based on that. Simplify to get out <= (k-n*b-1)/(a-b). So, set out = floor((k-n*b-1)/(a-b)) Then, if out is less than 0, your answer is -1. Otherwise, your answer is min(n, out).

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

    I am having understanding the problem, could you please explain the problem. I will really appreciate it. Thanks.

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

can any one explain problem D ?

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

    store array containing frequency of i in arr[i]. sort all values in reverse order, now for all elements after 1st element in array, its value is min(arr[i],arr[i-1]-1). Answer is sum of positive values in array.

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

Problem E is more easy for Java people

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

Thanks for the contest!

For anyone who had a hard time with any of the problems, I wrote up descriptions of my solutions, which you can find at this link. If you have any questions, feel free to post below.

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

    Thanks, I think it'd be a bit easier to read if you posted this as a blog and if you have the implemented code, to share it.

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

      Good idea—I’ll post this soon. Thanks!

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

        Geothermal {May be I am wrong}...

        I tried D using max-heap but at the 19th case the response was TLE .. but as you guys have used sort() method [complexity will be nlogn]. So, as Mine...

        https://codeforces.com/contest/1183/submission/56128383

        any suggestion where am I wrong???

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

          I'm not sufficiently familiar with Python to debug it effectively, sorry.

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

            Geothermal thanks for the response ...sorry, I don't want you to debug my code ... I am just asking whether max heap is a good way to solve it ..

            pseudocode:


            heap=maxheap(contains the frequency of distinct nos) start=maxheap[0] //max value while(heap not empty): val=heap(remove max value from heap) if((val-start)>=0): if(start>=0): count=count+start start=start-1 else: break else: if(start>=0): start=min(val,start) count=count+start start=start-1 else: break

            So, for me its O(nlogn) ... n for removing the elements and log(n) for maintaining the heap...??? am I correct?? ...

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

    Thanks for your effort. I looked into it. I found that explanation of Q.F was difficult for me to understand ( or maybe because i have used another method .) Can you tell me in short what you did ?

    My method : I found out during the contest that if there is a solution which doesn't have max element (let's say m) . Then the only better option can be m/2 + m/3 + m/5.

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

      Yes, I think we used different methods (although I know other people who used your approach too). That's a clever solution--my method was essentially a pruned complete search. I noticed that any number under 200,000 can't have too many factors (more precisely, they have at most 160 factors). This lets us considerably reduce the number of possibilities we have to search through, and from there the rest is essentially a bash.

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

        If I'm not wrong, you take 340 problems as a candidate for first problem , and for each of them you take next 170 as second and 340 as third candidate ?

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

          I took 340 problems as candidates for the first problem, then for each potential first problem, I chose 170 candidates for the remaining two problems. I then did some optimization so that I could pick the best pair of problems in ~170 operations rather than by considering all possible pairs of candidates.

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

    getting tle in test case 6 problem g https://codeforces.com/contest/1183/submission/56137010

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

How to solve G?

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

    Edit : This is for Problem H.

    Consider dp[i][j] -> number of distinct subsequences ending at i, of length j. Then,

    $$$dp[i][j] = \sum_{c = a}^{c = z} dp[prev[i][c]][j - 1] $$$

    Where prev[i][c] is the maximal index before i, that has value c.

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

Totally, I could not understand the problem C :(

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

    it takes me more than 40 min to understand :(

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

    You can consider the formula for how much additional charge you will need, where "out" is the number of days you don't charge: neededCharge = (out*a) + ((n — out)*b) — k + 1 Specifically, we need neededCharge to be less than or equal to 0, so we can set out based on that. Simplify to get out <= (k-n*b-1)/(a-b). So, set out = floor((k-n*b-1)/(a-b)) Then, if out is less than 0, your answer is -1. Otherwise, your answer is min(n, out).

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

    "For each query print one integer: -1 if Vova cannot complete the game or the maximum number of turns Vova CAN JUST PLAY otherwise"

    The maximum number of turns Vova can just play that is without charge and play.

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

How to solve E?

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

    dynamic programming dp [i] [j], the number of different strings of length i ending in j letter

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

      Could you explain how do you ensure that we don't count the same string twice while building the dp. Thanks in advance.

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

        Try to understand it yourself. Let's get another matrix used [i] [j], indicating whether there was such a state before. If it was, we simply reset dp [i] [j] and recalculate the answer for it since this time we will have more different lines of length i ending in j.

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

      Actually BFS is ok...

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

In test case 4 of E why cost int not 232 — 1*0 + 10*(10-9) + (C(10,2) = 45)*(10-8) + 44*(10-7).

UPD : Got it. I made a mistake.

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

why there was no hacking ? and when the ratings will come up ?

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

great round I would say but the complexity of the tasks > D is quite high for a Div. 3 contestants

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

Damn I could solve E I think.. isn't it trying all the possibilities and if it took too long we would output -1

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

    No its not you wold definitely get TLE or WA for that the solution . just consider a 100 letter string with same characters and k=99. you can use dynamic programming to solve it.

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

    Hahaha, trying all possibilities? Did you read "substring" instead of "subsequence"?

    Just as a side note, total possible ( without removing repetitions ) number of subsequences is $$$2^N$$$ where $$$N$$$ is the length of the given string.

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

      Did you read reza comment .. yeah I get it and I know the possibilties could be large but I thought if we didn't find 100 substring after 1e8 possibility then there's no answer but as reza said 100 same letter wouldnt work with this way

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

        Oh my bad then. But you didn't clearly mention what you were going to do? I accept I misunderstood here, but you should have said something like "Since $$$K$$$ is small, we can just find those many subsequences and then stop". This gives better idea of what you were trying to convey.

        Anyhow, I must apologize for my misunderstanding. Sorry for that! I shall read more carefully from now on.

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

Не знаю на сколько нормальным тут будет этот вопрос... Но на тест 20 5 7 3 в проблеме C ответ 1... Почему, если 20 — 7=13(осталось зарядки, после 1-го хода), так мы можем ещё из 13 вычесть 7(выполнить 1-е действие), почему ответ 1, почему мы можем просто играть лишь 1 раз?

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

    Потому что если мы играем 2 раза тогда (20-7*2=6, 6/3=2 ,2+2<5) мы не можем закончить 5 раундов.

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

can I hack my own solution???????

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

Последняя снова сложная, я даже думал, но все равно не решил.

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

Thanks for the contest!

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

Why am I not a trusted participant since I have participated in more than two rated rounds and never had +1900 rating?

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

The user CaNDidaTE_FaSTer cheated again.

He somehow find the solution of problem H of sraman915

Submission by sraman915: 56104958
Submission by CaNDidaTE_FaSTer: 56124086

I think he should be banned from Codeforces as he did cheating multiple time. The another cheating caught by me is here

I am drawing attention of MikeMirzayanov

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

    Who are you LE_ROI? :D :D :D If you can prove this I will give you everything in this world. Please don't wast your time to see other code. Nijher chorkai tel dao. Copy past codeforce onek valo dhorte pare. I don't know who is sraman915. Hey Sraman are you know me? LE_ROI are you man or woman? :D :D :D

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

    The question is all about finding the distinct subsequences of length K. after that one can easily figure out the solution. I googled it and found something relevant which I have also mentioned in my code.

    I don't know CaNDidaTE_FaSTer but after seeing his solution I think he has also used the same thing but he forgets to mention in his code.

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

      Yes, you are correct. But I don't copy and past. I just use google to find out finding the distinct subsequences of length K . Thanks you sraman915.

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

      Hey. I have also taken code from that site, although I was not sure whether I should use that code. Are we allowed to take code from other sites during contests?

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

    It seems he has copy and paste code from Internet source. It is clear from inconsistent indenting. Many people have done this. I don't believe he has cheated.

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

TIL that declaring a massive vector makes a big difference in time complexity. (vector (MAX)) https://codeforces.com/contest/1183/submission/56113733

https://codeforces.com/contest/1183/submission/56126400

https://codeforces.com/contest/1183/submission/56126075

https://codeforces.com/contest/1183/submission/56126321

I thought that declaring a vector only takes up space and not time.

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

TLE https://codeforces.com/contest/1183/submission/56117801 AC https://codeforces.com/contest/1183/submission/56126830 The only difference between 2 submissions is I declare the array inside main

Why I got TLE ?

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

    Have a look at my submissions I got plenty of TLE's for the same reason on D. When you declare your array globally of size 2e5 and when there are 2e5 queries it will become O(10^10) because you are initially array of size 2e5 everytime. That's why array should be dynamic to take advantage of the fact that the sum of n over all queries is <2e5.

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

How to solve G?

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

When I tried to hack others solution with my testcase.I am getting generator crash error Since it is valid. My test case is : : test case

(for Problem D )

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

    It is because you are generating a testcase with 200000 queries where n=200000. However, in the problem statement, it is mentioned that "It is guaranteed that the sum of n over all queries does not exceed 2*10^5 ".

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

Hello i am very new to codeforces will anyone tell me that after participating in div 3 and solving 2 questions why there is no effect on my rating??please tell me Thanks :)

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

can anyone explain..how to use DP in problem E?

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

    Sure. Sub-problem : Count number of distinct subsequence in a string ? Sol — I'll use 1 based indexing. Let DP[i] be the number of distinct subsequnces ending with character s[i]. Then if character s[i] did not occured before then we can chain it to all distinct subsequence occured before this position i.e. we can freely choose second last position in our subsequence DP[i] = sum of all DP[j] for j < i. If s[i] occured before then we don't need to count second last position before last occurence of s[i] because they are already calculated DP[i] = sum of DP[j] for prev[i] <= j < i. where prev[i] = last occurence of s[i]. Base case is empty subsequence. DP[0] = 1.

    Original-Problem — Just add length state in DP. DP[i][j] = Number of distinct subsequence having last character s[i] and is of length j . Base case DP[0][0] = 1.

    This solution is O(n^3) but can be optimised to O(n^2) by calculating prefix sum DP for each length layer.

    While finding best cost in problem : Start taking subsequence with maximum length.

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

very nice round . congrats

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

Can somebody please explain the graphical approach to problem E?

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

queries round.

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

can somebody explain how you think problem B solution thanks in advance

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

    Take the item with the least price, if you increase this price by k, you will get the maximum price this item can be given, Now the range of prices for this item will be, assume price as 'a', [a,a+k], Now look at the item with the maximum price, you can change it's value to anything in the range, (let price be 'b')[b-k,b+k], if you take intersection of these ranges, you will get the range in which all prices of other items can be brought to,i.e, each item in the array can be brought to some price in this intersection, the maximum of this intersection will be the answer.

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

    In B we have a sure move to maximize the common price, if that is not possible there can't be a common price.

    After sorting the prices, if we increase the smallest price by k(maximum possible increase), and if the product with largest price is less than a[0] + 2*k, then there exist an increment or decrement of a value less than k to reach that maximum possible price. But if the product with largest price is greater than a[0] + 2*k then there is no such price that the smallest and largest initial price product can have in common.

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

    thank you

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

Can someone please review my solution for B: https://codeforces.com/contest/1183/submission/56089281

I think I got lucky, since I don't even know what I was intending to do. My logic made sense in the start, and I kept changing the conditional to pass the example input.

Perhaps it will not pass sytem tests.

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

    I think your solution is correct. After sorting the array, to print (a[0]+k) as answer, we need to just check if (a[n-1]-k)<=(a[0]+k) or (a[n-1]-a[0])<=2*k. Instead of checking only for a[n-1] (or max element), you are checking for all elements which is not necessary. So it should pass system tests.

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

      Thank you for your reply. Yes I noticed this too. I wasted time being confused with myself. I fully understand it now.

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

Problem statement of C was not good, it took me around 30-40 minutes to understand the problem statement.

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

In the third problem, when I submit the solution with pypy I am getting TLE(time limit exceeded) in test 27 but when I use python 3 my solution is getting accepted. What is the difference between them and why did coordinators asked to use pypy??

edited: Solution with python 56132978 Same solution with pypy 56130341

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

    I did some research and found out that the problem is += when I tried solving with replaced += in pypy my solution was accepted.

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

Good round and good tasks. Thanks, Vovuh!

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

Will hack score?

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

.

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

How can I figure out what's wrong with my code when I get a WA on a mile long test case?

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

    Create a program that generates a (small) testcase, generate one as long as your output equals to the output of a bruteforce/copied model solution.

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

      The solution itself is more or less bruteforce plus I tested the code for a lot of small cases by hand so I'm really surprised that I get WA

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

The best div 3 I ever seen. But different in complexity between D and E was too hight.

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

Hey codeforces ,

Please check my blog where I have revealed a big fraud that happened in today's contest !

What these two users did is just unbelievable, I hope MikeMirzayanov will do something about the subject.

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

problem G getting tle on test case 6 https://codeforces.com/contest/1183/submission/56137010

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

My solution I'm getting trouble with problem B. Could anyone tell me what's wrong with my approach?? please...

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

When will the problem analysis be published?

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

any help pls!,why this code fail in test 3 problem B? https://codeforces.com/contest/1183/submission/56142029

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

how to solve E?? plz someone explain it in simple words

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

    Use breadth first search. Nodes are strings. Edges is removing one character from it. Use map or set to remove duplicates.

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

    For E u can simply bruteforce...Generate unique strings by deleting 0,1,2,3... characters from given string until size of 'S' becomes K... To generate all string u can use a queue of string and push the given string into it now take the front of queue, generate and push all unique string by deleting a character from it. Repeat this until queue becomes empty... You can refer to my submission

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

Are all the solutions rejudged? I had solved 3 problems but now it is showing none. What is the issue?

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

One of the worst contests ever. Terrible test cases, and for some reason, all questions had the same weight which doesn't make any sense.

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

Does our rank go up if we do successful hacks?

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

Editorials?

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

Interesting problems.

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

systems message:"Внимание! Ваше решение 56108275 по задаче 1183E значительным образом совпадает с решениями других участников и находится в группе одинаковых решений lukamosiashvili/56108275, Whatever.../56123536. Такое совпадение является явным нарушением правил. Отметим, что непреднамеренное утечка тоже является нарушением. Например, не следует пользоваться ideone.com с настройками по умолчанию (публичным доступом к вашему коду). Если вы имеете неоспоримые доказательства, что совпадение произошло по причине использования общего источника, опубликованного до соревнования, то напишите комментарий к посту о раунде со всеми деталями. Подробнее можно прочитать по ссылке http://codeforces.com/blog/entry/8790. Такое нарушение правил может являться основанием для блокировки вашего аккаунта или других штрафных санкций. В случае повторения нарушений, ваш аккаунт может быть заблокирован." I can not wonder how he copyed my code, because I not gived him my code.

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

Where Is The Editorial?

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

any editorial/tutorial please? :)

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

The test case in problem c on which my code was hacked is showing same solution on one of the correct submissions .Are there any other reasons of a code getting hacked ?

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

Where can I get editorial of this contest?? Plz help

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

Can someone please explain how to solve the last problem(H)?

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

Wow, this is my first time on the list!! Happy:)

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

This may sound dumb but I still dont understand Problem C- Computer Game. What is different between output 0 and -1?

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

    NOTE: In the first example query Vova can just play 4 turns and spend 12 units of charge and then one turn play and charge and spend 2 more units. So the remaining charge of the battery will be 1.

    doubt: TEST CASE: 15 5 3 2 If Vova can play 4 without charge and then 1 turn with charging then why is output 4?

    Help would be really appreciated

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

      It’s all based on the completion of this game. In worst case you may output 0, otherwise output -1 when Vova cannot complete anyway. Vova can complete only if after each of n turns the charge of the laptop battery is strictly greater than 0. If it is equal to zero, it can only output -1, but it is not good.

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

      The answer that the setter is looking for is the maximum number of turns Vova can play without charging, so the last turn (the play and charge turn) does not count towards the final answer. That makes the answer 4 instead of 5.

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

I am a begginer and most of my codes face TLE.Please suggest?

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

If you are Python programmer, consider using C++ instead of Python when you submit your code

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

what is wrong in my code;

include

using namespace std;

int main() { int a,n,b,d,c; cin>>a; d=a; while (d != 0) { b = d % 10; c = c + b; d = d / 10; } if((c%4) == 0) {cout<<a; } else {n=c%4; a= a+n; cout<<a;}}