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

Автор AmShZ, история, 4 года назад, По-английски

Hi Codeforces!

Dio, Keshi, Tet, alireza_kaviani, Davoth, AliShahali1382 and I are delighted to invite you to participate in Codeforces Round 722 (Div. 1) and Codeforces Round 722 (Div. 2), which will be held at May/24/2021 17:35 (Moscow time). Each division will have 6 problems and 2 hours and 15 minutes to solve them.

The curse has finally been lifted! We are proud to announce that antontrygubO_o didn't reject even a single task from the Div. 1 part!

Huge thanks to the following people:

For the sake of having short statements, this round does not have a theme. The characters featured in the statements are: Soroush (Tet), Sifid (Davoth), Parsa (Dio), Nima (N.N_2004), AaParsa (AaParsa), Haj Davood (davooddkareshki), Kavi (alireza_kaviani), Keshi (Keshi), Mashtali (AliShahali1382) and AmShZ (AmShZ).

Please read all of the problems and their notes, enjoy your time and solve as many as you can! Good luck have fun to everyone!

The scoring distributions will be announced later.

UPD: Here are the scoring distributions:

  • Div. 1: 750 1000 1750 2000 2750 3000

  • Div. 2: 500 1250 1750 2000 2750 3000

UPD: Editorial is out!

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

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

Being a setter, I fully understand the pain of other setters while writing statements.

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

omg saarang tester orz

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

as a teacher and as a friend, I am sure we will see a great contest :)

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

Finally wait for Anton round is over, would be a great round for sure!!!

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

As a tester, the problems are very nice and interesting! I recommend everybody to participate!

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

Woow !! Finally again an iranian round :))

I'm so interested to participate in my compatriots' round !

Hope to reach pupil in this round, Thanks AmShZ and other dear authors.

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

    Many times I see people commenting it's an Indian round, it's a Chinese round.. etc and now you are saying it's an Iranian round. What difference does it make? I don't think there is some pattern in the problem set associated with the region or something like that.

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

      We respect to our compatriots ! :)

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

      It's just that participants get excited because they have the same nationality as the authors.

      Not sure if it's true for Iran, but I guess that some countries have a few problem-setting-eligible users and those users are well-known among the people of that country. Wouldn't it excite you to see an acquaintance of yours set a round?

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

        Agree with you

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

        I definitely would, but expressing it in that way looks inappropriate. Mentioning country looks like drawing borders to me.

        Maybe I'm over reacting. Btw thanks for the contest.

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

          Nah I feel the exact same way as you. But then again, different people have different opinions and beliefs, so I dont mind it.

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

          Chinese round: Maths, implementaion,data structure

          Russian round: constructive, observational

          Iranian rounds: balanced perfectly

          Indeed it was balanced perfectly.

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

      i will add something about your comment after the contest

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

      ok as i said there are some few things you can find out when the contest is made by irainian:

      1) there are always some graph problem and most of the graph problems are either shortest path or tree problmes

      2) there are lots of dp problems

      3) there is no complicated greedy problems because most of irainians hates greedy

      4) they also hate geometry so you 99% can be sure there is no geometry

      5) there are usually hard combinatorics & DS problems

      these are the things that ive learned because im either student / classmate / friend with them : )

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

as an author, give me contribution!

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

orz

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

Its a really nice round with great and beautiful problems. I hope everybody can enjoy this round.great effort from all of the setters to finaly make this round.good luck everybody and have fun. (Dont read kostia's comments :))

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

As a tester, the problems are interesting and the statements are short. Hope you enjoy the round :)

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

Such boys !

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

