abc864197532's blog

By abc864197532, history, 3 years ago, In English

Hello, Codeforces!

dannyboy20031204 and I are glad to invite everyone to participate in Codeforces Round 772 (Div. 2), which will be held on Feb/20/2022 17:35 (Moscow time). This Round will be rated for participants with rating lower than 2100. You will have 2 hours to solve 6 problems.

We would like to thank:

Score distribution: $$$500 - 1000 - 1500 - 2250 - 2250 - 3000$$$

I hope all of you will enjoy the problems and have a positive delta. GL & HF ^^.

UPD1: Thanks for your participation! Editorial is out.

UPD2: Congratulations to the winners:

Div1 + Div2:

  1. jqdai0815
  2. eecs
  3. MatikaneTannhauser
  4. kotatsugame
  5. risujiroh

Div2:

  1. MatikaneTannhauser
  2. disorientation
  3. rainboy
  4. Bekzhan
  5. Vsinger_YuezhengLing
  • Vote: I like it
  • +650
  • Vote: I do not like it

| Write comment?
»
3 years ago, # |
Rev. 2   Vote: I like it +252 Vote: I do not like it

As a tester, I will tell you one possible solution to the problems:

Solutions
»
3 years ago, # |
  Vote: I like it +92 Vote: I do not like it

As a tester, this round is really worth to participate in

»
3 years ago, # |
Rev. 4   Vote: I like it 0 Vote: I do not like it

clashing with feb cook off

update : cook off posponded to 21 feb.

»
3 years ago, # |
  Vote: I like it +87 Vote: I do not like it

As a tester, I'll say that I think this round is very good!

»
3 years ago, # |
  Vote: I like it +67 Vote: I do not like it

As a tester, I think the problems are very interesting. May the force of positive delta be with you!

»
3 years ago, # |
  Vote: I like it +37 Vote: I do not like it

As a tester, I think the problems are very interesting. Good luck and have fun!

»
3 years ago, # |
Rev. 3   Vote: I like it +107 Vote: I do not like it

As not a tester, I hope participating this contest won't make my social credit and my rating decrease just like my contribution

  • »
    »
    3 years ago, # ^ |
    Rev. 2   Vote: I like it -30 Vote: I do not like it

    I wanted to upvote your comment, but this stopped me from doing so :)

    Spoiler
    :/
»
3 years ago, # |
Rev. 2   Vote: I like it +122 Vote: I do not like it

abc864197532 is a favorite to make it in the national IOI team and he will get gold medal in IOI 2022!

  • »
    »
    3 years ago, # ^ |
      Vote: I like it +11 Vote: I do not like it

    \abcorz/

  • »
    »
    3 years ago, # ^ |
      Vote: I like it +82 Vote: I do not like it

    BurnedChicken is also a favorite to make it in the national IOI team and he will also get gold medal in IOI 2022!

  • »
    »
    3 years ago, # ^ |
      Vote: I like it +28 Vote: I do not like it

    Fysty is also a favorite to make it in the national IOI team and the national IMO team and he will also get two gold medals in IOI 2022 and IMO 2022!

»
3 years ago, # |
  Vote: I like it +19 Vote: I do not like it

orzabc

»
3 years ago, # |
  Vote: I like it +102 Vote: I do not like it

As a tester and a statement verifier, I highly recommend participating in this contest! The problems are concise and well balanced, and I hope you'd find the problems (and editorial) easy to read.

»
3 years ago, # |
  Vote: I like it -8 Vote: I do not like it

As a tester, I want everyone to play osu! I hope everyone will enjoy this Taiwanese round.

»
3 years ago, # |
  Vote: I like it +46 Vote: I do not like it
Schrödinger's contest :D

Good luck and have fun!

»
3 years ago, # |
  Vote: I like it +19 Vote: I do not like it

\abcorz/

»
3 years ago, # |
Rev. 2   Vote: I like it +14 Vote: I do not like it

As a friend of a part of testers, why didn't I even hear this contest before this post :(
Never mind, it's time for me to participate :)

