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

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

Hi Codeforces!

Keshi, alireza_kaviani and I are delighted to invite you to participate in Codeforces Round 800 (Div. 1) and Codeforces Round 800 (Div. 2).

  • Start time: Jun/16/2022 17:35 (Moscow time)
  • Duration: $$$120$$$ minutes
  • Number of Tasks: $$$6$$$ for both divisions
  • Rated range: ($$$-\infty$$$,$$$1899$$$] for Div2, [$$$1900$$$, $$$\infty$$$) for Div1

We are honored to have set the 800th Codeforces round. We wish this wonderful platform all the best along with many other exciting rounds.

Huge thanks to the following people:

Thanks to NEAR for supporting this round, details can be found in this post.

We have worked hard to keep the statements clean and the pretests strong!

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 1500 2250 2500 3000

  • Div. 2: 500 1000 1500 1750 2250 3000

UPD: Editorial is out!

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

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

Great contest! you will enjoy it.

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

Orz

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

Yet another great Iranian round :) orz

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

Hope everyone can be red in this contest (of course include me).

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

btw congrats to alireza_kaviani for qualifying in Iran's IOI 2022 team

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

Codeforces orz
MikeMirzayanov orz
Polygon orz

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

Orz

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

Paranoid creepy tasks?

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

As a tester, problems are great and statements are short.

I encourage you to participate in this round!

You will definitely enjoy this round!

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

    Haha certainly....but sometimes short ones are the real fire ones...looking forward for this round....

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

Where is translation into russian?

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

Another div1 with trygub support? It will be fine.

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

Hope all the best for everyone

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

Finally, my first Div 1 contest. Yayyyy. Every time I used to fall back to expert just before Div 1 contests.

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

Good luck for everyone!!!

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

good luck for everyone

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

good luck man!

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

Good luck !?

Naah,it won't help :(

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

800th round! A great number

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

My first time participating in Div. 1, I am so nervous.

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

Wow, great!! 800 contests, its huge!! Thank you Codeforces❤️

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

I know I won't be able to solve any one of em, still gonna participate..

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

GAP

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

Hope I don't go back to being a pupil :/

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

When someone says orz as a comment
68e3682b065c5b4a66b64c2e78865293

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

tell newbie what is orz

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

is it contest?

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

I guarantee you will enjoy the contest.

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

I hope I don't lose points in this game.

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

No offence but why does authors tend to hide the score distribution and reveal it just before the contest starts?

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