round after another 2 days:( can't wait

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


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

    Frankly, you shouldn't count it as a ghaazzz round. And this way we can still expect a real ghaazzz round.

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

      agree.we can't count it as a ghaaazzz round,but as a ghaazzz round.

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

As a tester, I am way too late to post an as a tester comment.

(insert all the normal tester comments about how good the round was here)

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

as a tester, orz

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

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

The best adhoc cooontest")

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

Whenever We open Codeforces and see a contest announcement on home page, Inside us

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

I hope Question C has no nonsense

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

Good Luck Everyone !!

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

Length of the round is set to be 2 hours on the contests page, please fix it. AmShZ

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

May I ask what was the reasoning of having exactly 2 hours 15 minutes, and not 2 hours, and not even 2.5 hours?

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

    Whenever you give a 2hr contest and submit one of those messy problems in the last minute and get WA on pretest 2 and then wish you had only 10-15 minutes more. These are those 15 minutes.

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

Benq is going to participate in this game, I think he will play a very good result in this game.

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

Finally another Div.1!!!

But what a pity that the contest is held on Monday! I think many people like me can't participate in. sad to see that

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

Auto comment: topic has been updated by Tet (previous revision, new revision, compare).

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

The blog mentions the length of the contest as 2 hours and 15 minutes, while the contest page is showing 2:00.

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

Ever since I became candidate master(more than one month ago). It's first Div. 1 contest Hope to have good contest Thank you very much Haj Davood :)

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

Excited for the Contest hope that I will be able to solve at least B in this contest

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

Which one won the game Div 1? 1) Benq 2) Tourist 3) Radewoosh

Guess?

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

Why codeforces is not taking contest frequently ? The wait after every contest is lasting soooo long :(

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

    Though codeforces is kinda better, but you can also participate in other online contests. Such as atcoder, codechef and even yukicoder. These websites combined you'll have at least one contest every other day(maybe everyday).

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

      Ya , but the happiness of increase in rating on codeforces is of different level. :)

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

        I agree. The same is true for atcoder, but still not as much as codeforces. Besides, competing is great itself.

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

Don't know why, but I feel good about this contest. Feel like I'm going to get to almost reach pupil.

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

good luck, have fun :)

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

Dio If I surpass you, will you give that username?

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

The problems are always interesting <3

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

Iran is an actually a good country :D

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

and if i say orz i get negative contribution "(

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

Hi !

