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

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

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

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

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

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

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

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

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

Спасибо MikeMirzayanov за платформы, помощь с идеями для задач и координацией нашей работы. Задачи были придуманы и написаны командой Университета ИТМО: MikeMirzayanov, myav, Gol_D, Aris, senjougaharin, мной Vladosiya.

Также большое спасибо yorky, Jostic11, turmax, oversolver, ivanz, antonis.white, molney, KerakTelor, andrey.starodubtsev, Ahmad45123, myway, sofiaasta, Muhammad98 за тестирование раунда и весьма полезные замечания.

Всем удачи!

UPD: Разбор

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

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

Good Luck everyone! I hope everyone has fun!

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

Where is the link to register? I haven't participated in any of the rounds earlier. Can someone direct me, how to do so. Thanks.

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

Good luck everyone!

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

Good Luck to everybody.

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

I am competing tourist in parrallel universe.

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

Finally a div.3 round!!❤(●'◡'●)

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

For the guys who solved D. How did you reach the prefix sum observation? Had you solved similar problems before?

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

Good Luck EveryOne !!!

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

All The Best EveryOne !!

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

Hopeful this contest will be more friendly to newbies. Best of luck.

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

I hope it will be a great contest for everyone

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

I hope everyone has fun Good luck for everyone I hope it will be nice contest

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

I hope everyone has fun Good luck for all participants I hope it will be nice contest

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

Good Luck

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

Ollie gave

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

All my dreams are of an AK. (It only happened on a div 4)

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

    Agree with you! Me too having a dream to AK a div3!

    Now finally! I can participate in a contest.. after a long time (I had my exams). Hope this div3 would be last rated div3 for me! ;)

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

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