Lmao, what does +inf & -inf rating mean !!

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

    infinity, quite literally. If you did not know, negative ratings exist and they are not rated in most rounds (most rounds' rated range begin from 0)

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

[1900, tourist] for Div1* :v

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

Good luck for everyone!!!

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

Why only two div2 testers?

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

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

Why so many orz comments? Could someone explain, please?

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

RIP Score distributions.

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

When will be the score distribution update? It's just 1 hour 12 minute remaining.

»
21 месяц назад, # |
  Проголосовать: нравится +15 Проголосовать: не нравится
waiting for score distribution be like
»
21 месяц назад, # |
  Проголосовать: нравится +4 Проголосовать: не нравится

My first contest!!

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

Not a Doctor Still doing a lot of operations.

Won't say bad round. I liked the Problems though.

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

I think that this contest isn't good. I can't understand the problems well.

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

    Why so many downvotes !? It's my personal opinion !

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

      Because people didn't like your opinion. I mean that is how this system works. If people don't like your opinion they downvote you. if they like it then they upvote you.

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

If this was a Div2 I am a refrigerator. tf.

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

I don't mind difficult problems but a,b,c are very observation based and took me a lot of time, hence we don't get enough time for interesting problems like D

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

I dont like this round (my opinion)

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

    I respect the work of autors. Its very cool to do problems for codeforces round. I dont like this types problem. Thats what I meant.

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

I guess I am just dumb.

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

Round #800 CLASSIC GREEDY ONE !!!!!!

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

I didn't expect adhoc tasks :(

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

I liked problem C. Sample cases were very useful for solving.

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

    I hated it for that reason, but problem was very good . They should'n have provided the 5th sample it was easy to guess then.

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

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

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

How to solve Div 1C?

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

    Reverse the graph and then do something very similar to dijstrak starting from n-1. Notice that at some node, you have a bunch of nodes you can go to and if you know their distances, you can kill some in descending order(so like their effective distance is +0 +1, +2 +3....) and find the optimum of that. Thus, what you can do is to store the current estimates incoming (after reversing) for each node and pick the best (similar to dijstrak) after adding some weights. Then, we process the nodes by current estimate similar to dijstrak. But this may potentially force you to reupdate the whole set everytime you process a node. But, you realise that you only add numbers greater than numbers you add before (since you process nodes in ascending estimates). So, you can just store the best estimate.

    Essentially its just do dijstrak with the following modification: dist[v] = min(dist[v], dist[u] + indeg[v]) indeg[v]--

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

For problem D: if the sequence is decinc, there are only at most $$$3$$$ representations of it, that are of interest. For maximum increasing subsequence, you must use all elements except maybe one and if you don't use an element in the increasing sequence, it's always either first or last element.

Note that if the sequence is decinc, then so is all of its subsequences, hence you could kind of make a binary search for each $$$L$$$ on the largest $$$R$$$ such that $$$[L; R)$$$ is decinc.

But my solution failed pretests because it uses binary lifting and needs $$$O(n \log n)$$$ memory. I'm pissed off it doesn't pass.

Now that I think of it, you can probably also do it in $$$O(n)$$$ with two pointers?

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

I've seen a version of Div1D with answering for whole sequence in a few Polish competitions, so the key observation (that we can build the answer greedily) was known to me (I'm not saying that the rest is correct, last rounds weren't generous for me).

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

    I can write a bit more: assume that we've split the prefix into two sequences (decreasing and increasing) and the next two elements are $$$x$$$ and $$$y$$$, where $$$x$$$ can be appended both to increasing and to decreasing sequence. It turns out, that if $$$x<y$$$, it's optimal to append $$$x$$$ to increasing one. If $$$x>y$$$, it's optimal to append $$$x$$$ to decreasing one.

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

Approach for Div2C??

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

    Beginning from last non-zero element, iterating backwards, keep adding arr[i], sum must never be >=0, except at Oth element. That was the opeartion about.

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

      i was iterating from backwards and decreasing the current element say a[j](initial array) by k such that it gets equal to m[j](given array) and adding k-1 to a[j-1] lastly i check that array is equal or not alongwith my pointer is on the first element or not this approach is giving wrong answer

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

    let j = position of last non-zero number (1-indexed)

    There must be no prefix sum of length i(0<i<j) with sum <= 0

    A[j] must be negative and total sum of array A = 0

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

Div2B was hard -_-

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

I'll suffer from PTSD from now on for string problems :(

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

what's the solution for div1A? I have no idea why I got AC

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

    Hey, Can I ask you, As a div 1 participant how was Div1B?

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

      actually pretty simple problem on dp on trees

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

        Can you please explain your solution, or suggest some similar dp on trees problems.

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

    I don't know if i am eligible to explain something to CM, but this is how I solved.

    • First I observed that if the first element = x, then we go right x times from first element.
    • If we go x times right from first then we must go left x times from second element.
    • since the second element = a[1] = ( number of rights from second — number of lefts from second). So we get right_times[1] = a[1] + x.
    • Similary construct for all indices. If any of them is negative then its not possible since we cant go negative number of times in some direction.
    • This is my code

    PS: We also need to check if at some point right[i] becomes zero then all the array elements from that index must be zero, since we dont move towards right anymore.

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

tox1c_kid got trolled

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

Do you have a small test case that fails this simple and wrong solution for 1E?

  • For each element, count how distinct values on the left that the smaller than the element
  • For each element, count how distinct values on the right that the smaller than the element
  • Take the sum of the minimum of the two counts for each element
  • »
    »
    21 месяц назад, # ^ |
      Проголосовать: нравится +8 Проголосовать: не нравится

    I also had the same idea, but here is the problem: It might be better to take the right maximum and then the left maximum afterwards.

    test case:

    5

    4 3 5 1 2

    The min for 4, 3, 1, 2 is clearly 1. But the min for the 5 would be 3. However, we can take right maximum and then left: 5 -> 2 -> 0. So answer is actually 1+1+2+1+1 = 6 instead of 7.

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

1693C - Keshi in Search of AmShZ is the problem of the year.

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

Problems were interesting.

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

So hard..... I can not solve (Div 1. C)1693C - Keshi in Search of AmShZ, I thought topological sorting + DP may work, but what if the graph has a loop and is not a DAG?`

`

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

    you run a djikstra-like algorithm on the reversed graph. In each iteration, my solution has an invariant that the nodes that have been popped from the set have the smallest values of $$$dp[u]$$$, where $$$dp[u]$$$ is the minimal cost required if one starts from node $$$u$$$ and goes to node $$$n$$$. We remove edges only when we are at the node from which the edge emanates (goes out). Then you can see how a djikstra-like algorithm always maintains this invariant, and hence answer is $$$dp[1]$$$.

    details: 160892338

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

      I appreciate it, I think I do not understand the idea of djikstra totally, it is time to take my DS book up again.

      Sadly, I may get a down rank.

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

D1C is amazing and suitable for commemorable 800th round, thanks!

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

I hope to reach expert next round :( :(

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

rainboy orz on astonishing participation! He won't become a GM after this contest but he really deserved it. This strategy of solving the problems starting with the harder ones is really not that bad, especially for educational purposes.

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

The best round recently I think! Thank the author!

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

small feedback: A is kinda cool, B&C both too standart IMO

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

Not sure about the complexity of "dive" function in my solution to D: 160848374. If anybody wants to try to create the test were the complexity is worse, you're welcome (don't know if it's correct or not).

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

    I think I did the same thing, guessing that it would work (somehow it did). I would also like to see a proof of why this type of memoization runs in linear time.

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

      Yeah. I’m doing more stuff, but I can believe that the transition is correct.

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

I am able to solve only problem A.

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

see https://codeforces.com/blog/entry/103952?#comment-923384

UPD: why downvotes ? I simply removed my original post

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

is "wrong answer jury had better answer" different from "wrong answer expected ,found"?

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

    It's 2 different types of problems: "jury" thingy appears where you have to calculate a minimum or maximum answer for example and at some point there is a possibility to have a better answer than yours, but "expected" simply stands for a wrong answer.

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

Thanks for the round, Div1 pC was really interesting!

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

What was the sol for Div2 C?

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

    I solved this problem using RBS (Regular Bracket Sequence) pattern. If you consider the positive numbers as the number of open brackets and the negative numbers as the number of closing brackets, you will see "If the total sequence is regular and it's closed then the answer is yes".

    So you will get Yes for ( ()()() ) or ((())) or ( ( () ((())) ) ). But if the bracket is like this ()()() then it's no because in this case you can't get back to the first index.

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

    If at any index < last index prefix sum is <= 0 || total sum != 0 then ans is no

    here last index is index of last non zero element.

    Take care of few edge cases such as all zero elements

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

Great contest. The problemset was amazing and so fun to solve. Enjoyed this contest so much.

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

I think the problem setter is a Radiohead fan. Some of the problem title is similar to Radiohead's song title . Or its just a coincidence .

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

very good and balanced round + interesting problems. Though I FSTed on div2c but was a silly mistake.

Overall thanks for the amazing round

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

How to solve Div2 D problem?

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

    do DFS on the tree.

    if the node children returned a number which is greater than or equal lv, just return the min of the returned value of the children and the rv

    if it is less than the lv, you need to make another operation to fix this issue, so you will increase sol by one, then you will need to return rv.

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

      But how do you prove that the configurations doesn't matter?

      In the sense , say a node has value 5.. 5 can be written as [1,1,3] , [1,2,2] and so on. But in your solution , you just see the min(sum, Ri).

      Why does your solution work? Proof?

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

        I can't understand what you mean by configuration and why there are 3 numbers in your examples.

        I am not good at writing formal mathematical proofs, but I will try to proof it logically.

        The current node doesn't care how many nodes under it, it only cares about the maximum value they all need, because it is the maximum value I can give to the current node, I can decrease it if I want, but I cannot increase it without an additional operation.

        But notice that the sum of all the child nodes values may be greater than Rv, so I take the min of them

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

Can anyone tell the testcase for which my submission is failing (Div2C):- Submission

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

luck maatters much in life

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

can someone tell me why i got tle'd in this submission https://codeforces.com/contest/1694/submission/160921292 Thank you