When will the scoring distributions be announced ?

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

    We are still discussing it :(

    I'll post them the instant we agree on something ...

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

B part has a score of 1250 instead of 1000 or 750, I hope I become a specialist.

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

how does the scoring distribution of the problem matter? What does it actually mean?

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

    It gives you an idea about the level of the problem. Though it is not always accurate but most of the times it is. For example B problem might be a bit hard today as compared to other div-2's B problem but again it might be easy too. You can never tell you can only guess.

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

Div 2 3rd problem is of same difficulty of Div1 3rd problem wow :(

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

Seeing the score distribution, contest will be hard

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

time to skip after seeing the score distribution.

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

good luck to all!

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

Ghaaz = Goose(in Persian)

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

Only way i can solve Div 2 C is, if it is given as captcha to view anime online.

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

how to solve C?:)

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

    dp on trees, and only $$$l_{i}$$$ and $$$r_{i}$$$ are important in the range.

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

    can solve by dfs. just handle parent and child relation and add every child value with parent then answer is root value.

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

    For those who solved Div2C / Div1A, could you guide why DFS is needed (as opposed to BFS)?

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

      Any traversal technique works ig. I solved using dfs though xD

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

        Actually I had used BFS, which was incorrect. I think I now understand why. DFS is a must here since the max value of the root node (you can pick any node as root) depends on the max values of its children, which in turn depend on their children, etc.

        So once it's clear that you have to pick either L or R for each vertex (and no value in between), then it's a matter of solving subproblems first — recursion with DP does that effectively.

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

          Yeah, it doesn't I overlooked it. Basically it's like we should find the answer for all nodes in the last level and then the previous level and so on. So we can somehow store answers for higher levels first and then for lower levels using BFS. But we have to store the nodes which are at a particular level and it is implementation heavy.

          So I think BFS is something like top-down traversal so it's better to use DFS as it's a bottom-up traversal in such cases.

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

Is O(N^3) meant to pass div1D?

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

Why is a simple DFS getting TLE on Div2 C??

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

What happens if you AC a problem twice in pretests? I resubmitted one of the problems due to runtime and got -50 penalty but if the first solution passes systests, will I still get penalty?

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

Is D on OEIS? And how to D it?

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

    You need this one https://oeis.org/A051950

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

    I used dp. categorized the length of pair (L) into two parts:

    for each n, define f(L) as:

    if L <= n, only those n % (L-1) == 0 will contribute. I count the frequency of each prime factor of n (p_i) and do a product of (p_i + 1).

    if L > n, it will be a fully covering case, and the inner part will be dp[L-n-1]. Those can be calculated use prefix sum.

    so each dp[n] = sum_{L=2}^{2n} f(L).

    I'm not sure if this is good for system test, and sorry for the brevity of the description

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

    Very hard to demonstrate without paper.

    [...] [...]

    Suppose those two arches have the same length. Then we know nothing can belong inside of both of them, as each subarch isn't inside of the other (place inside of the left, not inside of the right), etc. And because the subarch must be smaller, then neither condition can be satisfied.

    Now, we know that must be a be a thick arch. Like for example, an arch of "thickness" 2 cross weaves 2 archs, if you know what I mean. And now you can place subarchs inside, this gives a relation dp[i] = sum of all j <i dp[j]. Since there is only one unique way to place this thick arch (otherwise it because multiple archs of varying sizes, but you just want that 1 thick arch). This thick arch can be anywhere from 1 thickness to the entire rest of the length so that's why we go for all j<i.

    The tricky thing is to handle the no-archs case, where all lengths are equal and you can place them wherever. The answer turns out to be the number of divisors of the number, though I have no idea why (I saw the potential pattern but no proof as to why it works), but proof by AC I guess. So add on the number of divisors at the end of every precalculation DP. And because it's prefix sums just keep a running prefix to add on every time.

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

Holy fk I passed D pretests in the last seconds! Shoot ...

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

    Hints on problem C, please.

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

      I used DP actually. Try to solve the problem (maximum sum) for each subtree. And for each node u, you can calculate what the result will be if you use the left or the right.

      The transition for one node using its left value will be

      dp[u][L] = max(|l[u] — l[v]| + dp[v][L], |l[u] — r[v]| + dp[v][R])

      Let me know if you need more spoilers

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

I am not familiar with the rules. I have submitted a correct solution at 0:05. But at around 0:35, I submitted another correct solution. I wonder why my score for that question is based on the finishing time of the latter one? (0:35 instead if 0:05)

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

    The second one is scored.

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

      I understand the rule right now but I wanna know the rationale behind this rule. Why don't it count the first correct submission that able to pass the system testing.

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

        If you want the first to count, then there is no need to submit the second. So, you decide.

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

          It's just because I didn't know this rule before this contest. I would definitely not do it again in the future contest. Btw I resubmitted it just because the second one has a higher chance to pass the system testing.

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

            Then isn't that a valid a reason to not consider your first submission ? As you were not confident that the first one would pass the final test cases and modified it to pass the system cases.

            I think its kinda synonymous to getting a WA and then debugging and resubmitting the correct solution .

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

    In case of multiple correct submissions (for same question), only latest one is considered. All previous submissions get skipped and don't appear in system testing.

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

Does D need some special DS or math technique?

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

My approach on C Code

Can anyone tell me what is wrong with it.

I have taken 4 critical numbers for each vertex

1) li

2) ri

3) (li+ri)/2

4) (li+ri+1)/2

The best result for each of them in dfs is returned in a array in the same order .

In the end when recursive calls finish we output max of all 4

**** EDIT NOW WORKING

WE need only left mini and Right maxi

Dfs Based Solution of C Parsa's Humongous Tree without DP based on the fact that during path traversal on a tree from root , A particular node is reached only once.

We return a pair {a,b} from every node.

A has the best solution from that node to all nodes below it when left_mini is assigned to that node.

B has the best solution from that node to all nodes below it when right_maxi is assigned to that node.

We store best possible values of the current node from all children node i.e. one with maxi on all possible calls and other with mini and then return it.

In the end when recursive calls end print the maximum of the pair of values returned from the root.