»
3 years ago, # |
  Vote: I like it +35 Vote: I do not like it

\8wcporz/

»
3 years ago, # |
  Vote: I like it +3 Vote: I do not like it

too few 1600-1900 problems in recent div2's, anyone?

  • »
    »
    3 years ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    The ideal order of the first three problems should be 800-900 -> 1100-1300 -> 1400-1700 I think

  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Yea, going to be speedforces for me unless I get enlightened by algod.

»
3 years ago, # |
  Vote: I like it -31 Vote: I do not like it

Good luck everyone for the round. May every newbie become green in this round.

»
3 years ago, # |
  Vote: I like it +46 Vote: I do not like it
Smile in pain
»
3 years ago, # |
  Vote: I like it +69 Vote: I do not like it

As a tester, I can confirm that the problems are all interested and worth reading. Good luck!

»
3 years ago, # |
Rev. 2   Vote: I like it -11 Vote: I do not like it

It's timing is clashing with IND vs WI match and Barcelona vs Valencia match on Sunday :(.

  • »
    »
    3 years ago, # ^ |
      Vote: I like it +48 Vote: I do not like it

    Then, it will clash with my murtastanbig time.

»
3 years ago, # |
  Vote: I like it +20 Vote: I do not like it

why is this blog still not at home page? eagerly waiting for this round , have always loved taiwanese contest problems :)

»
3 years ago, # |
  Vote: I like it -10 Vote: I do not like it

XDDDDD

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

I think this contest is gonna be cool.

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Which is the lie the mask or my face

»
3 years ago, # |
  Vote: I like it -122 Vote: I do not like it

Taiwan No.1! Taiwan No.1! Taiwan No.1! Taiwan No.1! Taiwan No.1! Taiwan No.1! Taiwan No.1! Taiwan No.1! Taiwan No.1! Taiwan No.1! Taiwan No.1! Taiwan No.1! Taiwan No.1! Taiwan No.1! Taiwan No.1! Taiwan No.1!

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

taiwan pog

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Codeforces contest question's are really good as compared to all other platforms.

»
3 years ago, # |
  Vote: I like it -19 Vote: I do not like it

who ask ???

»
3 years ago, # |
  Vote: I like it +2 Vote: I do not like it

It seems that there are some problems with the country filled in someone(who sets the theme)'s profile?

  • »
    »
    3 years ago, # ^ |
      Vote: I like it +19 Vote: I do not like it

    I have never seen a Chinese who does not fill in the motherland as China.

    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it -8 Vote: I do not like it

      Then you must havn't seen tibetan people who doesn't fill in the motherland as Tibet.

      • »
        »
        »
        »
        3 years ago, # ^ |
          Vote: I like it +3 Vote: I do not like it

        But the Taiwan independence elements took the opportunity to make trouble :).I still think there are some problems.

»
3 years ago, # |
Rev. 2   Vote: I like it +2 Vote: I do not like it

I hope to achieve new division as well as all participants

»
3 years ago, # |
  Vote: I like it +23 Vote: I do not like it

In this round, I will solve the problems and have some Waimai~

»
3 years ago, # |
  Vote: I like it +216 Vote: I do not like it

As a CPer, I don't care about politics at all. Let's just talk about problem quality/style/solution and make codeforces a CP community.

