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

Автор vovuh, история, 4 года назад, По-русски

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

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

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

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

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

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

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

Спасибо MikeMirzayanov за платформы, помощь с идеями для задач и координацию моей работы. Спасибо моим очень хорошим друзьям Дарье nooinenoojno Степановой, Михаилу awoo Пикляеву, Максиму Neon Мещерякову и Ивану BledDest Андросову за помощь в подготовке и тестирование раунда. Также спасибо Артему Rox Плоткину и Дмитрию _overrated_ Умнову за обсуждение идей и тестирование раунда!

Удачи!

UPD: Спасибо infinitepro, nuipojaluista, MrReDoX и Peinot за тестирование раунда и отзывы о задачах!

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

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

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

vovuh orz

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

is it rated?

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

Any idea why are problem ratings not getting updated for the past three contests?

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

imagine 8 problems for a div 3 ...

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

About 50 minutes after this announcement was published, the user MikMirzoyanov posted a fully copied text of it. Unfortunately, it is only in Russian. However, he almost immediately replaced it with just a call to participate in the round. But still, it was really strange.

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

Vovuh rounds are best to learn math, implementation and constructive for a beginner like me as I can hardly solve up to D in Div 3 rounds.

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

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

did you decide to bring in the problems from the next div3 contest to this coming one ? cuz there are eeeeeeeeeeeight problems ! o_o

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

I will try my best to solve problems even though i suck at this, i wont give up i believe that i can improve :).thank you for this div 3 rounds

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

![ ](IMG_20200928_122319.jpg)

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

Note that the start time is usual.

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

    I first read it unusual and scrolled up to verify the timings..got confused..came down and then read it correct.

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

Has it been confirmed anywhere that the number of problems in the contest is 8?

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

Has it been confirmed anywhere that the number of problems in the contest is 8?

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

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

[]memem.png

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

Подскажите пожалуйста, что такое 12-ти часовая фаза открытых взломов?

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

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

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

Please this time wanted SHORT statements and a STRONG pretests for DIV3!! Interested for the contest hope to get expert this time (done lot of practice indeed) !!

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

Hello everybody, I have a question that might seem ridiculous to you but as I am still a pupil I think it is ok to ask it. When inputs are like 4 3 2 4 6 2 7 9 4 and 1 2 3 4 Should I use cin differently? I mean in the first, there is a number in first line, and then 4 numbers in the other lines, but in the second one there is only one input number in each line. Thabk you in advance for your help.

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

    The comment did not share well. but it is like the first line: 4, second line: 3 2 4 6, third line: 2 7 9 4. and the other one, first line: 1, second line 2, third line 3, and etc.

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

      Above the editor box are some icons, try them, they wont bite you. Look out for "Block" and "Inline".

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

      no you can use cin as it is, and you can also verify it by actually trying it out

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

        I do not want to give unecessary pressure, but you know you are expected to make a big jump back to blue today, don't you?

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

          yep, that's why I initially decided to not attend,because of pressure,then I thought chuck it!Iam in

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

Wait !! I also want to be a tester. Someone knows how it is possible ?

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

26 minutes left time to be ready : )

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

Are these tester comments trendy presently?

Either way, here are my views on the contest.

  • Balanced.
  • Interesting problems.
  • Not implementation heavy.
  • A bit on the easier side, compared to previous div3 contests by vovuh.

Nevertheless, a fine problem set for a div3. Good luck and have fun!

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

Good luck everyone

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

Will solutions judged again after contest finised?

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

How can a participant be a trusted participant ? because on contest it shows me in unofficial standing ? and i'm just a newbie

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

    you need to take part in one or two contests to become a trusted participant.

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

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

Hope this round will remain rated :)

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