Solution

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

D < C :((

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

B is not nice problem, also misplaced.

B>D>C

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

    I guess you also thought that subsequence must be continuous.

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

      No, I think I understood the promblem correctly. But there seems to be some more or less obvious observation needed that is invisible to me.

      From other submission it seems that we can use all negative numbers (ok, understood), and then all positives up to the first bigger than the smallest diff so far.

      But why, why cannot be there ohter solution? Or did I get it wrong?

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

        Have you considered the case when any element <=0 is repeating twice?

        This has caused me 5 wa and 40 minutes.

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

        Note that the difference between two positive numbers is strictly smaller than the larger of the two numbers, so any solution can have at most one positive number. On the other hand, we can take as many non-positive numbers as we like. So the question really only is about whether we can take a positive number in addition to the non-positive ones, which is possible iff a positive number at most as large as any difference between the non-positive numbers exists.

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

          "...so any solution can have at most one positive number."

          Ok, thanks, that is the missing observation. What a stupid problem :/

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

            Indeed, it was stupid.

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

            I found B to be hard to understand, not from the language, but from the definition of the promblem itself.

            I had to read the definition of a strange seq at least a dozen times, and actually now I am hardly able to tell from head (just did read it again some seconds ago).

            So, basically that problem is "somehow get that wiered definition into your head, then you will quickly see the solution." I am ok with a complecated, or strange definition if it is a complecated problem.

            But a very simple problem with a complecated definition is a bad problem.

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

        You can see that there can be at most one positive integer and all others are 0/negative and their minimum abs difference must be greater than the positive number so we choose least positive number. If that number is still greater than minimum abs difference we remove that number. Since we are taking all nonpositive integers there can't be another solution. If we remove some negative integer to increase difference, ans will be less than number of nonpositive integers.

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

        Problem Div2B was constructive at best, it felt like you cater to the observation required and it should work.

        I am also curious about other approaches as well :)

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

How did you solve B? Tried for two hours to Frankenstein it with all of the possible cases I could think of, using different sizes of negative, zero and one positive number.

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

    You can prove that there can be at most 1 positive number. Then it's easy.
    Take all negative + zero numbers or take the smallest positive number also. For the second choice check whether it is possible.

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

    i tried with 5 case and take the maximum.
    1. all zero and all negative.
    2. only one zero and only one positive
    3. only one positive
    4. all negative and one positive (for taking positive and negative at a time check minimum of positive >= max difference of any 2 negative numbers)
    5. all negative and one zero and one positive (And taking all pos, neg and zero checked minimum of abs(negative value) >= min positive value and must checked 4 condition also)

    And taking all pos, neg and zero checked minimum of highest negative value >= min pos value and

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

    Very easy solution:

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

Used deque for interval minimum with correct complexity in div1D but TLE, unfortunate.

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

such nice problems! good job :)

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

I found that my $$$D$$$ is on the edge of the TL much latter in the contest but decided against improving it(I hope it passes), how to calculate number of divisors for each [1,2n] fast, I did $$$O(sieve*logn)$$$?

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

    You can do it by iterating for each number from 1...n by its multiples.

    1,2,3,4,....
    
    2,4,6,8.....
    
    3,6,9,12...
    .
    .
    k, 2k, 3k...
    .
    .
    n
    

    it's very similar to sieve. This has complexity NlogN

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

      Yeah, very stupid of me being unable to find such simple algorithm given that I had used this before more than once

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

    Can you explain the basic idea of how to solve D.

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

      @dhruv7888 It can be solve by DP. Ex, N = 3: dp[3] = dp[2] + dp[1] + dp[0] + number of diviors of 3

      Because when you know all the good pairs of N = 2, to form good pair with N = 3, you can add a pair bound all pairs with N = 2, similarly add 2 outside pair to N = 1 ...

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