I am so weak that I can only get higher rating by div3 or div4 :(

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

I'm registered as out of competition due to rating rollback, when the contests start will I be considered as out of competition or what?

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

    No, only the rating while registering is considered. If you want to participate as rated, you can unregister and register

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

One person is missing is Vovuh :p BTW, Thanks Vladosiya and team for the contest.

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

How to do well in Div. 3? What's your opinion if someone fails to solve all of the problems..?

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

swap F G!!!

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

Hardest Div3 ?

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

I shouldn't work out problems from back to the front.

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

oh,how to solve tast D and E?It's too difficult!

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

    Problem D:

    Since |T| <= 100, you can find all substrings.

    While finding the substrings, loop through each string s and see if it is equal to the current substring. If it is, store its index, start, and end in a vector. This takes O(N^3).

    Now you have a vector of segments. The problem then becomes: find the minimum number of segments needed to cover a line, in this case, T. You can do this greedily in O(N).

    For each segment left of the current position, find the one that goes farthest right. Keep doing this until you reach the end or it's impossible to solve this case.

    My submission

    Sorry if if the implementation is bad. I was rushing.

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

      i do the same but not think greedly how to take minimum of them Thanks for sharing your submission

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

      Nice approach. I didn't think about this. I use DP instead. :')

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

        Can u please explain your solution.

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

          Let $$$dp_i$$$ be the minimum required string to color string $$$t$$$ where letters at $$$t_i$$$, $$$t_{i+1}$$$, ..., $$$t_{|t|}$$$ are going to be colored (all the letters from $$$1, 2, ..., i-1$$$ must already been colored)

          Then I will try all possible $$$s_j (1 \le j \le n)$$$ that can fits position $$$i$$$ (in other words, I will try to color $$$t_i$$$, $$$t_{i+1}$$$, ... $$$t_{i+|s_j|-1}$$$ using the selected $$$s_j$$$). To check which $$$s_j$$$ match, I use a simple pattern matching logic

          Then for the transition for the next $$$i$$$ (call it $$$i'$$$), I will pick such starting index so that all the letters between $$$1$$$ to $$$i'$$$ already colored

          In other words the value of $$$i'$$$ lies between $$$i+1, i+2, ..., i+|s_j|$$$. I pick those who gives minimum value and construct the answer.

          Therefore : $$$dp_i = min(dp_{i'})$$$ for all possible $$$i'$$$

          You can look at my submission for more details

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

      Oh god, I was thinking that you have to choose the substring covering the highest amount of still black characters and struggled to find a bug in my code, thank you for the explanation.

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

    Problem E

    If we add the first digit a certain amount of times, we always get 2 as the last digit

    • 11 + 1 = 12
    • 12 + 2 = 14 + 4 = 18 + 8 = 26 + 6 = 32 (see this)
    • 13 + 3 = 16 + 6 = 2 2
    • 14 + 4 = 18 + 8 = 26 + 6 = 32
    • 16 + 6 = 22
    • 17 + 7 = 24 + 4 = 28 + 8 = 26 + 6 = 42
    • 18 + 8 = 26 + 6 = 32
    • 19 + 9 = 28 + 8 = 36 + 6 = 42

    The special cases are 0 and 5, because

    • 10 + 0 = 10 + 0 = 10...
    • 15 + 5 = 20 + 0 = 20...

    So if any number has a 0 or 5 in the last digit we must check if all numbers with 0 as last digit are equal, and if the last digit is 5, we must add 5 and check again that all are equal. If a number doesn't have 0 or 5 as last digit, we can't do it.

    If not we increase every number to have a 2 as last digit and check if all a[i]/10 (the number minus the last digit) have the same parity.

    The reason: if you look in the examples, secondly we have 12 to 32, and to go from a digit 2 to the next digit 2, we must add 20, if we ignore the last digit (as we do in a[i]/10) we must add 2.

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

      "If we add the first digit a certain amount of times, we always get 2 as the last digit"

      Actually, the digits 2, 4, 8, and 6 will all work for this.

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

Please do a STRICT PLAG CHECK. According to me, D was quite tough , 2k submissions seems fishy

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

    Actually it isn't once you realize that it is a variation of merge intervals problem.

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

      Interesting. I just brute-forced (kinda) b/c bounds were really small.

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

    It's heavy implementation problem. Also A, B, C (and probably E) were really fast to implement once you got the right idea. So, in my opinion, that's why problem D got so many last second submissions (I've spent around 1 hour 30 minutes writing + debugging it and only got AC after the contest).

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

Why is C SAME as 1462C - Unique Number!?

Only difference is that in contest today x $$$<=$$$ 45 and not x $$$<=$$$ 50.

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

I think number of a div increased by 1 accidentally

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

Another Div 3 which I'm going to downvote. Authors think that they are preparing problems for Div 2.

D — good idea but shit ton of implementation.

E — couldn't solve but I think it's some casework which I absolutely hate, hence didn't bother.

Also, C = https://codeforces.com/contest/1462/problem/C. wtf?

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

    E is just being able to observe a certain pattern that arises when you keep applying the operation on a number.

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

    E is not about casework but observation

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

    E was a great problem that taught you about cycles without having to go into any implementation

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

isn't G just a simple dfs solution ??

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

I hate all those people who are expert or more and do not participate with their main account, But after all this was a round that I didn't like(just my opinion)

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

may i say this round is just a piece of shit ? div3 seriously?

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

How to solve 1714E - Add Modulo 10?

This is my submission. I have feeling I am either very far away from solution or like one line away from solution.

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

    So basically there is a cycle of ones digits, and if u keep adding u will eventually enter 2, 4, 8, 6 etc, which is a cycle of size 20. You simulate for every number until it reaches the digit that you choose, 2, 4, 8, or 6, and the difference between all numbers must be divisible by 20, due to the cycle. The other case is 5 and 0, which, if it's a ones digit with 5, u add the 5 and see if all the values are equal, because the 0 can not change the number.

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

Why is D so much implementation???

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

I have observed that number of submissions during last 10-20 minutes is too much high. Especially in this contest, I saw that submission rose too much.

Is this an indicator of cheating or are these really clutch submissions?

Also I don't understand how can problem E have more submissions than G. G was so straight forward, E atleast required some property of functional graph and heavy implementation.

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

U THINK F INTERESTING ? I came up with it in 5 minutes and get WA on pt 2 all the time lol

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

166589237

Can anyone tell why it is failing?

edit: nvm, got it

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

    That's too much of implementation. You can solve it easily if you measure time only in minutes

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

Why is my D giving MLE? 166596216 Will there be any more space efficient solution.

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

did someone notice that problem A — 1714A - Everyone Loves to Sleep was difficult than normal A problems

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

Solved ABCDE, got too tired to think about F or G lol.

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

I wasted approx 45 minutes solving D and implementing it was a hell . but it gets TLE and from the submissions it looks E was easier than D.

Can anyone guide me how to improve my rating as i am stuck here since very long

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

    E is implementation aswell, I don't know how did it got that many submissions, wait till hacking phase finishes then judge

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

Are hacks rated?

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

 Missed my AK~

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

Solved B and C, got stuck at A !!!!

Any hints for A ? Stuck at test 3

My Submission

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

    Convert times in minutes. Determine what happens if the current time is before/during/after each alarms and compute in minutes the difference of the current time and the alarm. Output the minimum difference in hours-minutes format.

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

    It will be easier if you convert everything to minutes and then output $$$ans÷60$$$, $$$ans$$$ $$$mod$$$ $$$60$$$ .

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

Amazing trick for looping through array or string backwards (used in todays B):

for(i=n-1; ~i; i--)

If you use ~i it will return false for $$$i=-1$$$ and true for all other $$$i$$$.

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

Is the purpose of A to scare people away from CP!??

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

Problem D = debugging infinite loops for an hour, at least thats what I felt and still couldnt find out whats causing it

Thats what happens when you nest while loops

and problem G, which I would have solved in 20-30 mins on LC using the standard recursive dfs approach, I didnt do it because I knew it wouldnt pass and idk how to implement that iteratively. Thats why my 2330 LC rating using pure python wouldnt matter here lol :/ same for two of my friends who used python only have 2400+ LC and 5 stars codechef but couldnt hit expert on cf

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

Wait, am i on next level or smth? Why so many people talk about A being harder then usually? Is it really that hard to observe, that you need to sum this day time left and new day time if m < M? Or what is the difficult?

No offence to ones who didn't solve it, but i am really curious.

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

    Usually A is one simple observation, and simple implementation. For this one you had to consider multiple cases and also figure out a way to quickly convert the hours into minutes and back again.

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

    Its just that, its a little bit confusing/harder to implement than B & C in todays contest.

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

In today's contest, these two users have the exact same code for problems E and F (the slightly harder ones), Chahel and goelarnav12. Please take action, as this is against the spirit of individual competition and is blatant plagiarism.

In fact, this is goelarnav12 's second offence. This user has plagiarised in the past. You can look at the "skipped" submissions. Kindly take strict action against these people.

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

submission : https://codeforces.com/contest/1714/submission/166593483 O(2*nlogn) gives TLE in the G!

my approach was , for every node get as much as you can for b we do a dfs , a goes from the front , and makes the path for the b and then for every node , while sumb < suma we increase the b , b can be updated at most n times , and so as a so the total time complexity is O(2*nlogn) (logn because I use maps for storing edge weights)

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

So, I registered, participated. Couldn't solve a single question. Bahaaha, almost hysterical.

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

Что такое "фаза открытых взломов"?

By the way, check out my problem C solution:

https://codeforces.com/contest/1714/submission/166538483

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

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

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

      Но разве тут не на полном наборе тестов проверяется сразу? При отсылке пишет не "Претесты пройдены", а "Полное решение".

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

        Завтра утром будет проверка на полном наборе тестов, а взломы тоже есть

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

        Проверка идёт на полном наборе авторских тестов, но каждый удачный взлом по задаче добавляется в список тестов, и по завершении фазы посылки перетестируют с учётом взломов.

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

Can anyone explain the dp method for problem D? Thanks in advance

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

Could someone try hacking my D? (https://codeforces.com/contest/1714/submission/166556061) Feeling paranoid now since I'll finally get to expert with this round probably, but seeing a lot of TLEs.

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

someone please help me in G my complexity is o(2*nlogn) but I get TLE submission : https://codeforces.com/contest/1714/submission/166597686 basically for every node , I increment the b as much as I can

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

    If your tree is a path then height is no lomger log(n) and your time complexity hits O(n^2).

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

      I tought it is still o(n) , like A traverses the tree and B comes afterwards , so there are a total of 2 traverses , what is wrong with that ?

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

    When you have a long path with short sum of b's for vertex v, which has a lot of children each requiring adding up all b's, yours becomes O(n^2).

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

      freehandle I didnt get it , can you giva a case , I will run jt on my machine too see how many operations does it make , btw I want to point out that : if vertes V's ancestors b is k , then to start searching for V's b , we will start the search from k , so it wont start from the root for every node to find their b's

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

        Exactly what I wrote is the case. Start a path with a = 1, b = 10^8, make a long path of length n/2 with a = b = 1, then make n/2 children at the end with a = 10^9, b = 1. For each children, you have to add up n/2 b's.

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

What is the point of such tasks as C? The stupidest precalc (166535760) solves them.

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

Why is my submission for Problem D failing on test 5? 166614128

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

    Your solution outputs 4, but you can solve it in 3 iterations (1 1; 1 3; 2 6).

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

C using recursion 166615609

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

In E Problem, I thought that if the last 2 digits are the same, those values can become the same after some finite operations, but it is giving WA. Can anybody help why my solution is wrong

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

Why am getting TLE in question B?

Trying to do it O(n) only :[

Solution

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

    You are failing this test:

    $$$t = 10^4$$$

    $$$n = 1$$$ for each test

    And for every testcase you create $$$10^5$$$ array, that means you do $$$t \cdot 10^5 = 10^9$$$ operations

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

    There are a few optimizations for your code. Don't use vector<int> freq(200001, 0). You can use map<int, bool> freq or set<int> freq.

    You might be thinking: but I cannot use those data structures because freq[a[i]] can be $$$2$$$. You actually can if you first check if freq[a[i]] == 1 (in this case same as freq[a[i]]) and if it isn't then increase freq[a[i]] by $$$1$$$.

    This way time complexity is $$$O(NlogN)$$$ because grabbing elements in std::map takes $$$O(logN)$$$ and std::set.count() also takes $$$O(logN)$$$.

    Your accepted solution using std::map: 166667859.

    Your accepted solution using std::set: 166668032.

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

I highly recommend watching neal's explanation for problem E if you don't know how to solve it.

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

Did anyone noticed that lots of the hacked solutions for D have almost the same code ?

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

Can anyone tell me what's wrong with the problem E? This is my code here.

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

    When a[i]%10==2 for all i, f doesn't get set

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

      If a[i]%10!=0 or 5, then all a[i] can be transformed into a[i]%10==2 by using the operations. In my code, f means if a[i]%10==2 exists, then if there is another a[i]%10==0 or 5, the answer should be no.

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

        Yes, f is meant to indicate whether a[i]%10==2 exists after the transformation, but f is not being set when a[i]%10==2 for all i in the original array.

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

was D intervals problem ?

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

Can anyone explain the solution for. problem E??

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

    There is a small observation.Say the current number is x. If x%10 is 2, and you perform operations you get a series. 2->4->8->6->2 so after performing 5 operations from any of these numbers you get back to the number itself with a sum of 20.Now suppose x%10 is 1,3,7 or 9. again if you perform one operation you reach 2,6,4,8 respectively.So the numbers become a part of the series.Now the only numbers which cannot be a part of these series are 0,5.So there are three cases.

    1. The array has numbers of the form 0,5 and at least one number from rest of the numbers.In this case the answer is No.
    2. The array has numbers only of form 0,5. In this case for the numbers having x%10=5 do the operation once.Now all elements end with 0 in the array, so no operation can be don further.Now all elements in the array must be equal for an answer to exist.If all elements are equal answer is Yes.Else answer is No.
    3. Now if all elements are of the form 1,2,3,4,6,7,8, or 9.For numbers having 1,3,9 do the operation once.So now all numbers are of form 2,4,6,or 8 in the end.Now as mentioned we can add 20 to any of these numbers without any issue. So we add 20 to all numbers such that the difference between all numbers of 20 is within 20.Now we try to make all elements of this array equal to the maximum element of the array using operations on each of the element. suppose the maximum element of the array is 38, We would try to make all elements of the array equal to 38 46 52 or 54.If is it possible to make all elements equal to any of these elements answer is Yes else answer is No.Note :we are not checking for 58 as if we can make all elements equal to 38 we can also make all elements equal to 54.

    For implementation details check this out 166574350

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

HAVE BEETHOVEN97 DONE MOST HACK IN CODEFORCES HISTORY?

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

    Hacking is not a very easy thing to do, it takes patience to look through everyone's code and attempt to hack it, and hacking so many solutions in every contest is pretty impressive. The man's a legend and i hope he doesn't stop.

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

"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."
Does this mean I could get some points from this contest if my rating is less than 1600?

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

Problem D can actually be treated as a graph problem using greedy and DFS or similar to solve. Just store the adjacent strings that satisfy the condition, do BFS, and backtracking. Though the implementation is awkward and the cases are trivial at least to me LOL,
166652986

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

    Ну и зачем всё так усложнять?)

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

      я вообще сканлайн написал...

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

        у меня тоже нечто на это похожее но решение на столько костыльное, что боюсь оно не пройдёт сист. тесты

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

          удачи! мое должно пройти, честный куб вроде как, и особо без костылей

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

            только жаль что так долго идёт тестирование(

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

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

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

                С большим количеством посылок наверное связано, ведь в div. 3 задачи решать легче, чем в div. 2...

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

Problem D can be treated as a graph problem and can be solved by greedy and DFS or similar. Just store the adjacent strings that satisfy the condition, making it a directed graph, do BFS, and backtracking. Though the implementation is awkward and the cases are trivial at least to me LOL. Checking out this solution if you want. 166652986

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

When will ratings come?

p.s. hopefully i get pupil :3

edit: yay i am pupil now :)

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

Why Rating not updated yet?

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

а че раунд как нерейтинговый отображается?

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

    потому что только через пару часов все АС сабмиты протестируют на взломах, и где-то ближе к вечеру обновится рейтинг — так всегда с Div3, Div4 и Educational раундами :)

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

Hello everybody! Can anybody tell me why my E problem changed it’s green color to red? Yesterday during the round it passed all tests and got “full solution” status… I suppose that it’s connected with “hacks” but I am new here and still barely understand the matter of that word.

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

Why am getting TLE in G link: https://codeforces.com/contest/1714/submission/166682000

the dfs is supposed to have TC of O(2*n)

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

    This solution is not actually O(n) since the two pointer system goes back.

    Imagine if the current position was 50k and the pointer was at position 1,

    Now you enter node at depth 50001 and the value is large enough to allow the pointer to move from 1 to 50k, that needs 50k operations, now you get to the end and go back in dfs to 50000, the pointer is back at 1 and when you another node at depth 50001 with a large value the pointer needs to move back to 50000 again.

    Worst case performance is (n^2)/4 or O(n^2) giving TLE.

    Edit: If you take a look at the test case that fails you can notice that the pointer will be stoped at value 1 while the tree continues going down in a tower with small values. At some point the values will become large again and the pointer will need to move back down a lot of times.

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

      But still the pointer will not visit any node twice right? Suppose we are at noode root then in all subtrees of root the pointer will only visit to the depth only once.

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

        This is not correct, when going from root to 50k the pointer will visit all nodes, when the dfs goes back the pointer will return to 1 and can visit the same nodes again.

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

      Hey your explanation was great could you also review this ? https://codeforces.com/contest/1714/submission/166712292 thanks in advance

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

        You seem to have a similar issue, the while loop inside your function that moves the pointer behaves in the save way that caused the issue I described above.

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

Does someone know what is test case 354 from test 2 at problem F?

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

My submission for G was considered as plagiarism even though I don't even know the other person. Compiled and tested solution locally. Please look into this MikeMirzayanov

https://codeforces.com/contest/1714/submission/166555725 https://codeforces.com/contest/1714/submission/166575418

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

Attention!

Your solution 166560427 for the problem 1714D significantly coincides with solutions aldol_reaction/166560427, Cx330_L/166571248. Such a coincidence is a clear rules violation. Note that unintentional leakage is also a violation. For example, do not use ideone.com with the default settings (public access to your code). If you have conclusive evidence that a coincidence has occurred due to the use of a common source published before the competition, write a comment to post about the round with all the details. More information can be found at http://codeforces.com/blog/entry/8790. Such violation of the rules may be the reason for blocking your account or other penalties. In case of repeated violations, your account may be blocked.

MikeMirzayanov Hello, the main function part of my code comes from https://blog.csdn.net/mashizuren/article/details/113345347

Me and cx330_ L is not consistent. I use KMP and he uses bruteforce. In interval merging, we use the merging method of this article. You can see that my code style is always the same for all the topics in this field. Please restore my place and return my score. I didn't cheat.

my: https://codeforces.com/contest/1714/submission/166560427 his: https://codeforces.com/contest/1714/submission/166571248

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

    anything happened? is the issue resolved , i too have the same problem and got all my code plagiarised

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

      He didn't plagiarize my code, we just refer to code from a same blog that was posted before. The problem is not solved.

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

My code is not working for a particular test case. Can anyone check! Thanks here's my solution: https://codeforces.com/contest/1714/submission/166584533

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

    Your second last for loop misses the final element (the condition should be i < n). It gets AC after fixing this.

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

Can anyone look and tell why is my solution for G is giving RTE for testcase 3? 166727901

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

Edit 1 : Thanks, I figured it out...

Can anybody kindly help me with this https://codeforces.com/contest/1714/submission/166761762 , this is my code for G which getting memory limit exceeded on test 3, I think either the way I am making the graph is taking more memory or the vector for B_i's I update everytime in dfs is taking alot of memory but I can't figure out how to do the problem without using the vector for B_i's and if anybody can see the tutorial kindly send me the link cause I can't see it (maybe its not out yet...).