off-topic
  • »
    »
    3 years ago, # ^ |
      Vote: I like it +21 Vote: I do not like it

    He has two stars in Arcaea.

    \abcorz/

    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it +21 Vote: I do not like it

      dXqwq also has two stars, and their rating are also very high

      • »
        »
        »
        »
        3 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        feel bad when I realize that my best play is barely 12.5 :(

»
3 years ago, # |
  Vote: I like it +5 Vote: I do not like it

As not a tester, can we forcus on the contest, but not the authors?

»
3 years ago, # |
  Vote: I like it +99 Vote: I do not like it

Stop talking about Taiwanese Round and Chinese Round please, let's just participate in this round and you'll find out if it's interesting or not. By the way, Codeforces is not a place to talk about politics.

»
3 years ago, # |
  Vote: I like it +8 Vote: I do not like it

wow. I remember old dannyboy20031204 post about his fast level up in cp. And now he is problemsetter. Not Bad.

»
3 years ago, # |
  Vote: I like it +20 Vote: I do not like it

abc round on cf XD

»
3 years ago, # |
  Vote: I like it +22 Vote: I do not like it

»
3 years ago, # |
  Vote: I like it +24 Vote: I do not like it

Codeforces is not a place to talk about politics , if you want to talk about Taiwanese Round and Chinese Round , You are challenging China!

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

As a person writing a comment, I hope other people who write comments also write comments.

»
3 years ago, # |
Rev. 2   Vote: I like it +8 Vote: I do not like it

Remember that Codeforces is not used to talk about politics.It is home to people who like programming from all over the world.

»
3 years ago, # |
  Vote: I like it +23 Vote: I do not like it

Are you pretest 2,because i am not getting what's wrong with you

»
3 years ago, # |
  Vote: I like it +13 Vote: I do not like it

Can we just focus on the contest instead of the controversial political problems?

»
3 years ago, # |
  Vote: I like it +3 Vote: I do not like it

operationforces!

»
3 years ago, # |
  Vote: I like it +4 Vote: I do not like it

sadly Speedforces and I'm not fast enough :/
100 points could get me 600 higher position

»
3 years ago, # |
  Vote: I like it +17 Vote: I do not like it

my today contest scenario :3

Spoiler
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

How to solve the type of problems like D ?

  • »
    »
    3 years ago, # ^ |
      Vote: I like it +10 Vote: I do not like it

    I just used dynamic programming where $$$dp_i$$$ stands for number of elements between the range $$$[2^{i-1}, 2^{i})$$$. Then, $$$dp_i = dp_{i-1} + dp_{i-2}$$$.

»
3 years ago, # |
  Vote: I like it -43 Vote: I do not like it

I think pretests of E are very weak. In my solution, I did two topsorts for each component and even tho I forgot to clear the adjacency list after the first top-sort, it passed pretests and I resubmitted.

Also, Problem A-E for me in this round was 5 mins of thinking and all the rest time spent in coding. Problems were not nice [A-E].

»
3 years ago, # |
  Vote: I like it +5 Vote: I do not like it

literally solved first 3 pblms by simply guessing. Hope pretests were strong.

»
3 years ago, # |
  Vote: I like it +11 Vote: I do not like it

how to do F? Is it some DnC magic?

  • »
    »
    3 years ago, # ^ |
      Vote: I like it +42 Vote: I do not like it

    You can find that when the pair (x,y) is optimal , only if $$$\forall_{x<i<y} w_i>max(w_x,w_y)$$$.

    the number of such pair is $$$O(n)$$$.

»
3 years ago, # |
  Vote: I like it +1 Vote: I do not like it

Logic for C?

  • »
    »
    3 years ago, # ^ |
    Rev. 4   Vote: I like it +3 Vote: I do not like it
    1. you can't modify the last two elements, so if $$$a[n-2]>a[n-1]$$$ that's impossible to do what's requested.
    2. if $$$a[n-1] \geq 0$$$, then it is always possible (always choose $$$z = n-1$$$)
    3. if $$$a[n-1] < 0$$$, then the answer depends on whether $$$a$$$ is already sorted.
»
3 years ago, # |
Rev. 2   Vote: I like it +28 Vote: I do not like it

Hints for Problem D: Infinite Set

Hint 1
Hint 2
Answer to Hint 2
Hint 3
Answer to Hint 3
Hint 4
Answer to Hint 4
Generalizing for all n: Hint 5
Final Algorithm
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Would be more than grateful if someone could point out what I'm missing in my following submission to C: https://mirror.codeforces.com/contest/1635/submission/147096871

»
3 years ago, # |
  Vote: I like it +1 Vote: I do not like it

It was a blood lesson to use log instead of logf in the C++ 11 and later standards.

»
3 years ago, # |
  Vote: I like it +5 Vote: I do not like it

Was the idea of E something like this —

  1. Make a undirected graph according to input.
  2. If graph is not bipartite, print NO.
  3. Else, make another directed graph such that for each edge [u,v] in input, make an edge u -> v if [u,v] is of type 1, else make an edge v -> u.
  4. If there is a cycle in this new directed graph, print NO.
  5. Else, do a topo sort and give coordinates to each node in order they appear.
  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I didn't use step 3 and 4, but I did use a pseudo topsort where I first arbitrarily set one set of vertices of the bipartite graph as cars moving to the right, and the other set to be the cars moving to the left. Then, whenever a car moving to the left has destined cars all placed or a car moving to the right has irrelevant cars all placed already, we put this car into the queue.

  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Yes, but not exactly.

    In step 3, the direction depends on both the type and bipartite colouring of u / v. Basically our colouring means L / R right? So we want L before R for type 2 and L after R for type 1. So we need to check the colour of u / v to set this direction correctly.

    Except for that one change, your post exactly describes what my submission does — 147085911

  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I did almost the same you are describing, except that instead of toposort I used posorder in the dag (easier to code in my opinión).

»
3 years ago, # |
  Vote: I like it +32 Vote: I do not like it

Problem C, submited in 1:59:57..., and got accepted. Never give up. QAQ

  • »
    »
    3 years ago, # ^ |
      Vote: I like it +13 Vote: I do not like it

    Same here. I submitted C in 1:59:49 and I also got AC! These last moment's AC gives so much joy.

»
3 years ago, # |
  Vote: I like it +1 Vote: I do not like it

My idea for D :

  • Sort $$$a_i$$$ in ascending order
  • Make sure that I haven't counted the $$$a_i$$$ before. What I do to check :
  1. Suppose that $$$a_i$$$ is odd, then I divide $$$a_i$$$ by $$$2$$$
  2. Else, I check if $$$a_i$$$ is a multiple of $$$4$$$, if it is, I divide $$$a_i$$$ by $$$4$$$, otherwise I stop.
  3. If at any given moment $$$a_i$$$ exists, then I won't count this $$$a_i$$$ as an answer

Now how to count what are elements "connected" to $$$a_i$$$, this is what I did :

  • Find the MSB (most significant bit) of $$$a_i$$$ assume it's $$$x$$$
  • So now I want to count ways to represent $$$p-x-1$$$ as the sum of some number of $$$1$$$ and $$$2$$$. I can simply count this use the sum of first $$$p-x-1$$$ fibonacci numbers

But I get wrong answer on pretest 5, can you spot it where my idea / implementation might be wrong? My code : 147094782

  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I guess the recursion should've been $$$dp[x] = 1 + dp[x-1] + dp[x-2]$$$

    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Umm why is that?

      • »
        »
        »
        »
        3 years ago, # ^ |
        Rev. 3   Vote: I like it 0 Vote: I do not like it

        let's say $$$p=4$$$ and you have a number $$$1$$$, which is $$$0001$$$ (in binary form) you can also have $$$0100$$$ and $$$0011$$$, and the possible numbers are thus $$$dp[1] + dp[2]$$$, but you still have to count the $$$0001$$$ itself, which yields $$$dp[3] = 1 + dp[2] + dp[1]$$$

        • »
          »
          »
          »
          »
          3 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          Yeah I also think about that.. but why wouldn't the sum of fibonacci numbers solve this?

  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    while(tmp > 1){

    Shouldn't this line be while (tmp > 0)?

    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      I don't think that's the issue... because I check if $$$tmp = 1$$$, then I check whether 1 is in the set

      But it's also impossible since it is guaranteed that $$$a$$$ is distinct

  • »
    »
    3 years ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    Try this test:
    4 3
    1 3 4 7

    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Thanks for your test case! I got it accepted. It is a silly mistake that I made

  • »
    »
    3 years ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    Oh, I had this pretest getting me 7 times. I think there's a problem in choosing the correct i to summarise first I fibonacchi numbers: if i-th element of A is a degree of 2, (x-th), then you have to count first p-x-1, since our number has x+1 digits in binary system. Otherwise there are x digits and we have to count first p-x. Sorry if I'm wrong, but I think that's the problem.

    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Hmm.. but I used the MSB function to get the leftmost digit in binary. Shouldn't it be the same?

      • »
        »
        »
        »
        3 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Oh, I guess it is. Yeah, sorry

        • »
          »
          »
          »
          »
          3 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          No worries! Thanks for helping tho. Because this is very bother my mind :')

»
3 years ago, # |
  Vote: I like it -6 Vote: I do not like it

Very interesting problems.

Thank you writers, testers and coordinators so much!

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

How does B work, there is some "trick"?

  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    my greedy approach is:

    Process from left to right. whenever we meet a peak at $$$a[i]$$$, set $$$a[i+1] = max(a[i], a[i+2])$$$ and keep moving.

    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Ah, ok, I see.

      A local maximum counts only then as a local maximum if it differs from both adjacent elements, ie 2 3 3 2 is not a local maximum.

      I tried to solve a more complex problem :/

  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    always change next item A right after local max to max(local max from left, item right from A)

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Why is the output for Problem E test 2 'No'?

  • »
    »
    3 years ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    because here is cycle(1-2-3-1) of odd length. but directions changes between neighbors.

    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Where is it given that directions changes between neighbors

      • »
        »
        »
        »
        3 years ago, # ^ |
        Rev. 2   Vote: I like it 0 Vote: I do not like it

        Because if two irrelevant cars share directions, one have more speed than the other, they will meet.

»
3 years ago, # |
Rev. 2   Vote: I like it +8 Vote: I do not like it

Good problems but presets were weak

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

unfortunately ran out of time for problem D. anyone else solved it with sum of sums of fibonacci for unique items (in terms of reachable by 2*y+1 and 4*y)? will try submitting after system testing

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

sus likes to give feedback for contests instead of giving contest, after becaming pupil :)

»
3 years ago, # |
Rev. 3   Vote: I like it +1 Vote: I do not like it

missed some observations on C and ended up submitting a complicated solution very late

expecting a big rating drop, but it's also a good opportunity to find out my weaknesses

»
3 years ago, # |
  Vote: I like it +1 Vote: I do not like it

Great contest with interesting problems! plus amazingly fast rating changes!

»
3 years ago, # |
  Vote: I like it +8 Vote: I do not like it

Ratings updated preliminarily. We will remove cheaters and update the ratings again soon!

  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Rating only increases by one when cheaters are removed , so are there very less cheaters?

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

thanks for the fast editorial!

»
3 years ago, # |
Rev. 3   Vote: I like it +3 Vote: I do not like it

observationforces

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Can anyone help me out with the 4th problem. I calculated the Fibonacci series and recalculated the sum in the vector v.Then simply for every val in the array calculated the possible root val and if its not visited previously marked it and added the precomputed val to the ans.147109778 . Its giving was on test 5

»
3 years ago, # |
  Vote: I like it +6 Vote: I do not like it

D is a great problem!

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Finally some rating gain yay

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Thank you for great problems and fast editorial. I really enjoyed solving D and E. Very good round!

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

I enjoyed this contest solved A,B and C

  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Bro I am sorry if I demotivate you(I am just curious) , you have solved a lot of problems , how are you still green?

    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Yeah bro! same question i asked from myself :(

      • »
        »
        »
        »
        3 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        I think at this point , you should just start giving virtual contests instead of practicing from problem set. You already have learnt all the topics , now focus more on performing good in real contests.

»
3 years ago, # |
  Vote: I like it +7 Vote: I do not like it

As a first-time contestant for CF but years of experience on other CP contests, I kindly feel annoyed with that all problems in the contest are greedy related. Is this some norm for CF?

»
3 years ago, # |
  Vote: I like it +7 Vote: I do not like it

There was a fantastic round :) thanks.

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

D was a great question!Need both logic and algorithm ability.I like this problem.But somehow,as the rating contribution reflects,the gap between C and D are a bit big.