Sigh. I solved A and B in under 12 minutes but couldn't solve C in the next 2 hours. There must be something wrong with the way I am practicing.

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

    I used to be really bad for the first 2 months, today I solved 5 problems so don't give up and keep practicing. Unless you're doing problems below your current level, there is no wrong way of practicing.

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

    Meh, it happens, there are days where I fail to solve problems rated 200-300 below my current rating in contest. Don't be troubled by it too much. Rather analyze where you went wrong and what you can do to improve on it in the future.

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

    Yeah I coudn't solve B and C at all after solving A in the first 5 minutes. For B i kept on trying to simulate the process but kept on getting WA. Is there a better way and are there other questions that are similar to B?

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

      My solution to B was just (the spread of the ones)-(the number of ones) assuming the ones are not already stuck together. Eg: For 0010101, 5 — 3 = 2.

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

Hope Mike won't plag me today again xD.

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

What about D & E

was for solving D any knowledge of graph theory need??

and what is the procedure of E

any one tell me please the procedure of this two problem.

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

    E was simply (C(N,N/2)*((N/2 — 1)!)^2)/2 AND FOR D no just make a star graph.

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

      i don't have any knowledge about graph that's i ask is there any other process to solve that

      would please explain E to me?

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

        See number of ways to pick N/2 people is C(N,N/2), where C is binomial coeff. Now to arrange them in a circle such that each time a different circle is formed is given by standard formula of circular permutations which is (no of objects — 1)! Here no of objects = N/2 and since there are 2 groups both of them get multiplied to get total number of ways hence a square in the factorial term. Now multiply this with our C(N,N/2) and you are almost done! Also you need to divide by 2 since you also chose the reverse order in the process.

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

        For D you can make a star graph by connecting all the non equal elements wrt center of the star.... to the center of the star and now only the elements having value equal to number in center of star remain. Connect these elements to the to any other vertex of the star other then the center and you are done. Answer is always YES if atleast 2 distinct elements exist.

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

    I was thinking of a birpartite graph with coloring, but it wasnt, just search for a pattern.

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

    D: Knowledge of bipartite helps in a way. If all numbers are same then answer is NO else YES. Then you can join first node to all nodes which don't have value a[1]. For other nodes having values a[1] connect them to any one of the nodes having value not equal to a[1].

    E: I just did OEIS. Too weak in maths. ;_;

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

anyone else solved E using OEIS?

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

    Problem E

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

    Did you?

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

    I was tempted to but the derivation was actually pretty easy.

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

    When I'm given a number like n=20 is 12164510040883200 I just can't resist going for OEIS. Never even read the problem, I just went directly for OEIS 96121869.

    Then Codeforces kept showing me popups over and over about announcements about issues with the problem description. My secret to success was to never having read the problem description in the first place xD

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

      How do you search in Oeis? You just put 12164510040883200 in the search bar then choose first result that comes? or what?

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

        I just searched for 1260 12164510040883200 and scrolled down until I found what I was looking for (the sequence in E turned out to be the 2nd search result).

        You can read about different ways to do searches here. You can do for example this (shows all sequences containing 1,3, 1260 and 12164510040883200) or this (searches using wild cards).

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

This contest is a nightmare for higher specialists, many solved 5 still their rating will decrease.

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

Anyone know? Which formula is answer of E problem?

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

    ((n-1)!)/(n/2)

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

    $$$(n-1)!/(n/2)$$$

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

    It is "(N-1)! / (N / 2)" but I have no idea why

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

    ll ans = nCr(n, n/2) * pow(fact((n/2 )-1), 2)/2;

    First calclulate number of groups possible (of half members each) by nCr(n, n/2), then use formula of circular permutation i.e. (n/2 -1)! to find number of ways to arrange people in a group. (n/2 -1)! * (n/2 -1)! would give the ways for both group. Now divide the product by 2 as there be would be possibility of group A,B and B,A.

    eg. n = 8 , ways to make group of equal people = 8C4 = 70 AND ways to arrange people in one group = (4-1)! = 6 AND ways to arrange people in 2 groups = (6 * 6)/2. Final answer = 70 * (6*6)/2 = 70*18 = 1260

    edit: And we can simplify this to the formula many people used, although I took too much time in D and could not submit E in time

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

What were the solutions to F and G?

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