Does anyone solve problem D with DP formula, dp[i] = prefix[i] + number of Divisors of i? I got TLE, could you share the way to count the number of divisors?

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

    If you have factorisation in form $$$n = \prod p_i^{a_i}$$$ then number of divisors is equal to $$$\prod (a_i + 1)$$$.

    Factorisation can be done pretty quickly by precomputing all primes, or just using linear sieve.

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

      Thank you, the factorisation is really good idea, I have leant new thing. What the time complexity of the factorisation? Does Linear sieve mean that iterating for each number from 1...n by its multiples? And it will take O(NlogN)?

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится +16 Проголосовать: не нравится
    for (int i=1; i<=n; i++) {
        for (int j=i; j<=n; j+=i) {
            factor[j]+=1;
        }
    }
    
  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Yes. I used dp[i] = pref[i — 1] + number of Divisors of i.

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

I never thought 6 months ago that I'll be able to even maintain a lower specialist. But alas my dream come true and If all my 4 solution passes, I'll be an expert.

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

Solve C 10minutes, B 2hours and failed :(

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

How to solve C?

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

    Observe that foreach vertex it is allways optimal to use either l[i] or r[i], never some value in between.

    Root the tree somewhere, do a dfs. Result of the dfs is foreach vertex the max value we can get if we used l[i] or r[i] for that vertex.

    To find the two values for the current vertex, find the values for all adj vertex, then try both values and record the max value possible.

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

Very nice problems! Thank you for the contest!

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

At first, I tried some greedy solution of C, and it looks scary...Then I glanced at D, it looks scary too...So I waste about 1.5 hours trying to solve E...

This story tells us that don't solve problems out of order if you're not sure you can solve all of them :(

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

I decided to abandon python after this contest. Using python in codeforces is totally a disaster and will ruin your rating. Many problems, especially graph problems, like problem C in this contest, using python will cause you TLE, TLE, TLE...... while others languages can pass easily with same algorithm. It takes me 5 minutes to think of problem C, 15 minutes writing and compile, and an hour to submit, TLE, optimize my code, submit, TLE, optimize my code .....It's very very very frustrating to make tens of attempts but didn't pass, and see my current ranking drop from 300 to over 2000. Goodbye my rating, and goodbye python.

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

I am getting TLE in C. Time complexity of my code is O(2*(v+e)) but I facing TLE, please help me. 117248045

Edited- This issued was solved, instead of cin, I used scanf. It's working properly now.

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

:( Can anyone show me some tips for solving A and B super fast?

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

I'm such an idiot. I solved div#2 C but was using int instead of long long. Thankfully it struck me just 10 minutes before the contest ended.

And it wasn't the first time this happened to me. :(

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

    define int long long gang

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

    Lol man, exactly what happened to me. First time I solved DP problem in a contest, first time I solved C in division 2. Lesson learned man, I changed my template to replace ints with long longs by default now. I do not want this to happen again, feels really bad

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

Solved div 2 B with ternary search .Can anyone explain a simpler solution for it..

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

    the simplest solution I found is take all -ve and all 0, then try to take as many +ve as possible

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

    Simple solution is to take all the non-negative numbers. After that, it is pretty easy to observe that we can take almost one positive number. So start by finding the minimum difference in the non-negative elements already selected and try to pick a positive number greater than or equal to the minimum difference. I observed this after solving a few cases on paper.

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

How did people solve C div1? The solution boils down to running a DFS on the first graph, adding/removing vertices from the second graph and counting number of nodes from the second graph which currently have no descendants. What is the good data structure for this? I used some preorder segment tree with rollbacks, but there might be an easier solution...

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

    I used a binary indexed tree to check if a given vertex has any marked descendants, and a link cut tree to find the deepest marked ancestor of a given vertex. 117214561

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

    I used just a set. If you run a euler tour on the second tree and map each vertex to a segment, it's equivalent to finding the longest subsequence of vertices on the first tree such that none of their segments intersect, and the subsequence is part of a path from the root to some vertex in the first tree.

    Basically you store a set of all the segments that you take from the root to a parent of a vertex; when scanning the vertex in, check if a segment intersects it in the set. If it does, remove that (because it's never optimal to take a larger over smaller segment if both intersect, and if two segments intersect, one must completely overlap the other since it's from a euler tree). Then, add the segment belonging to the current vertex in the set. The answer is the maximum size of the set at any time.

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

    The only data structure I used was a set. If you record the in and out times using DFS in the second tree, we have each node in the first tree is labeled with an interval $$$[in, out]$$$. We want to consider all intervals on a path from the root to a leaf, and try to find the largest set of nonintersecting intervals. But since the $$$[in, out]$$$ intervals either don't intersect or contain each other, we can simply use a set to do this.

    Submission

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

When is rating normally distributed?

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

Is there a proof of correctness for Div2 problem C ?

Considering the right or left value on each node will yield the maximum value.

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

    Say you choose some value a such that l < a < r, and you've already chosen some value b for another node. If a ≥ b, then adding 1 to a will increase |a - b|. Otherwise, subtracting 1 will increase it. You can keep adding/subtracting until you get to l or r, and get a max value.

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

    Consider $$$v[i]=l[i]+1$$$ to be a better solution than $$$v[i]=l[i]$$$ Then this is because there are more adj vertex with $$$v[adj]<v[i]$$$ than there are with $$$v[adj]>v[i]$$$

    If this is so, then $$$v[i]=max(l[i],r[i])=r[i]$$$ is true, by induction.

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

I did not pass problem C because I used int instead of long long. Lesson learned. That would be the first time I solved problem C :(

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

In problem D, when I used vectors for adj lists it TLEd and when I used 2D array for weights, it ACed. This was not fair T-T T-T. It costed me "Grandmaster" today.

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

[Deleted]

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

A non recommended approach for Div 2 problem $$$D$$$
Write bruteforce solution and generate first few terms of the sequence, here they are $$$1, 3, 6, 13, 25, 52, 102, 206, 411, 823,...$$$
As this can't be found on OEIS, make an observation that $$$dp(i) = 2 \times dp(i - 1) + c_i$$$
Search for sequence $$$c$$$ : $$$1, 0, 1, -1, 2, -2, 2, -1, 1,...$$$
which is A051950, so $$$c_i = \tau(i) - \tau(i - 1)$$$, where $$$\tau(i)$$$ is the number of divisors of $$$i$$$.

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

AAAAaAAaaaAAaaaaa I didn't submit D1D because I fucked up one line of my dijkstra and an "i" was supposed to be a "j", and last round I FST'd because a "<=" was supposed to be a "<"

why am I so cursed

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

Feedback on the contest:

A: Clean nice easy (and a bit standard) problem.

B: I am not a fan of counting problems where there is fundamentally zero computer science involved.

C: Cool problem. The two crucial observations (finding a polynomial solution, and then finding a pseudo-linear solution) where equally hard for me. The difficulty of the problem was really on the spot.

D: Cool problem. The fact that, in the end, this is just Dijkstra is very nice.

E: Once again, I am not a fan of counting problems where there is fundamentally zero computer science involved (I could not get AC during the contest, so maybe my solution is flawed and thus my comment does not make sense).

Overall I really enjoyed taking part in the contest since the two problems C, D were cool! Thanks to the authors, nice contest!

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

To not keep you waiting, the ratings updated preliminarily. In a few hours/days, I will remove cheaters and update the ratings again!

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

Can anyone please explain how the Problem D(DIV-2) boils down to just finding prefix sum of number of divisors?

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

    Foreach group of i pairs we can build "packs" of size k if k divides i. So, that number contributes to the solution. Also, we can pair the 2,4,6,... outermost points in combination with the previously calculated result for the i-2, i-4, i-6,... inner points (see third picture of examples). So we need to add up these prefix sums.

    117249412

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

Is there a way to solve Div2C using BFS instead of DFS? I could find the relation to find the maximum sum to reach any node from some initial node say 1, but got stuck after this since I was using BFS and could not think of a way to find the total maximum sum.

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

    the approach for this problem is bottom-up, which means that you need to solve DP for the leaf nodes, then accumulate to the root node

    I think it's more convenient and makes more sense, and DFS is often used for DP-on-tree problems

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

    You should do a bottom-up dp which can be done with either dfs or bfs, but dfs is easier to implement.

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

During the contest, I made this observation for D — the range of distances for each city is $$$[minC, minC + n - 1]$$$ where $$$minC$$$ is the minimum traveling time of a cannon in that city; to remove the $$$log_n$$$ from the Dijkstra complexity.

I thought that was pretty neat until I read other people's codes and realized that we could just run a simple $$$O(n^2)$$$ Dijkstra...

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

For the D problem, what should be the starting point to think in order to solve the problem?

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

Why is this (https://codeforces.net/contest/1528/submission/117194884) solution so much slower than this solution (https://codeforces.net/contest/1528/submission/117196442). The only difference is that in one case I used vector with assign() (it should have linear complexity I think) and in the other case I used a plain array.

EDIT: nvm it's o(n²), I'm blind

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

good contest !

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

To the setters, or to setters in general:

Just out of curiosity, do you test standard solutions on languages other than C++? I didn't compete today because I was busy, so there's no bitterness over rating here, but I'm curious as to why a 1 second time limit was necessary for Div 1A/2C (for example). A DFS solution should be perfectly adequate, but it will not pass in pypy without some trickery (e.g. coercing to floats, flattening arrays, etc). Clearly an N^2 solution would not pass in 2 seconds even in C++, so why the need to make it so difficult for a standard language like pypy? To my mind if you implement a clean DFS solution, it should have the chance to pass without all the extra little hacks. I know using C++ is quicker and always will be, it just seems like 1 second versus 2 is unnecessary here, and in many other cases.

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

Hi, Can someone explain me why we add the number of divisors of i to dp[i] in Problem C of Div 2 ? Thanks in advance .

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

One of the best contest I ever wrote, almost got D at the end. Thanks Iran. Thanks to the setters.I hope to see more rounds from you all!

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

In problem B what is the answer for this test case 3 1 0 1 I think the answer is 3

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

    You can have at most one positive element in a strange sequence.

    let a and b be positive integers, then max(a , b) > |a — b|, thus [a , b] is not strange.

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

      in this input |1-0| = 1, |0-1| = 1, |1-1| = 0 and the max element is 1..

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

        No, as you've mentioned |1-1| = 0 which is smaller than the maximum element which is equal to 1 so it's not strange ...

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

Can you download a whole test case on Codeforces? In div1 C the 18th result in the second test is wrong so I have no way to see the input for it.

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

    Found the mistake, I always make a stupid mistake when making larger programs ;((((((

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

Auto comment: topic has been updated by AliShahali1382 (previous revision, new revision, compare).

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

Which type of round is this? Is it global round or something else?

Capture

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

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

Please provide python code for problem div2C/div1A that passes in the editorial AmShZ if possible

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

As a participant who rated up ,Give me Contribution!

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

I guess my new colour is a message from god that I should stop participating in rounds and practice

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

Can someone help me why my dp usual solution for problem C is giving TLE? my solution

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

Really nice round! I didn't get a good ranking, but problem 1A 1C 1D are excellent!

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

and for your information in the first question his name should spell echag no eshag i mean sh shouldn't readen as normal form .

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

I hope Iranian contests are very very great and I enjoy it Please make more contest

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

MikeMirzayanov Please update problem ratings of this round!!!

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

antontrygubO_o , Dio this 722 Div.2 is not a rated contest?

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

    People usually ask "is it rated?" before the round not after it ...

    In any case, yes, it is rated.

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

.

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

"Attention!

Your solution 117199988 for the problem 1528C significantly coincides with solutions PrashantM/117199988, nishant02/117243984..."

There was no Plagiarism involved in these solutions.

While we have practised together causing some similarity in the code style (variable names "dp" and "Tree", function "solve") — the solution itself was not copied, and not online unintentionally either (I use sublime text, and have been for the past 6 years). And apart from the variable names / the core logic being small and similar (there are many similar submissions apart from ours) — there are visible differences in the code.

Please revert the flag on our submissions.

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

...

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

,,,,