If Div3 is a contest in which we'd like Div3 participants to solve the entire set, this seemed like the perfect one.

I dislike problem E because it felt easier than B (to me and maybe others too considering the number of solves). F seems pretty easy if the constraint of M/2 is omitted and we're supposed to find maximum sum divisible by K in each row. How do I stay within the constraint? I'm thinking 3 state dp maybe. Any ideas on how to solve G?

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

    For F, it is simple to reduce that difficulty in your idea, do an auxiliary dp for only col counting the state for checking M/2. Extract optimal and use it to update main dp.

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

      I looked up your solution after you posted the "Why would you give a problem...." comment. It's very elegant. Understood, thanks!

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

First time solved 5 :) and spend 1 hour in F but not able to get AC.

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

I think the tests in Problem F are weak as printing the maximum sum minus (maximum sum) % k is giving Accepted.

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

How is second test case for G giving 13 ??? shouldn't it be 16 by reducing edge (2,3) to zero????

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

    They took a path which wasn't in any of the shortest routes. After making it 0 it became a part of the shortest routes.

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

$$$E$$$ — OEIS

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

    Can someone tell me how to use OEIS, especially when I don't know the whole sequence(contigous sequence) of numbers.

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

      for this problem, they gave the answer for 2, 4, and 8 so I just find the answer for 6 manually and then search that series on Oies.com, it simply gave me a formula which gave me AC

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

      Use underscore, like for the given problem you can search something like 1, 3, _, 1260.

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

Why would you give a problem like F in a serious contest?

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

    To be fair I don't think any significant number of participants < 1600 rating would have come across the idea. Anyway Div3s are fairly educational in nature, E / F is often a problem which can easily be condensed to a standard idea.

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

      Yeah, but F should not be solved by 250+ peoples if we see the other div3s. And yeah, it was educational. I was getting struck in implementation with fake updates cause I initialized everything with 0. Probably that's why they put it in F.
      But, a lot of people dance between blue and cyan so this probably gives unfair advantages to them.

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

        Yeah fair enough, maybe the idea is more common than I realize. I just felt that way since I didn't actually come across this idea till I was around 18-1900.

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

Can anyone tell what's wrong in my code for D?
my approach: if all elements are same, then answer is NO,
else find the min element index, find the max element index. bring the min element to first index, and then print from second index with following condition.
if arr[i]!= minimum element print i min_index (i.e. i 1) else print i max_index
UPD: got it. I was changing index's value.

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

There is always a problem which doesn't allow to increase rating. This time it is F.

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

I want to know if anyone bothered to simplify the answer of E to (2*(n-1)!)/n.

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

    You can't simplify it further. It's a factorial. Maybe you could write the mathematical notation to make it look clean but that doesn't help programmatically.

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

Solved 3 problems for the first time, Is this round easier than usual or have I improved?

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

It was a great Div4 contest!

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

Search 12164510040883200 on OEIS, and you will find the answer in the first sequences of the searching result — A110468

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

    You could have simply chose to not post that. I feel incredibly stupid now as I calculated it for every n using the formula and wasted more than 30 min :facepalm:

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

      A lot of people solved it by hand. There's nothing to feel stupid about it. I did it too (although I took only 10-ish minutes proving at 3-4 implementing). Although those who did search for it are at a slight advantage in the contest, it's insignificant over many future rounds. At least you were able to prove why the formula is correct and not blindly copy it from elsewhere.

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

It took an Eternity to understand E :(

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

Anyone solved the problem D using maximum spanning tree where weight = abs(a[i], a[j]) ?

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

Can someone explain E?

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

    1- you want to know how many times you can divide n people into to n/2 teams. The answer is nC(n/2). But, for every time you choose a n/2 number, you leave another n/2 (aka you choose them too into a different team). So, the answer will be nC(n/2) / 2.

    to give a quick example, say n = 4. One way to choose 2 people is [1,2] (which leaves [3,4]). Another way is to choose [3,4] (which leaves [1,2]). They are both the same. So, we divide by 2.

    2- For every team, you want to know how many times u can rearrange it (without changing the members) to form a different team. this is basically (n/2)!. Realize also that every ordering will be repeated n times. for example, [123], [312] and [231] are the same. so, it's (n/2)!/n.

    So the answer is nC(n/2) / 2 * (n/2-1)! (how many times we can reorder the first team) * (n/2-1)! (how many times we can reorder the second team).

    I hope this helps.

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

      Yes now I understand. I was able to get the first part but could not find the number of possible arrangements in each team.

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

Basic idea of problem C (atleast what I thought): The dominant piranha is not present if all elements are same. Whenever all the elements are not same, there will exist one or many piranhas with the greatest weight , one of these must have a neighbour which has weight less than maximum value ,that index is one of the answers. But my code gives wrong answer, Clearly there is a silly mistake in it , It would be helpful if someone could point it out my submission

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

Someone explain solution for F pl.

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

    Let's cald dp[n][m][C + 1][j], where is first two are position of current element, C — count of taken element it that row and j — remainder of divison of k.

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

I somehow get to manage the formula for E (only god know what logic I applied.. actually I tried to fix random factorials lol) but dont have a intuition for that. Can someone please help me with the intuitive proof for the same ?

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

Why so many hacks in F?

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

Can anyone please help me by telling that where my code is failing for B, I am unable to find it. Code

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

Just searching for the output of the last sample leads you straight to https://oeis.org/A273878.

Finding answers after typing out a series on OEIS is alright, but just getting it from one output, which is given in a sample, is not.

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

SS.png
How to submit all problems at the same time without a gap of even one second ?

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

how to do b?

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

too many people solved too many questions ;-;

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

Just google searching the output to the last sample on E (n=20) leads you straight to https://oeis.org/A273878.

Getting answers from OEIS after typing out a series is alright, but with just one number, that too which is given in the sample, is not.

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

    I hate OEIS...I solved it with a smooth PNC method and got it right 3 sec after contest ended :(

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

please tell what is wrong with my solution it is showing run time error with exit cod=2147483647 https://codeforces.net/contest/1433/submission/96165473

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

Authors tried hard so that formula for E do not reveal directly , but "a ninja must see through deception" :) . Nice problemset.

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

Amazing problems. Thanks to all the testers and problem setters for wonderful problems.

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

What an absolute stupid contest! No thinking, no DS, nothing. Just some stupid observations and you're good to go. Why do you even frame these type type of problems? Just say like — Print numbers from 1 to n. It will be a lot better to solve. Seriously, even Leetcode contests are better than these contests, atleast they require some thinking and implementation, and DS. But here, just put some if-else conditions in problem D which is supposed to be a good problem, and you're done! Absolute waste of time and effort.

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

What is the intuitive proof of E ?

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

    There are cnk(n, n // 2) // 2 ways to split people into groups of size n // 2
    Now there (n — 1)! ways to arrange people inside each group

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

$$$F$$$ was awesome :).

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

    then please give me some insight to solve it, how you started thinking about it and how it end, please if you can

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

such a good div3 round !

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

in open hacking phase, is there penalty for Unsuccessful hacking attempts? if i hack someone, will i get points or something?

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

Problem E had only 19 possible inputs and you give 4 of them in the samples?!
I think Codeforces is advertising OEIS.

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

what is the solution of D?

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

    Maintain a count for how many cities are under a bandit gang and indices (using map preferably). Connect all other gang cities to one city.

    Example: [1,1,1,2,2,3,3,3,3]

    Counts: [1: 3], [2: 2], [3: 4]

    Now, connect all cities under gang 2 and 3 to one city in gang 1. For the two remaining cities under gang 1 (notice 1 city of gang 1 is already used up in previous connection), connect them to any other city distinct gang city. Implementation is simple.

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

Can someone explain me why this output gives WA for 1433D - Districts Connection in the first test case:

My submission : 96170947

I also didn't understand the verdict.

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

    1 1000. You have to print the index, not the values.

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

      I think you answered someone else's query in my comment :3

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

        No, I saw the participant's output for your submission, for 3rd case, it has one extra output line 1 1000, the checker was expecting a string "YES" and you provided space-separated integers.

»
4 года назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится
  • in problem c
  • How this test case :
  • 4
  • 7 1 4 3
  • is 1 not 3 ??
  • Test 2 (14)
  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    1 and 3 is wrong answer

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

    The biggest piranha can eat all other piranhas. So 7 at index 1 can eat everything else. However, 4 at index 3 (what you say) can not because it will only get to size 6 after eating piranha with size 1 and 3 and it can't eat 7.

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

    Initially the pirhanas are 7(indx1) 1(indx2) 4(indx3) 3(indx4).

    NB: don't be confused. 1st element's index is '1' not '0'.

    if your ans is 3 that refers to index 3, that means the pirhana of size 4 will be the last. But it will become 6 at its peak which is still smaller than 7. So ans will be for 7, so ans = 1.

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

Felt todays contest more inclined towards fast speed rather than logic building :(

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

    Yep, Div. 3 is hard for those familiar with OI mode contests (where speed doesn't matter as long as you get the points)

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

I am getting TLE in F. Can anyone tell me how I can improve my solution to pass in time limit constraints.

Complexity: n*m/2*n*m*max(a[i])

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

I am getting TLE in F. Can anyone tell me how to improve it?

Complexity of solution: n*m/2*n*m*max(a[i]) Edit: Link updated

Edit2: Used the above approach with modulus for removing unnecessary values and got AC and also complexity becomes O(n^4)

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

Can anyone give me the tutorial of F please ?? ACtually i need the explantion of any solution approach

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

My solution was hacked too :p :p

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

Why so many hacks in F? What is the hack case?

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

Lesson from Problem F: Don't be greedy. Be dynamic.

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

Test for problem F 2 2 4 1 1 1 2

ans = 0

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

Yet another HackForces?

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

I don't quite understand question F. This is the code of WA in my game https://codeforces.net/contest/1433/submission/96164623 This is my AC code after the game https://codeforces.net/contest/1433/submission/96173437 The only change is that I changed MAXM from 70 to: int MAXM = (70 / k + 1) * (70 / k + 1) + 5; if (MAXM <140) { MAXM = 141; } Although there may still be a problem, it is ac for the time being. (I guess if MAXM is set to 4901, it will definitely be ac, but it will time out), I don't understand. According to my understanding, the total status will not exceed 70. How is this going? Is there any kind person to answer? Thanks in advance.

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

How to solve problem G?

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

    First of all, lets just forget about setting the weight of an edge to zero for a second. So we want to find the shortest paths for all courier routes. Floyd Warshall might come to mind but $$$O(n ^ 3)$$$ is not likely to work here with $$$n \le 1000$$$. However we have an additional constraint on the number of edges, $$$m \le 1000$$$. So we can just Dijkstra from each node to get all distances in $$$O(n * m * log(n))$$$. Lets call these original distances $$$original(i, j)$$$.

    So now that we have these original distances lets get back to the main problem, how do we find the answer for setting an edge weight to zero? Well suppose we set the weight of an edge {$$$u, v$$$} to 0. Then for each courier path one of the following must be true:

    • The courier path doesn't use this edge, i.e., $$$d(a_i, b_i)$$$ = $$$original(a_i, b_i)$$$.

    • The new courier path is of the form $$$a_i - \cdots - u - v - \cdots - b_i$$$ or $$$b_i - \cdots - u - v - \cdots - a_i$$$. Since $$$original(u, v) = 0$$$, we get $$$d(a_i,b_i)$$$ = $$$d(a_i, u)$$$ + $$$d(v, b_i)$$$ or $$$d(a_i,b_i)$$$ = $$$d(a_i, v)$$$ + $$$d(u, b_i)$$$ respectively.

    We can just again use dijkstra from the vertices $$$u$$$ and $$$v$$$ (this time ensuring we don't pass through the edge {$$$u, v$$$}) to calculate the distances for the second case in $$$O(m * log(n))$$$ for each edge. After this we can just take the minimum of these three values to value of $$$d(a_i,b_i)$$$.

    So we can just iterate on each of the $$$m$$$ edges, consider it to be the edge we make zero weight, and calculate the answer for all m edges using these distances in a total time of $$$O(m * m * log(n))$$$.

    Submission — 96142460

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

      Using Dijkstra only wouldn't this method also correct? (haven't implemented yet)
      For every $$$(a_i,b_i)$$$ Let $$$e_1,e_2...e_k$$$ will be the edge in the shortest path. $$$C[i]$$$ contains the contribution of every possible edge i.e. $$$C[i]=w_i*f$$$ where $$$0<=f<=K$$$ is the frequency of the edge $$$e_i$$$ in all $$$K$$$ delivery. Now final answer will be $$$\sum C[i] -max(C[i])$$$.
      I think it's right, right? However can you tell any easiest implementation idea of how I can get these edges in shortest path while using Dijkstra?

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

        No, this is not correct. The given 2nd example in the problem statement is a counter example. It is possible that an edge is not picked with the initial edge weights, thus not even included in your shortest path.

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

      Awesome Explanation. Thanks a lot.

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

can i get some help on finding the hack-testcase or why my code might fail on some cases ? it seems like a lot of people are getting hacked on F XD

my submission : my code

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

This solution looks copy pasted from somewhere here

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

Can anyone tell why my Submission for Problem D gave this weird Memory Exceeded Error.

My approach was to connect all possible edges(belonging to different gangs), then if it is possible selecting any connected graph print accordingly.

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

How to approach problem F ?

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

Today I gave my first contest but I did only A B C D in 2 hours. But I did not even get time to read F, G, H . How do I improve ? and what mistake is very common among ultra beginners ?

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

E was such an easy ques that it can be solved in 5 min but due to bad statement it took me 1hr to solve...really disappointed

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

I solved problem E afterwards with help of OEIS. During the contest, I was pretty messed up with that. Anyone would like to care what I am thinking wrong for Problem E. If I am not wrong there was two announcements. There was that thing, [1, 3, 4, 2] and [4, 2, 1, 3] are equal (in first announcement), [1, 2, 3] and [1, 3, 2] are distinguishable (in second announcement). My question is, I can make [1, 3, 2] from the [1, 2, 3] by choosing 1 (index 1) then going backwards index 3 with value 3 and index 2 with value 2, thus it makes [1, 3, 2]. So [1, 2, 3] and [1, 3, 2] circle should be equal like [1, 3, 4, 2] and [4, 2, 1, 3]. What is wrong with my thinking?

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

Weak pretests for F. Hacked a few solutions using this test case. 3 2 13 1 1 13 1 1 1

  • Few people didn't consider that minimum answer will be 0.
  • I misread the q. Instead of no more than m/2, I applied DP considering exactly m/2 in each row and it passed all pretests.[My fault]

BTW F was a really nice DP problem.

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

    You don't know what I did! I just took the max m/2 elements in every row summed them up and took the max number less than or equal to sum divisible by k and it passed pretests and later it got hacked. I already knew it would get hacked but this type of solutions passing makes me sad. The tests were quite weak. My solution would even fail for this-

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

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

E was 2*f(n-1)/n why did they ask for so small n? for f being factorial

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

Is the contest very easy or all the participants were much more intelligent then me?

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

Problem F:

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

I think we need to rename Div3 rounds to vovuh rounds. Sounds kinda cool :)

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

As an extra, try to solve C for all fish, i.e. check for each fish if it can eat everyone else. It’s a surprisingly beautiful problem (probably div2E/div1C level).

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

    We can use Segment tree. For every current fish $$$f_i$$$ we will do range update(left side and in right side). for $$$i<j<n$$$ we update as $$$a[j]=a[i]+j-i-1-a[j]$$$ in right side and $$$a[j]=a[i]+i-j-1-a[j]$$$ in left side. Now we will find min_range query in left side and right side If minimum value>=1 in both side then it's possible otherwise not. Overall complexity $$$O(NlogN)$$$
    Please verify whether it's correct or not. I think it is.

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

      What does your solution do in the case where $$$a = [4, 2, 1, 1, 1]$$$ at position $$$2$$$? Answer should be “YES”. More complicated cases exist, as well.

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

    This is how I initially read the problem. Then I thought "this seems hard" and read it again. But now that I think about it again it is indeed a nice too-hard-for-Div3C problem.

    Here's a quick outline of a solution idea:

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

      The solution looks good to me (at least the code seems OK)! I'm not exactly sure what you mean with properties (4) and (5) (for my example, $$$L = 2$$$ and $$$R = n$$$ satisfies your constraints, but does not block fish at position $$$2$$$).

      I've posted my take on the solution to my original comment.

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

        Constraints (4) and (5) do apply to the $$$L=2, R=n$$$ interval on $$$a = [4, 2, 1, 1, 1]$$$, but it does not block the fish at position 2 because $$$L \neq 1$$$ and $$$a_2 = 2 > a_{L-1} - R + L = 4 - 5 + 2 = 1$$$.

        Regarding the question posed at the end of your solution: I expect $$$O(n)$$$ time is possible. My idea is to generate the constraining intervals in increasing order of $$$R$$$ with one pass, and to generate the constraining intervals in decreasing order of $$$L$$$ with another pass. Then, the constraints can be applied in $$$O(n)$$$ with one more pass using two pointers and a stack, since any two constraining intervals are either disjoint or nested. (EDIT: See 96263307.)

        Incidentally, the hack test that I added to kill my incorrect version of that submission with slow asserts left on caused around 150 people with naïve $$$O(n^2)$$$ submissions to the original problem C to fail system tests.

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

          ‘Any two constraining intervals are either disjoint or nested’ -> nice one.

          Also, it’s pretty funny that you managed to hack 150 people by hacking your bad solution.

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

    Some progress.
    1. The set of fish $$$i$$$ can eat forms an interval $$$[L, R]$$$ where $$$L <= i <= R$$$. If we can't extend it any further, than
    2. $$$a_{L - 1} >= a_i + R - L$$$ and $$$a_{R + 1} >= a_i + R - L$$$
    3. $$$mx(L, R) < a_i + R - L$$$
    if we combine, we have
    4. $$$a_{L - 1} > mx(L, R)$$$ and $$$a_{R + 1} > mx(L, R)$$$
    Now, how to check that thing? I am struck here.

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

For problem D, why does 96184774 AC and 96185095 doesn't? All I did was change arrays to ArrayLists. I am unable to see the testcase which it fails on.

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

    Integers are object so you can't compare them with == because most of the time the references won't be the same.

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

Anyone, please help me here! I coded F and got a TLE on case 144. I was practicing out of the contest, so I hardcoded that case to see if there are more cases like it. But after hardcoding, my solution passed. On scrolling through cases, Case 144 and Case 227 are similar while 227 being more in size constraints. But my solution passes 227 while fails on 144 if not hard coded. I used DP. Can anyone please help why is this happening and how do I optimize to pass case 144?

Submission: 96189336

Update: Hacked my own solution so as to someone don't see it as an AC solution. But someone help me out here so as to why is this happening on case 144 and not on 227. And how to optimize?

Update 2: Figured it out! Thanks

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

deleted

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

The comment is hidden because of too negative feedback, click here to view it

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

It is so annoying to see that someone needs only 2 minutes to solve the problem G while I have to spend 2 hours :/

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

When will the ratings come?

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

This was my first contest. I submitted a couple of questions which got accepted. why am I still unrated?

any help regarding this ? X(

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

    The ratings have not been updated yet. There was a 12 hour hacking phase after which system testing begins and after that ratings are updated.

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

@vovuh my rank on common standing list and friend standing list are showing different please tell me which one would be considered, it is a difference of 300 rank which would be quiet high for Div3 for me , please reply

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

    Yes. I have also observed the same.

    In common rankings, only trusted participants are considered for the ranking. Just below the title "Common Standings". It is mentioned "[Trusted participants only]". So, I guess the rank shown in your friend's standing list will be considered for the rating.

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

//it's of piranha question.. I did the same as editorial now...will u please help where is my logic wrong???

          ll n;
	  cin>>n;
	  ll a[n];
	  ll max=0;
	  ll r=0;
	  ll loc;
	  for(int i=0;i<n;i++)
	  {
	  	cin>>a[i];
	  	if(a[i]>max)
	  	{
	  		max=a[i];
	  		r=0;
		  }
		  if(max==a[i])
		  {
		  	if((i!=0 && a[i]!=a[i-1]) || (i!=n-1 && a[i]!=a[i+1]))
			  {
		  	loc=i+1;}
		  	++r;
		  }
	  }
	  if(r==n)
	  {
	  	cout<<-1<<"\n";
	  }
	  else
	  {
	  	cout<<loc<<"\n";
	  }
  • »
    »
    4 года назад, # ^ |
    Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

    Your are accessing a[i+1] without even assign any value to it. I guess that is the reason behind it.

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

Can someone tell me whether Hacking changes your ranking in this contest, because I hacked 3 solution but my rankings didn't got changed

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

Don't dzgod1905's submission times look suspicious?

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

Can anyone help me figuring out the solution for the 3rd Question ( Dominant Piranha ) if the question asked how many piranha's instead of any one dominant piranha.

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

    The first comes to my mind is very naive, piranha is dominant if it can eat all piranhas around. So you can store piranhas in linkedlist. For example you are checking i-th piranha, on each step you remove either right or left node and increase value in current until there are no steps or neighbors. Repeat this for each piranha. O(n^2). Key is to store piranhas in linkedlist.

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

    You will have to find the maximum element in the array , if the no. on its left or right is less than that no. , the index of this value is your answer, whereas if both of its right and left are equal to it make I+=1; and check again . The answer would be No only if all the elements are equal

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

When will the ratings are going to update of this contest?

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

Is this rated?

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

Why hasnt the rating been updated yet? Its almost 20 hours.

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

When will ratings update?

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

Is this round rated?

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

vovuh Why do you never announce round winners?

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

    I did it some time ago, but the script awoo wrote for winners table worked incorrectly for Div3 iirc (there was a problem with trusted participants) and I stopped posting them. I wanted to fix the script for Div3 but I'm too lazy didn't have time to do that. Maybe I will do that in a few weeks or ask awoo for the help.

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

Hi vovuh,

Is the way ratings for problems are calculated standard across all different types of contests? Looking at the ratings now, they seem incredibly mismatched, seeing as both F and G are rated 2100. G is somewhat understandable, but how in the world did F become the same? Although fitting for a Div. 3, you probably cannot ask for a much more straightforward DP problem! Perhaps it is because of the fact that Div. 3s are regarded as 'easy' contests, so CMs and above don't take the contest seriously and go straight for the final problem, and upon solving it, leave? In any case, maybe problem ratings for Div. 3 rounds should be calculated manually instead?

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

    Hey. I'm sorry, but I would say the thing I said so many times already: I'm not tied with the technical side of Codeforces (and calculating problems rating is exactly its technical side). I'm just an author and a coordinator (in some way), so you could ask Mike about that feature and its correctness.

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

Regarding F. Zero Remainder Sum: Can someone PLEASE tell me how can I make this code faster 96316767. I've been trying to figure it out all day. It is exceeding the Time limit test 6.

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

    Use a 4D array instead of a dictionary.

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

      Thank you for your suggestion. Unfortunately, I did try this alternative already 96316025 and it failed on the same test

      Do you think it’s imposible to solve it using recursion in python ?

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

        There are 0 accepted solutions in Python xD. There are a few using PyPy3. But ig all of them are iterative.

        In C++ even my N^5 solution passed xD.

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

What's up with the rating of the problems ?

A-E are under 1300, F is 2100 which is a pretty standard dp.