Vladosiya's blog

Codeforces Round #847 (Div. 3)
By Vladosiya, history, 23 months ago, translation, In English

Hello! Codeforces Round 847 (Div. 3) will start at 27.01.2023 17:35 (Московское время). You will be offered 6-8 problems with expected difficulties to compose an interesting competition for participants with ratings up to 1600. However, all of you who wish to take part and have a rating of 1600 or higher, can register for the round unofficially.

The round will be hosted by rules of educational rounds (extended ICPC). Thus, solutions will be judged on preliminary tests during the round, and after the round, it will be a 12-hour phase of open hacks.

You will be given 6-8 problems and 2 hours and 15 minutes to solve them.

Note that the penalty for the wrong submission in this round is 10 minutes.

Remember that only the trusted participants of the third division will be included in the official standings table. As it is written by link, this is a compulsory measure for combating unsporting behavior. To qualify as a trusted participant of the third division, you must:

  • take part in at least five rated rounds (and solve at least one problem in each of them)
  • do not have a point of 1900 or higher in the rating.

Regardless of whether you are a trusted participant of the third division or not, if your rating is less than 1600, then the round will be rated for you.

Thanks to MikeMirzayanov for the platform, help with ideas for problems and for coordination of our work. Problems have been created and written by ITMO University team: MikeMirzayanov, myav, Gol_D, Aris, Gornak40, senjougaharin and Vladosiya. Also this time, molney suggested one of the tasks.

We would like to thank: alwyn, morasha3, csegura, BledDest, stevenkplus, Darko, Coki628, Crutch, Qwerty1232, Jostic11, liouzhou_101, Jeffin, AW_Flister, glebustim, yorky, mango_lassi, 74TrAkToR, ErrorDeveloper, Be_dos, MODDI, Vercingetorix for testing the contest and valuable feedback. List of testers will be updated.

Good luck!

UPD: Editorial

  • Vote: I like it
  • +202
  • Vote: I do not like it

Comments Comments (283)
| Write comment?
»
23 months ago, # |
  Vote: I like it +18 Vote: I do not like it

Hoping for the first time getting AK (solve all problems) in this contest.

→ Reply
»
23 months ago, # |
  Vote: I like it 0 Vote: I do not like it

I just hope this round doesn't become unrated and no hearts are broken ;)

→ Reply
  • »
    »
    23 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Hoping +ve delta for every participant.

    → Reply
    • »
      »
      »
      23 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      -ve delta teaches more than +ve if you want to grow.

      → Reply
      • »
        »
        »
        »
        23 months ago, # ^ |
          Vote: I like it +3 Vote: I do not like it

        Yes you are also right. But if somebody already have rating < 900, how can he be happy with getting more -ve delta.

        → Reply
    • »
      »
      »
      23 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      You know that's impossible right ?

      → Reply
»
23 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Hopefully there will be no error like the yesterday contest

→ Reply
»
23 months ago, # |
  Vote: I like it +2 Vote: I do not like it

BTW the kitty in the Vladosiya's profile is very cute (◠‿◠)

→ Reply
»
23 months ago, # |
← Rev. 3   Vote: I like it +5 Vote: I do not like it

Iam new here and I didn't get the meaning of "penalty for the wrong submission in this round is 10 minutes", can anyone explain? .. Thanks in advance

→ Reply
  • »
    »
    23 months ago, # ^ |
    ← Rev. 2   Vote: I like it -32 Vote: I do not like it

    Sorry, I am unaware of this.

    → Reply
    • »
      »
      »
      23 months ago, # ^ |
      ← Rev. 2   Vote: I like it +8 Vote: I do not like it

      No. In div3, div4 and education rounds, contestants are ranked by the lexicographic order of (count of problems you've solved, (-1)*sum of the minutes after the contest begins of your accepted solutions), and every wrong submission you submitted (before the correct one) will let the second term -10.

      → Reply
  • »
    »
    23 months ago, # ^ |
      Vote: I like it +6 Vote: I do not like it

    If you make a mistake, then 10 penalties are added to your total penalty.

    → Reply
  • »
    »
    23 months ago, # ^ |
    ← Rev. 2   Vote: I like it +2 Vote: I do not like it

    [ Deleted ]

    → Reply
»
23 months ago, # |
  Vote: I like it 0 Vote: I do not like it

hoping to be Expert on this contest... Wish me Luck ... xD

→ Reply
»
23 months ago, # |
  Vote: I like it 0 Vote: I do not like it

What if I can't solve at least 3 problems?

→ Reply
»
23 months ago, # |
  Vote: I like it +7 Vote: I do not like it

As a tester, tested.

→ Reply
»
23 months ago, # |
  Vote: I like it 0 Vote: I do not like it

is it possible to getting everyone positive ratting?

→ Reply
  • »
    »
    23 months ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

    The total delta of every contestants will definitely be negative due to the algorithm of codeforces. However, there are many new accounts (or alt accounts) which participate in contests with 0~1 problem solved, each of them bring +1400 rating to the total rating of CF users (by the first 6 contests they take), which makes the total rating of active CF users being balanced.

    → Reply
»
23 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Very nice new rules for Div3 contests

→ Reply
»
23 months ago, # |
  Vote: I like it +1 Vote: I do not like it

omg blue round

→ Reply
»
23 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Hoping to remain specialist:)

→ Reply
  • »
    »
    23 months ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    Hoping for you to be an expert :)

    → Reply
»
23 months ago, # |
  Vote: I like it +4 Vote: I do not like it

Is it easier to increase rating in div3 than div 2 considering I am a specialist?

→ Reply
  • »
    »
    23 months ago, # ^ |
      Vote: I like it +9 Vote: I do not like it

    Yeah, because mostly you will be on the top of the ranking list so codeforces favours those who are top in the scoreboard. But you might fall hard if you can't solve according to your rating as you should do as a specialist.

    → Reply
»
23 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Finally, my time to shine

→ Reply
»
23 months ago, # |
  Vote: I like it 0 Vote: I do not like it

I have a question that usually I only need to take part in at least two rated rounds, but why this time I have to take part in at least five rated rounds? I'm very frustrated because I had only taken part in four:(

→ Reply
  • »
    »
    23 months ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

    Regardless of whether you are a trusted participant of the third division or not, if your rating is less than 1600, then the round will be rated for you.

    Since you are green, you don't need to worry about it.

    → Reply
»
23 months ago, # |
  Vote: I like it -7 Vote: I do not like it

ChatGPT here, participating in this Round ^^ This will be Fun.

→ Reply
  • »
    »
    23 months ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    I bet, you wont get single question right,,, if you are using only CHAT GPT, and no Human logic/intelligence ...

    → Reply
»
23 months ago, # |
  Vote: I like it 0 Vote: I do not like it

My Turn ...... :)

→ Reply
»
23 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Can someone suggest me some topics which are most common and helpful under problem ratings from 1200 to 1500?

→ Reply
  • »
    »
    23 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    number theory, greedy, implementation, constructive algorithms :)

    → Reply
»
23 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Hoping to be specialist :) There are only 4 ratings to go Don't let me down pls :)

→ Reply
»
23 months ago, # |
  Vote: I like it +3 Vote: I do not like it

Please no NP-hard problems. Please no NP-hard problems. :D

→ Reply
»
23 months ago, # |
  Vote: I like it +8 Vote: I do not like it

Can't wait to see hmzqaq's performance in this round. (He's duck_pear)

→ Reply
»
23 months ago, # |
  Vote: I like it 0 Vote: I do not like it

first unrated div3 contest for me..........it's unbelivable :)

→ Reply
»
23 months ago, # |
  Vote: I like it +5 Vote: I do not like it

Hoping to be a specialist... Wish me good luck.

→ Reply
»
23 months ago, # |
  Vote: I like it +5 Vote: I do not like it

Hopefully I can reach expert

→ Reply
»
23 months ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

Either my Code is Wrong or Something Else PROBLEM=B,

Verdict: WRONG_ANSWER Input 7, 2 2 1, 2 4 2, 4 9 5, 5 17 11, 3 15 10, 4 4 3, 5 20 15, Participant's output 1 1, 2 2, 1 1 3 4, 2 2 2 5 6, 5 5 5, 1 1 1 1, 3 3 3 6 5, Checker comment wrong answer wrong r: 15 expected, 14 found (test case 7)

→ Reply
  • »
    »
    23 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I'm getting something similar, on test case 5, my sequence sums up to 15. But it's getting wrong answer r: 10 expected, 9 found

    → Reply
  • »
    »
    23 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Not a bug, actually. Just can't tell why it's happening during contest, but it's not a bug. The best I can do is to advice reading the statement carefully.

    → Reply
    • »
      »
      »
      23 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      You were right. I reread it, made one slight change on an if statement, got AC.

      → Reply
»
23 months ago, # |
← Rev. 2   Vote: I like it +4 Vote: I do not like it

A channel is providing solutions in youtube live during contest. This is not fair. The round should be unrated.

→ Reply
  • »
    »
    23 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I think this comment should be removed asap so less people will see the link.

    → Reply
  • »
    »
    23 months ago, # ^ |
      Vote: I like it +2 Vote: I do not like it

    The same things had happened in some of the div2 contests before directly. However, those contests were rated too. So I thought it would be better to ignore them and just remove cheaters afterwards instead of making the whole contest unrated.

    → Reply
    • »
      »
      »
      23 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      How will you determine the cheater if he didn't copy the code but only copy the idea behind the implementation?

      → Reply
      • »
        »
        »
        »
        23 months ago, # ^ |
          Vote: I like it +1 Vote: I do not like it

        so you saying that more than thousand people that write it fair won get their delta because of one man?

        → Reply
  • »
    »
    23 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    it's much more unfair to make it unrated, because most of the people solved the problems on their own.

    → Reply
  • »
    »
    23 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Was it in your youtube feed?

    → Reply
»
23 months ago, # |
← Rev. 2   Vote: I like it +13 Vote: I do not like it

This contest is a little hard but quite interesting comparing with other div3 contests. Thanks for the authors' and testers' hard working!

→ Reply
»
23 months ago, # |
  Vote: I like it -25 Vote: I do not like it

Wtf this is not Div. 3

→ Reply
  • »
    »
    23 months ago, # ^ |
      Vote: I like it +7 Vote: I do not like it

    Sir Please be respectful here. Don't use those hard word. ~~~~~ I am sure you can express yourself even without those slang. ~~~~~

    → Reply
    • »
      »
      »
      23 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      and you (both of you) please go back to solving tasks?

      → Reply
      • »
        »
        »
        »
        23 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Bro F is out of my league. I have already solved till E within 50min. Waiting for editorial for elegant solution of F.

        → Reply
»
23 months ago, # |
← Rev. 2   Vote: I like it +30 Vote: I do not like it

→ Reply
»
23 months ago, # |
← Rev. 3   Vote: I like it -16 Vote: I do not like it

MikeMirzayanov

Someone with codeforces handle demons_paw is providing solutions of Codeforces Round 847 (Div. 3) Codeforces Round #847 (Div. 3) in youtube live during contest. This is not fair. The round should be unrated. I have sent the youtube live video link in your codeforces inbox. Edited**

→ Reply
  • »
    »
    23 months ago, # ^ |
      Vote: I like it +16 Vote: I do not like it

    Why do you share this in a public discussion post during a contest ? At least should wait until it’s over

    → Reply
    • »
      »
      »
      23 months ago, # ^ |
        Vote: I like it -12 Vote: I do not like it

      I think, there is a possibility that the youtuber can delete the live video at the end of the contest.

      → Reply
      • »
        »
        »
        »
        23 months ago, # ^ |
          Vote: I like it +4 Vote: I do not like it

        By the way, now you really should edit the comment and delete the link so that no one else can use it

        → Reply
  • »
    »
    23 months ago, # ^ |
      Vote: I like it +28 Vote: I do not like it

    Thank you, we've already seen it and we're really upset about it.

    Please don't cheat on the rounds! Firstly, it is forbidden. Secondly, it won't help you develop your competitive programming skills at all :(

    → Reply
  • »
    »
    23 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Was it in your youtube feed?

    → Reply
»
23 months ago, # |
  Vote: I like it +6 Vote: I do not like it

Finally I was able to use first 31 digits of pi from my template :D

→ Reply
»
23 months ago, # |
← Rev. 2   Vote: I like it +4 Vote: I do not like it

Me after solving A,B,C,D,E

→ Reply
»
23 months ago, # |
  Vote: I like it +6 Vote: I do not like it

Who else can remember PI without searching the google =)))) BTW, I really love all of the problems

→ Reply
  • »
    »
    23 months ago, # ^ |
    ← Rev. 2   Vote: I like it +1 Vote: I do not like it

    you don't have to remember pi, neither do you have to google for solving that problem. That's why I liked the problem (hint: look at the testcases)

    → Reply
  • »
    »
    23 months ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    you could just copy pi digits from the sample input xD

    → Reply
»
23 months ago, # |
  Vote: I like it +44 Vote: I do not like it

Problem G was worded very badly in English :notlikeblob: I wasted about 20 minutes just trying to understand the problem (the statement is much better now). Using terms like move / jump / turn interchangeably was just confusing, surprised this wasn't picked up in testing.

Even after I solved the problem, I had zero clue what this meant: "The same bonus can be used an unlimited number of times, but not more than once per turn."

?????

Oh well, still got 8th place :sunglasses: Screencast + editorial at https://www.youtube.com/watch?v=fVaNJ2eTegw&ab_channel=JoshuaChen :)

→ Reply
»
23 months ago, # |
  Vote: I like it +3 Vote: I do not like it

Problem A: The observant programmer might have noticed that one of the test cases included all 30 digits of pi for a quick copy and paste

Problem B: I spent more time deciding what the best way to implement would be than if I had just picked the slowest way and started writing it immediately

Problem C: Neat problem, interesting observation that the answer can be deduced from just the first 3 permutations and all of the other ones are irrelevant. Spent 30 minutes debugging poor code though.

Problem D: Standard frequency map problem

Problem E: A little disappointing that the solution was readily available on Geeks For Geeks, pretty sure most people just pasted the algorithm because it's allowed.

Didn't have time to solve F or G but F looked interesting.

→ Reply
  • »
    »
    23 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    how to solve E

    → Reply
    • »
      »
      »
      23 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      I literally don't know. Copy and paste this. https://www.geeksforgeeks.org/find-two-numbers-sum-xor/

      → Reply
    • »
      »
      »
      23 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it
      1. a+b is even as per the question so , if x = a xor b then x is bound to be even, since at a time both a and b can either be odd or even.
      2. Consider the bit positions where x is set, we are sure that for those bit positions only a is set or b is set. so for those bit positions say i; a[i]+b[i] = x[i]; the sum of those bit positions is x itself. let us call this sum as setSum.
      3. We know 2*x = a+b, then the sum of bit positions where a[i]==b[i] or x[i]=0 is 2*x-setSum is equal to x itself. let us call this sum as the otherSum.
      4. otherSum is equally distributed b/w a and b, so a and b will get equal share of otherSum/2. let us call this as Add.
      5. for any set bit position i of Add, x must not be set (because these are the bit positions where a[i]==b[i]) so if( x&(Add)!=0) solution is not possible.
      6. Hence one can give an easy answer to this as a= add, b = x+add or
      7. a = x/2, b = x+x/2 (giving all setSum to b only)
      → Reply
»
23 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Do we have to solve problem E using recursion?

→ Reply
  • »
    »
    23 months ago, # ^ |
    ← Rev. 3   Vote: I like it -11 Vote: I do not like it

    No. You just need to check if x is even and if (x + x/2) ^ (x/2) is equal to x. If both conditions are true, print x+x/2 and x/2 else -1.

    → Reply
    • »
      »
      »
      23 months ago, # ^ |
        Vote: I like it +1 Vote: I do not like it

      Wow. People hate this comment so much :/

      → Reply
      • »
        »
        »
        »
        23 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Did you hack your own solution PURPOSELY? What's the logic behind it?

        → Reply
»
23 months ago, # |
  Vote: I like it 0 Vote: I do not like it

How to prove D?

→ Reply
  • »
    »
    23 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Obviously if we have multiple of the same number we must start a new doll. And it also optimal to continue the streak of a previous doll if we have one. So greedy covers both cases.

    → Reply
»
23 months ago, # |
  Vote: I like it 0 Vote: I do not like it

how's D done anybody ?

→ Reply
  • »
    »
    23 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Sort the array and put each element into a frequency map. If freq[a[i]-1] == 0, increment answer by 1. Else, freq[a[i]-1] -= 1, because it can no longer be used. Then freq[a[i]] += 1 because it can be used for a bigger doll.

    → Reply
»
23 months ago, # |
  Vote: I like it +11 Vote: I do not like it

F was the same as: https://mirror.codeforces.com/problemset/problem/342/E

→ Reply
»
23 months ago, # |
  Vote: I like it -25 Vote: I do not like it

speedforces

→ Reply
»
23 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Problem F

→ Reply
»
23 months ago, # |
  Vote: I like it +6 Vote: I do not like it

This problem 342E. Xenia and Tree is almost similar to today's problem F :)

→ Reply
»
23 months ago, # |
← Rev. 3   Vote: I like it 0 Vote: I do not like it

Is there any wrong in my B? I output $$$s-r$$$, $$$\lceil r/{(n-1)}\rceil$$$ n-2 times and $$$r-(n-1)*\lceil r/{(n-1)}\rceil$$$. I have no idea why it is wrong.

→ Reply
  • »
    »
    23 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I was trying to find an elegant way to have n dice sum into the desired sum, and I settled on initializing an array with all 1's then replacing as many as I could with the max allowed dice number, then replacing the final 1 with the remainder.

    → Reply
»
23 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Lol, first tournament I have answered something. :)

→ Reply
»
23 months ago, # |
  Vote: I like it +7 Vote: I do not like it

How to do Problem F?? I thought of an approach of applying bfs every time I make a node black (bfs from ith node in array c) and whenever I reach a node which is already black I make my mini variable (which stores the min result till now) to be the min of previous mini and level of this bfs which took me to a black node

Why I think this should run!! lets say in worst case scenerio I have a linked list type tree then ttou can easily observe that you would take atmax n bfs steps to identify the first black guy then for the second time you would only take atmax n/2 and similarly next time n/4 .... which leads us to a very simple series sum n+n/2+n/4+n/6+....+n/n which I thought would work within the given time limit Also whenever my mini becomes 1 then I am simply breaking out and puuting all my ramaining answers to be 1 only

This apporach gave a TLE on test case 18 :(

can anyone please tell me what must be wrong in my approach

PS:- Sorry for the spelling mistakes if any :)

→ Reply
  • »
    »
    23 months ago, # ^ |
    ← Rev. 2   Vote: I like it +1 Vote: I do not like it

    The worst case scenario is a snowflake with sqrt(n) tails, every tail has sqrt(n) vertices and first sqrt(n) black guys are ends of a tail. The first sqrt(n) bfs will take n steps, so in worst case this algorithm has time complexity o(n^(3\2)). I think, that in this problem you must use LCA instead of BFS to find distances between the vertices

    → Reply
    • »
      »
      »
      23 months ago, # ^ |
        Vote: I like it +3 Vote: I do not like it

      Ohh Now I understood why it was giving TLE

      I got frustrated in the contest as I couldn't think of this worst case scenerio

      Thanks a lot man!

      → Reply
      • »
        »
        »
        »
        23 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        what is wrong with O(n^1.5)? Are we supposed to do better than this? I am running TLE on test 18 also.

        → Reply
        • »
          »
          »
          »
          »
          23 months ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          It would pass I guess But in my case I was using set instead of visited array (as array construction would take n time which would definitely give TLE) but since I was using set it would add extra complexity so I guess due to that it's giving TLE.

          I am just unable to think how to keep track of visited nodes within time limit as I want a new visited set or array for every ci.

          → Reply
          • »
            »
            »
            »
            »
            »
            23 months ago, # ^ |
            ← Rev. 2   Vote: I like it 0 Vote: I do not like it

            Did you AC at the end?

            My idea is to go through each black node and do a dfs up to answer steps, (answer is the min distant so far) and see if I can find another black node that is closer than answer. If I find one, update answer so that next time we can dfs less depth. However, this will tle at test case 18. I thought the time complexity is O(n^1.5), but clearly this will TLE. Appreciate if anyone can help me understand why.

            My submission 190916688

            → Reply
»
23 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Any hint for F?

→ Reply
  • »
    »
    23 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    you can dfs to update the minimum dis of every white nodes to the nearest black node, and we need to set the maximum dfs dep to the curr ans.

    Or just spam Centroid (it's very similar to this problem 342E

    → Reply
»
23 months ago, # |
  Vote: I like it +16 Vote: I do not like it

Let us not mention the fact, that tasks E and F are very well-known, what is a purpose of giving task A?

Tasks B C D G were great though.

→ Reply
  • »
    »
    23 months ago, # ^ |
      Vote: I like it +10 Vote: I do not like it

    Is F well known coz it is repeated? Or the concept well known as well? Hints also pls :D

    → Reply
    • »
      »
      »
      23 months ago, # ^ |
        Vote: I like it -8 Vote: I do not like it

      This task can be solved with centroid decomposition. If you are using it, you can just follow some well-known approach.

      I wasn't participating the round, but it seems to me that this task is solvable by DSU. If we will suppose that there can't be two adjacent black nodes, then if you will treat black nodes as deleted, the answer is the size of minimal component plus one. However I'm not sure this will work. But the fact that the task can be solved with centroid decomposition using some well-known approach makes this task well-known and thus not suitable for the round.

      → Reply
  • »
    »
    23 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I am wondering how you tell your opinion about the problems without participating in the round, I think something is sus here

    → Reply
    • »
      »
      »
      23 months ago, # ^ |
        Vote: I like it +10 Vote: I do not like it

      See, I'm a master, and I can read the tasks, think a little bit and come up with a solution :)

      → Reply
  • »
    »
    23 months ago, # ^ |
      Vote: I like it +15 Vote: I do not like it

    I really liked A because instead of calculating the value of pi upto 30 places or searching it on the internet , i for a moment looked at the samples and found the asnwer's is already there and tbh it made me chuckle a bit and i started rest of the contest with smile. i don't know it's purpose and but yeah that's how it made me feel!

    → Reply
»
23 months ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

My solutions for the first four problems:

Problem A:

Spoiler

Problem B:

Spoiler

Problem C:

Spoiler

Problem D:

Spoiler
→ Reply
  • »
    »
    23 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Could D be solved this way but counting decreasing values instead of increasing?

    → Reply
»
23 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Can some one explain me how were the rules of the game for problem G?

I didn't understand the problem statement :(

→ Reply
»
23 months ago, # |
  Vote: I like it 0 Vote: I do not like it

hi im new here, is this rated or unrated cuz i wanna get a rating but when i click on my profile it says that this contest is unrated, but in this announcement it says its rated, thanks :)

→ Reply
  • »
    »
    23 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    All contests will be shown as unrated until the rating update is calculated.

    → Reply
»
23 months ago, # |
← Rev. 2   Vote: I like it +3 Vote: I do not like it

Problem F is similar(same) to 342E - Xenia and Tree! I would like to ask why to give a Centroid Decomposition problem in Div3 round? (it's for < 1600 people) is it expected from them to know Centroid Decomposition??

→ Reply
  • »
    »
    23 months ago, # ^ |
      Vote: I like it +29 Vote: I do not like it

    Cause this problem can be solved without centroid decomposition. Don't assume your way is the only way to solve a problem.

    → Reply
  • »
    »
    23 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I spend way too much time reading random CF blogs and immediately thought of centroid decomposition because there was a recent action on a blog about it. But I've never even experimented with the algorithm so I didn't even try to solve it with my remaining time.

    → Reply
  • »
    »
    23 months ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    We can solve this problem by DFS with maximum depth set to the current answer. I passed it without centroid decomposition.

    → Reply
    • »
      »
      »
      23 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Is this n log n? Because if the black vertices were adversarially chosen then they have to be at least at the half way distance between two other black vertices?

      → Reply
      • »
        »
        »
        »
        23 months ago, # ^ |
          Vote: I like it +6 Vote: I do not like it

        Although I can't prove it I think so. IMO the worst situation of my solution is: The graph is a chain with 2^n+1 nodes, and black nodes are added by the order (0, 2^n, 2^(n-1), 2^(n-2), 3*2^(n-2), …) where time complexity is O(n*log(n)).

        → Reply
        • »
          »
          »
          »
          »
          23 months ago, # ^ |
            Vote: I like it +30 Vote: I do not like it

          Unless I am misunderstanding your solution, the complexity is at best $$$O(n \sqrt n)$$$. Consider a set of paths of lengths $$$b, b+1, \dots, 2b$$$ merging at a single vertex, and $$$O(n)$$$ leaves connected at that single vertex. The vertices at the ends of the paths turn black one by one, starting from the longest path. For the first $$$O(\sqrt{n})$$$ vertices that turn black, every leaf adjacent to the path merging point is visited, thus at least $$$O(n \sqrt{n})$$$ vertices are visited in total.

          → Reply
          • »
            »
            »
            »
            »
            »
            23 months ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            Enlightening example, thanks

            → Reply
          • »
            »
            »
            »
            »
            »
            23 months ago, # ^ |
            ← Rev. 2   Vote: I like it 0 Vote: I do not like it

            What is the number of edges in this case? I think the complexity is O(min(m, n*sqrt(n)))

            upd: ...My comments above is wrong, I was thinking, for each node, there should be a value stored indicating the nearest black node, If that information is maintained, not necessarily accurate but should be accurate if the value is smaller than current result, then for this test case, bfs should stop when reach the 'root', the complexity is O(m).

            → Reply
          • »
            »
            »
            »
            »
            »
            23 months ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            I tried solving F using bfs with some optimization, but got TLE on test case 20, can you or anyone please help with what is the time complexity of my solution, and why it's failing. 190874842

            → Reply
          • »
            »
            »
            »
            »
            »
            23 months ago, # ^ |
            ← Rev. 2   Vote: I like it 0 Vote: I do not like it

            can you please explain that how is the complexity O(n√n)? I am not able to understand ur previous answer?

            → Reply
  • »
    »
    23 months ago, # ^ |
      Vote: I like it +17 Vote: I do not like it

    We solved it without centroids (didn't even think about it), so we decided it would be just a great task.

    → Reply
»
23 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Had solved all problems in a Div 4 earlier, today solved all problems in Div 3.

→ Reply
»
23 months ago, # |
← Rev. 4   Vote: I like it +10 Vote: I do not like it

All problems solved (if no FST).

A: Ctrl+C the last line of the example and Ctrl+V to the code.

B: Do division with remainder for r and n-1.

C: For numbers with initial position i in range [1,n-1], the position after remove a number will be i or i-1. If i==n, the position after remove will be only i-1. Therefore by count the miminum and maximum position of numbers in each permutations after removal, we can find their initial position.

D: Greedy. Always remove a maximal equidistant sequence with common distance 1. But we need implement this solution by an ordered map. We count the time of occurence of each number and store them in a map, and for each adjacent key-value pair [k1,v1] and [k2,v2], if k1+1==k2 we add max(v2-v1,0) to answer (because we can extend some sequences containing k1 to k2), if k1+1<k2 we add v2 to answer (because k1 and k2 cannot appear in any same sequence).

E: By the equality (a^b)+2*(a&b)=a+b, we need to let a^b=2*(a&b)=(a&b)<<1=x. Therefore, if x is odd number or x&(x/2) is not zero, there's no solution, otherwise (3*x/2, x/2) is a solution,

F: We use dfs to update the minimal distance of every white nodes to the nearest black node, but we need to set the maximum dfs depth to the current answer.

G: First we need to check if node 1 or any neighbor of 1 has token on it. If not, use bfs to search how many tokens can reach node 1 by any sequence of bonus nodes. If there's no such token, there's no solution; if there're >=2 such token, we can move them alternately to node 1. If there's exactly 1 token, we need to check if there's other movable token and how many times we can move them. We need to check for every edge (u,v), if u, v are both bonus nodes, mark them as "infinite move". Then for each tokens we check if they have any adjacent bonus node. Therefore, the final condition is: there's some other node adjacent to an "infinite move" bonus node, or the number of movable token (except the one can reach node 1) >= (the distance of the reachable token to node 1)-1.

→ Reply
  • »
    »
    23 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    You can do F with centroid decomposition.

    → Reply
  • »
    »
    23 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Missed the last condition in G

    → Reply
  • »
    »
    23 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Do you know exact proof for D? thanks

    → Reply
  • »
    »
    23 months ago, # ^ |
    ← Rev. 2   Vote: I like it -8 Vote: I do not like it

    Here's this bizarre solution for E I found right after the contest ended (I solved it the same method with yours in contest). Just try $$$(\lfloor n/2 \rfloor, \lceil 3n/2 \rceil)$$$, if their XOR is $$$n$$$, then that is the solution. else, -1. I don't understand why this approach works, but it seems like it does.

    Also, here's a very elegant solution for C, which I came up with because I didn't want to do make implementation a rigorous job. Basically, just sort by sums of indices. Submission goes to 190790499.

    → Reply
    • »
      »
      »
      23 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      That's what tourist has done

      → Reply
      • »
        »
        »
        »
        23 months ago, # ^ |
          Vote: I like it -8 Vote: I do not like it

        Yep, I just saw. Doesn't change the fact that I found the method by myself, though. Let's just say that we both found it independently.

        → Reply
    • »
      »
      »
      23 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      I found this during the contest, but forgot to check if their XOR is $$$n$$$.

      → Reply
  • »
    »
    23 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Can you explain your dfs solution a little more?

    → Reply
    • »
      »
      »
      23 months ago, # ^ |
      ← Rev. 5   Vote: I like it -16 Vote: I do not like it

      The answer decreases on every step, and this rate of descent is very quick. For a worst case, lets say, the first two colored nodes are on the diameter of the tree, and the third colored node is on a centroid. You can see that now the answer is halved. So even on the worst case, we will use an average $$$O(n \log n)$$$ time complexity in total. If we consider every worst case (such as an "f$%&ed up star", a term I just came up with, which is like a star but there are $$$O(\sqrt n)$$$ paths with length $$$O(\sqrt n)$$$), the worst case will probably be $$$O(n \sqrt n)$$$. Definitely not $$$O(n^2)$$$, though.

      UPD: actually I am pretty sure it's $$$O(n \sqrt n)$$$ or better even in the worst case, that "f$%&ed up star" in fact starts to get towards $$$O(n \log n)$$$ after $$$O(\sqrt n)$$$ steps, $$$O(n)$$$ each step.

      → Reply
  • »
    »
    23 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I used the same logic for G but it gives wrong answer on testcase 5,i've spent two hours trying o decode but can't find it. here's my solution- https://mirror.codeforces.com/contest/1790/submission/190884446 any help is highly appreciated.

    → Reply
    • »
      »
      »
      23 months ago, # ^ |
        Vote: I like it +1 Vote: I do not like it

      Try to add vis[v]=true after q.push[v].

      My first wrong submission also made this mistake, which caused distance was calculated incorrectly.

      → Reply
  • »
    »
    23 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I use the similar idea for F (i.e. limiting the distance by using current answer for traversal) but using BFS to implement it but got TLE in case 18.

    Any idea what's the catch?

    → Reply
  • »
    »
    23 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    (a^b)+2*(a&b)=a+b Where did everyone get this formula from, how does it work out. Explain, thank you.

    → Reply
    • »
      »
      »
      23 months ago, # ^ |
      ← Rev. 2   Vote: I like it 0 Vote: I do not like it

      (a^b)=(a|b)-(a&b) by the definition of xor

      (a|b)=(a+b)-(a&b) by the inclusion-exclusion principle

      → Reply
»
23 months ago, # |
  Vote: I like it 0 Vote: I do not like it

This is my solution for F , it keeps getting TLE on test1 and i don't have a damn clue why:(

can any one tell ?

190880017

→ Reply
  • »
    »
    23 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    in the init function, the declaration is wrong. you need to specify the type.

    → Reply
»
23 months ago, # |
  Vote: I like it 0 Vote: I do not like it

How to solve E(with proof)?

→ Reply
  • »
    »
    23 months ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    We know that, a+b = a^b + 2*(a&b) here a^b is given let say it is x, and sum is given as 2x so, 2x = x + 2*(a&b) =>  a&b = x/2 , so all bits of x/2 should be there in both a and b, and x should be even, if odd then answer is not possible

    so, both a and b are atleast equal to x/2.

    now bits of x should not be present in both a and b otherwise it will not be present in their xor which is x, so x^(x/2) must be 0, if not then ans is not possible else we can add x to any of them and answer would be 3x/2 and x/2 190824234

    → Reply
    • »
      »
      »
      23 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Where do you learn things like a+b = a^b + 2*(a&b)? I never seen it in my life

      → Reply
      • »
        »
        »
        »
        23 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        You can read about bitwise math properties or you can discover them through problems

        → Reply
  • »
    »
    23 months ago, # ^ |
    ← Rev. 3   Vote: I like it 0 Vote: I do not like it

    well. my solution is bit complicated i guess but

    1) it's not hard to prove that a+b = (a^b)+2(a&b) (consider 4 cases when ith bits are (0,0), (0,1), (1,0) and (1,1) and check that this statement is true)

    2)by definition a+b = 2*(a^b) => a^b = 2(a&b).

    2.1) it's not hard to see that if (a^b)%2==1 then there is no solution because a^b must be even because it's equal to 2(a&b).

    2.2) but there is some even numbers that can't be answers too. lets consider some cases:

    • if a and b have the same leftmost bit X than XOR on position X must be (1^1)=0, but at the same time AND on position X must (1&1)=1 => this case is not possible, so leftmost bit in a and in b not in the same position. now lets say that a>b so leftmost bit in a is more that in b.

    • if a>b it means that on position X XOR equals (1^0)=1 and AND equals (1&0)=0. but we remember that (a&b)+(a&b)=a^b => X-1 th bit of a&b must be 1 (otherwise a&b + a&b != a^b) => but if X-1 th bit of a&b is 1 that X-1 th bit of a and b is 1 simultaneously => X-1 th bit of a and b is 1. => X-1 th bit of a^b is 0.

    • but we can use the same approach for every 1 in a^b. according to the above, if we see 1 in the position Y in a^b, then in the position Y-1 we MUST have 0 (otherwise we won't have a&b + a&b = a^b)

    2.3) now we need to iterate over a^b and check if there is exist two adjacent indices M and M+1 such that M==(M+1)==1. if they exist, then answer is -1. otherwise we can get answer.

    3) iterate over a^b. if bit X is 1 then a+=(1<<X) (a>b because i want so) and a+=(1<<(X-1)), b+=(1<<(X-1)) (because as i proved it above, X-1 th of a&b must be 1). thats all.

    → Reply
»
23 months ago, # |
  Vote: I like it 0 Vote: I do not like it

anyone can tell me test case which hacked D

→ Reply
»
23 months ago, # |
← Rev. 3   Vote: I like it 0 Vote: I do not like it

how to solve e ?

a xor b= 2*(a & b) after this observation?

→ Reply
  • »
    »
    23 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    x = 2 * (a & b)

    So a and b has similar bits to x / 2, let's say:

    a = x / 2; b = x / 2

    But, to maintain equation (a + b) / 2 = x, a should be 3 times bigger:

    a = 3 * x / 2; b = x / 2

    If this is not a valid pair, then there is no answer

    → Reply
    • »
      »
      »
      23 months ago, # ^ |
      ← Rev. 2   Vote: I like it 0 Vote: I do not like it

      a should be 3 times bigger ? how i'm not getting this point?

      → Reply
      • »
        »
        »
        »
        23 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        if (a + b) / 2 = x, and b = x/2, then:

        (a + x/2) / 2 = x

        a + x / 2 = 2 * x

        a = 2 * x — x / 2

        a = (3 * x) / 2

        → Reply
    • »
      »
      »
      23 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      how can we conclude that is this is not a valid pair then no other pair is possible? I am stuck in this statement.. PLease help.

      → Reply
»
23 months ago, # |
  Vote: I like it +1 Vote: I do not like it

Nice problems like all other div 3s. orz ITMO University team

→ Reply
»
23 months ago, # |
← Rev. 4   Vote: I like it +12 Vote: I do not like it

My solution got TLE on test on problem F

I've used Heavy-light technique.

I thought the solution should fit in the time limit, but I was wrong

Any thoughts why ??

My solution

solution explanation

and BTW very nice contest today ORZ

Update : thie solution passed, i had to make a small change to make bfs code faster

→ Reply
»
23 months ago, # |
← Rev. 3   Vote: I like it 0 Vote: I do not like it

**edit dont't try it, I made a mistake

In problem G why does this case's answer is "NO"?

1
4 4
2 2
2 1
2 1
1 2
1 3
1 4
2 3
→ Reply
»
23 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Hi Guys! If you are upsolving and want help with video tutorials you can refer this: https://youtu.be/YEyg27tm2sQ

→ Reply
»
23 months ago, # |
  Vote: I like it 0 Vote: I do not like it

This contest had a lot of "standard" problems. Seems like both E and F could just be looked up, which is a little unfortunate.

→ Reply
  • »
    »
    23 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I think F was a good one, but for E yes it was standard, Actually I just searched for "How to find two numbers a, b where their sum is S and their xor is x"

    → Reply
  • »
    »
    23 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Agreed, I feel as though alot of people who did E just googled it, which makes rankings unfair.

    → Reply
    • »
      »
      »
      23 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      You could google it too :)

      → Reply
      • »
        »
        »
        »
        23 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        I would not cheat

        → Reply
        • »
          »
          »
          »
          »
          23 months ago, # ^ |
          ← Rev. 2   Vote: I like it +1 Vote: I do not like it

          It's not cheating, because it's legal

          You are not searching for a fresh solution for this problem, you are searching for a similar problem

          → Reply
          • »
            »
            »
            »
            »
            »
            23 months ago, # ^ |
              Vote: I like it +9 Vote: I do not like it

            It is legal according to the rules, but it feels unfair and I don't want to gain rating I don't deserve.

            → Reply
            • »
              »
              »
              »
              »
              »
              »
              23 months ago, # ^ |
                Vote: I like it +1 Vote: I do not like it

              ok it's up to you :D

              → Reply
            • »
              »
              »
              »
              »
              »
              »
              23 months ago, # ^ |
                Vote: I like it 0 Vote: I do not like it

              oh shut it now, googling is also a skill and searching for hints to crack the problem will help you in the long run

              → Reply
              • »
                »
                »
                »
                »
                »
                »
                »
                23 months ago, # ^ |
                  Vote: I like it -12 Vote: I do not like it

                sve ću vas pobit majku vam jebem retardiranu

                → Reply
                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  23 months ago, # ^ |
                    Vote: I like it -13 Vote: I do not like it

                  literaly nuke india and dont flinch

                  → Reply
»
23 months ago, # |
← Rev. 3   Vote: I like it -32 Vote: I do not like it

Problem F, why TLE? just java(use java17)?

→ Reply
  • »
    »
    23 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    My similar C++ solution runs for 800-900 ms, and jaTLEva often cost 4-5x times…

    → Reply
»
23 months ago, # |
← Rev. 3   Vote: I like it 0 Vote: I do not like it

The data of problem C is too weak. There is not even a test case with $$$T=10000$$$. I hacked many people by $$$T=10000$$$.

→ Reply
  • »
    »
    23 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    How? It says "the sum $$$n^2$$$ over all input sets does not exceed 2⋅10^5."

    → Reply
  • »
    »
    23 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Can you try hacking mine? I'm trying but it says Testcase can not be longer than 256 KB ;-;

    → Reply
»
23 months ago, # |
  Vote: I like it 0 Vote: I do not like it

The name of problem B looks pretty familiar :)

→ Reply
»
23 months ago, # |
  Vote: I like it +3 Vote: I do not like it

nuke cheaters pls

→ Reply
»
23 months ago, # |
  Vote: I like it +4 Vote: I do not like it

Concerns about problem E.

After the contest I visited a few solutions and searched online. There are codes available online to determine two numbers from their sum and XOR.I copied one solution and changed it a bit (i)in order to run for t test cases and (ii) set Sum to x*2,where x was the given XOR of a and b. It got accepted. Is it okay to have this type of problem which has solutions available online?

→ Reply
»
23 months ago, # |
  Vote: I like it +5 Vote: I do not like it

For F, how to prove the efficiency of "keep doing BFS from every c[i], but only push a new node in the queue if its distance is getting decreased"

→ Reply
  • »
    »
    23 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    How about the case when tree is
    c0->c1->c2......ci->ci+1->....->cn
    for each i, doesnt it takes O(n)?

    → Reply
»
23 months ago, # |
← Rev. 3   Vote: I like it +9 Vote: I do not like it

I have solved problem F with sqrt-decomposition over queries in 997 ms. Solution.

We can divide all queries in $$$\dfrac{n}{\sqrt{n}}$$$ blocks with size of block equal to $$$\sqrt{n}$$$. When we reached a border of current block, we can run multi-bfs from all of black vertices in this block and calculate vector dist[u] = distance to nearest black vertex from vertex u. Also we can calculate distance between two vertices in same block with LCA in $$$O(1)$$$.

So, solution works in $$$O(n \cdot \sqrt{n})$$$.

→ Reply
  • »
    »
    23 months ago, # ^ |
      Vote: I like it +10 Vote: I do not like it

    This was my solution from the testing phase, and I had one hell of a time squeezing it into TL. Thankfully, the problem authors increased the TL after this.

    → Reply
»
23 months ago, # |
  Vote: I like it 0 Vote: I do not like it

problem F more like Xenia and Tree 2

→ Reply
»
23 months ago, # |
  Vote: I like it 0 Vote: I do not like it

190861468 can anyone try to hack my E solution? I do not have proof for this approach

→ Reply
»
23 months ago, # |
  Vote: I like it +1 Vote: I do not like it

https://www.geeksforgeeks.org/find-pair-of-integers-such-that-their-sum-is-twice-their-bitwise-xor/?ref=rp same question

→ Reply
»
23 months ago, # |
  Vote: I like it 0 Vote: I do not like it

F problem, so many Python submissions got TLE, but the same of C++ can just AC, that's not fair! I think the tester at least should test some widely used language, not just C++!

→ Reply
  • »
    »
    23 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    the TL is 4 seconds, i do not think the authors could've possibly made it more otherwise people would just brute it, tourist's solution was under 200ms.

    → Reply
    • »
      »
      »
      23 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      But some red can't pass it using python, so if we have different TL for different language, this problem will be solved. I know it's hard to change, but it's really a good direction

      → Reply
»
23 months ago, # |
  Vote: I like it 0 Vote: I do not like it

it seems that no one can hack the code in $$$O(n^3)$$$ in problem C. I think this is a mistake. A better way is to make $$$1\leq n\leq 100, 1\leq t \leq 1000$$$.

→ Reply
»
23 months ago, # |
  Vote: I like it 0 Vote: I do not like it

How to solve F using DFS approach?

→ Reply
  • »
    »
    23 months ago, # ^ |
      Vote: I like it +20 Vote: I do not like it

    Let's call dis[u] as the minimized distance that all black vertices to u.

    For each $$$C_i$$$ ，we DFS it while calculating the depth. When DFS v and dis[v] is less or equal to the depth, we break the chain.

    We can demostrate that it's $$$O(n \sqrt n)$$$ ，because：

    1、For the first $$$\sqrt n$$$ vertices that will be black, all vertices' dis[u] will be updated for max $$$O(n)$$$ times，that's $$$O(n \sqrt n)$$$ ；

    2、After that, each dis[u] will be less than $$$\sqrt n$$$. When we DFS the other vertices, each dis[u] will be updated for max $$$O(\sqrt n)$$$ times，that's $$$O(n \sqrt n)$$$ .

    → Reply
    • »
      »
      »
      23 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      How are you calculating dis[u] and couldn't understand this statement " For each Ci,we DFS it while calculating the depth. When DFS v and dis[v] is less or equal to the depth, we break the chain". Could you explain it in detail

      → Reply
      • »
        »
        »
        »
        23 months ago, # ^ |
          Vote: I like it +1 Vote: I do not like it

        DFS from the vertice that be black just now, and update each dis[u] with dis[u] = min(dis[u],depth). When dis[u] is already no larger than your DFS depth, it's ok to return.

        Sorry for my poor explanation, it's my first time to comment this at cf:)

        → Reply
        • »
          »
          »
          »
          »
          23 months ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          Hey, how do you prove that the for later sqrt(n) queries they'll take at max sqrt(n) time? And what is the worst case tree for your solution?

          → Reply
          • »
            »
            »
            »
            »
            »
            23 months ago, # ^ |
              Vote: I like it +4 Vote: I do not like it

            Actually I also was thinking about this.

            IMO, it's not necessary that for each dis[u] will be less than $$$\sqrt{n}$$$. However, $$$ans = \min_{u}{dis[u]}$$$ would be less than $$$\sqrt{n}$$$ within $$$O(\sqrt{n})$$$. After than, when doing DFS (or BFS), each node will be updated only up to $$$\min(ans, dis[u])$$$ number of times.

            Why ans is less than $$$\sqrt{n}$$$ within $$$O(\sqrt{n})$$$ is where I am not exactly sure. This can be organized as the size of maximum subset of vertices such that the minimum distance between each pair of vertices is $$$\ge \sqrt{n}$$$. Just a heuristic explanation is that most of the vertices will be covering at least $$$\sqrt{n}$$$ vertices within $$$\sqrt{n}$$$ distance.

            → Reply
            • »
              »
              »
              »
              »
              »
              »
              23 months ago, # ^ |
              ← Rev. 2   Vote: I like it 0 Vote: I do not like it

              so the worst case would be a linked list with the first sqrt(n) queries on consecutive nodes from one end? Tbh this "all queries after first sqrt(n) queries will give an answer of <= sqrt(n) seems so intutive rn but IDK how to prove it mathematically.

              → Reply
            • »
              »
              »
              »
              »
              »
              »
              23 months ago, # ^ |
              ← Rev. 2   Vote: I like it +3 Vote: I do not like it

              After handling $$$k$$$ nodes the maximum distance must be at most $$$2n / k$$$. Consider a ball of radius $$$r$$$ around each of the black nodes. If some two of these balls intersect, the corresponding black vertices have distance at most two times the radius of the balls minus one, which is $$$2r - 1$$$. Otherwise, we have $$$k$$$ disjoint balls containing at least $$$r + 1$$$ vertices each, which is a contradiction for $$$r \geq n/k$$$.

              → Reply
            • »
              »
              »
              »
              »
              »
              »
              23 months ago, # ^ |
                Vote: I like it 0 Vote: I do not like it

              Oops, i made a mistake:(. Not dis[u] is no larger than sqrt(n). Actually it's the update times of each node is O(sqrt(n)) for later queries. Thank you for making i realize it!

              → Reply
»
23 months ago, # |
  Vote: I like it 0 Vote: I do not like it

So will this round be rated? >_<

→ Reply
»
23 months ago, # |
  Vote: I like it +3 Vote: I do not like it

When rating will appear?

→ Reply
»
23 months ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

i didn't understand #D can someone explain me please?

→ Reply
  • »
    »
    23 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Consider sets of nesting dolls. They are segments consisting of consecutive numbers. Then there is the following solution: 1) sort the array 2) go through the elements in a row and see how many such elements there are. Let the elements x, the element itself, well, If the elements with a value of x — 1 are less, then we need to add to the answer the difference of these two numbers, because we need to create all sets of nesting dolls, in which the element x — 1 is not included in them. 3) output the answer This can be conveniently done using map (you can see my solution). P.S. I do not know English, so please forgive me typos or some grammatical errors.

    → Reply
»
23 months ago, # |
← Rev. 2   Vote: I like it +2 Vote: I do not like it

When will wait over ? UPD: wait over.

→ Reply
»
23 months ago, # |
  Vote: I like it 0 Vote: I do not like it

System testing has been finished??

→ Reply
»
23 months ago, # |
  Vote: I like it 0 Vote: I do not like it

I am new here (kinda), I don't know why this contest shows up on my profile as unrated ?

→ Reply
  • »
    »
    23 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    All contests are unrated until the ratings are updated.

    → Reply
»
23 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Publish the Editorial plz

→ Reply
»
23 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Why is this round not rated for me? My rating is well below 1600. The final standings are out, yet i dont see any changes in my rating.

→ Reply
  • »
    »
    23 months ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    The system testing hasn't started yet. Just wait.

    → Reply
    • »
      »
      »
      23 months ago, # ^ |
        Vote: I like it +2 Vote: I do not like it

      That's too slow. Why not start the system test?

      → Reply
    • »
      »
      »
      23 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      I remember system testing used to be wayyyy faster. Now they delay it so much for each contest

      → Reply
      • »
        »
        »
        »
        23 months ago, # ^ |
          Vote: I like it +1 Vote: I do not like it

        That's true. I don't understand why system test has been delayed for so long either.

        → Reply
»
23 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Hi! Can anyone explain what's wrong with this solution for D? I've got Time Limit on the Test 27.

Count a frequency of every doll's size (current size = k). Iterate through doll's sizes and check there is doll with size less by 1 (k-1). If there is no, then it's start of new sequences. If it is, then we can use dolls with size k in a new sequence only if frequency of k is more then frequency of k-1

def main():
	t = int(input())

	for _ in range(t):
		res = alg()
		print(res)

def alg():
	n = int(input())
	aDict = dict()
	res = 0

	for i in input().split():
		i = int(i)
		
		if not i in aDict:
			aDict[i] = 0
		
		aDict[i] += 1

	for k in aDict:
		if k - 1 in aDict:
			res += max(0, aDict[k] - aDict[k - 1])
		else:
			res += aDict[k]

	return res

if __name__ == '__main__':
	main()
→ Reply
  • »
    »
    23 months ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    Hi! The code similar to yours in C++ also receives the verdict TL (on test 28) — 190976286. However, if you replace the unordered_map data structure with just a map, the solution gets OK — 190976343. This is due to the implementation of these classes "under the hood":

    unordered_map is a hash table. The standard Python dictionary uses it. On average, the asymptotic behavior of each operation is O(1), but in the amortized worst case (when a hash collision occurs) this will be O(n). On large tests according to the paradox of birthdays collisions will occur quite often.

    map is a red-black tree. Even in the worst case, the main operations are performed in O(logn). On average, it works slower than a hash table, however, due to not the best standard hash functions, I recommend using map.

    So, you should implement the red-black tree yourself, or switch to C++ to explicitly choose which data structure to use.

    → Reply
»
23 months ago, # |
  Vote: I like it 0 Vote: I do not like it

(a^b)+2*(a&b)=a+b Where did everyone get this formula from, how does it work out. Explain, thank you.

→ Reply
  • »
    »
    23 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    https://stackoverflow.com/questions/4068033/add-two-integers-using-only-bitwise-operators

    → Reply
  • »
    »
    23 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Think about the sum of two numbers a and b, and let's focus more on the ith bit.
    x[i] = 0 if the ith bit of the binary representation of x is 0 else x[i] = 1

    if a[i] & b[i] = 0 then (a[i] + b[i]) = (a[i] ^ b[i])
    else a[i] + b[i] = (a[i] ^ b[i]) + (1 << (i + 1)) because you should carry one extra bit to the right.
    and (1 << (i + 1)) = 2 * (1 << i)
    so a[i] + b[i] = (a[i] ^ b[i]) + 2*(a[i] & b[i])

    → Reply
  • »
    »
    23 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    it's just addition of bits that is only one of numbers and those that are in two of them

    → Reply
»
23 months ago, # |
  Vote: I like it +9 Vote: I do not like it

When will the ratings update

→ Reply
»
23 months ago, # |
  Vote: I like it +9 Vote: I do not like it

Why the rating isn't update yet?

thanks!

→ Reply
  • »
    »
    23 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    The rating is usually updated a little longer after the educational rounds. You should get used to it.

    → Reply
»
23 months ago, # |
  Vote: I like it +6 Vote: I do not like it

SpeedForces during contests, SlowForces during rating updates.

→ Reply
»
23 months ago, # |
  Vote: I like it +1 Vote: I do not like it

Finally, the system testing has started! @_@

→ Reply
  • »
    »
    23 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Too bad it will be finished only in 4 hours

    → Reply
»
23 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Has the official rating been published? My rating didn't change..So, I don't know if I have improved or not...

→ Reply
  • »
    »
    23 months ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    The official rating hasn't been published yet. If you want to predict your rating delta you can use cf predictor

    → Reply
»
23 months ago, # |
  Vote: I like it 0 Vote: I do not like it

How my code is giving Time Limit Exceeded?? Can anyone explain alwyn csegura Darko Submission->190829557

include <bits/stdc++.h>

using namespace std;

define ll long long

int main() { int t; cin >> t; while (t--) { int n; cin >> n; int a[n + 1]; ll int ans = 0; unordered_map<int, int> m; vector v; a[0] = -1; for (int i = 1; i <= n; i++) { cin >> a[i]; // cout<<a[i]; if (m[a[i]] == 0) { v.push_back(a[i]); } m[a[i]]++; } sort(v.begin(), v.end()); int smallest = v[0]; for (int i = 0; i < v.size(); i++) { if (i == 0) { ans += m[v[i]]; smallest = v[i]; continue; } if (v[i] == smallest + 1) { // cout<<smallest+1<<endl; if (m[v[i]] == m[smallest]) { smallest = v[i]; } else { if (m[v[i]] > m[smallest]) { int mini = min(m[smallest], m[v[i]]); ans += max(m[smallest], m[v[i]]) — mini; }

smallest = v[i];
            }
        }
        else
        {
            ans += m[v[i]];
            smallest = v[i];
        }
    }
    cout << ans << endl;
}

}

→ Reply
  • »
    »
    23 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Probably because of collisions in unordered_map<>. Try doing the same thing with map<> or use custom hash with unordered_map<>

    → Reply
    • »
      »
      »
      23 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      But it is not my fault!!

      → Reply
      • »
        »
        »
        »
        23 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        It actually is. You chose to use unordered_map instead of map, while it's well known that unordered_map might cause collisions, resulting in O(1) average, but O(n) worst.

        → Reply
        • »
          »
          »
          »
          »
          23 months ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          I don't think so, It's my problem,It is default Things,This type of solutions must be Accepted.

          → Reply
          • »
            »
            »
            »
            »
            »
            23 months ago, # ^ |
              Vote: I like it +5 Vote: I do not like it

            It's not about solutions. It's like unordered_map being slow, therefore not passing time limit. Solving those problems isn't the hard part of them. Solving them EFFICIENTLY is. Therefore, you are required to solve them efficiently, or forced, I should say.

            Yeah, it's definitely sad to fail your solution in that way, but it's a good 'lesson' which you will know the next time you encounter it. That's why we do CP, to learn.

            → Reply
»
23 months ago, # |
  Vote: I like it 0 Vote: I do not like it

when the new ratings will happen

→ Reply
»
23 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Is there an error in the system testing? My solution was accepted during contest (accidentally submitted in python instead of pypy), yet TLE in the system testing. Test case 26 on 200,000 length array runs in 300ms, but then saying same length array runs over 2000ms for test case 27? Unable to replicate an inflation factor of 6x on my local computer with big numbers.

https://mirror.codeforces.com/contest/1790/submission/190800700

→ Reply
»
23 months ago, # |
  Vote: I like it -21 Vote: I do not like it

Attention!

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

Clearly we all used prewritten Centroid Decomposition code taken from https://robert1003.github.io/2020/01/16/centroid-decomposition.html and we were flagged incorrectly.

MikeMirzayanov

→ Reply
  • »
    »
    23 months ago, # ^ |
    ← Rev. 2   Vote: I like it +11 Vote: I do not like it

    Firstly, the message to you contains precise instructions on where to write about such issues. Why are you breaking it?

    Secondly, can you clarify any reason why the main parts (not CD code) in all solutions are the same?

    → Reply
    • »
      »
      »
      23 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it
      • About main function part is similar:
              cin >> n >> f;
        cd.init(n);
        vector <int> lists;
        for (int i = 1; i < n; i++){
            int x;
            cin >> x;
            lists.push_back(x);
        }
        for (int i = 1; i < n; i++){
            int a, b;
            cin >> a >> b;
            cd.addEdge(a, b);
        }

      The above is the basic part to get the input, so it is difficult to avoid it being the same.

      cd.build(1, 0);
cd.modify(c);
      • For this part, it is the part already written in the sample code in the blog above
      int ans = 1e8;
for (auto i: lists){
     ans = min(ans, cd.query(i));
     cout << ans << " ";
     cd.modify(i);
}

      And the last part is because the topic says, I just do it.

      ** Change the color of a vertex and get the minimum distance from that vertex to one of the given vertices (must calculate the distance first because if we change the color first, it will be wrong)

      → Reply
    • »
      »
      »
      23 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      The main part is so simple that it is hard to avoid having similar code. It's just reading input and processing queries. Plus our code for other problems is completely different.

      → Reply
»
23 months ago, # |
  Vote: I like it 0 Vote: I do not like it

First of all, I apologize for my bad English. Then after completing the Codeforces Round #847 (Div. 3) contest, I received the following message:

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

  • I used the Centroid Decomposition code from this blog — a well known algorithm website in my country, and this blog.

  • About main function part is similar:

        cin >> n >> f;
        cd.init(n);
        vector <int> lists;
        for (int i = 1; i < n; i++){
            int x;
            cin >> x;
            lists.push_back(x);
        }
        for (int i = 1; i < n; i++){
            int a, b;
            cin >> a >> b;
            cd.addEdge(a, b);
        }

The above is the basic part to get the input, so it is difficult to avoid it being the same.

cd.build(1, 0);
cd.modify(c);
  • For this part, it is the part already written in the sample code in the blog above
int ans = 1e8;
for (auto i: lists){
     ans = min(ans, cd.query(i));
     cout << ans << " ";
     cd.modify(i);
}

And the last part is because the topic says, I just do it. "Change the color of a vertex and get the minimum distance from that vertex to one of the given vertices" (must calculate the distance first because if we change the color first, it will be wrong)

→ Reply
»
23 months ago, # |
← Rev. 2   Vote: I like it +1 Vote: I do not like it

When will the ratings be updated?

→ Reply
»
23 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Bruh in D i used unordered map during the contest and it gave TLE after the contest on test 28 but when I changed unordered map to map it gave passed all test cases!!

→ Reply
  • »
    »
    23 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    that's something you should have known. unordered_map is always be hacked.

    → Reply
»
23 months ago, # |
  Vote: I like it 0 Vote: I do not like it

has the round been declared as unrated??

this was the first time I turned green :(

but am back to newbie now

→ Reply
  • »
    »
    23 months ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    There is a small chance that contest became unrated due to E problem.

    → Reply
»
23 months ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

there is some thing i can't understand, i'm coding in java and in problem d i was been hacked on it, solution was o(n) and same solution in c++ didn't face any matters , and it wasn't first time i face that..

→ Reply
»
22 months ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

How come the tutorial solution for problem F gives TLE ? https://mirror.codeforces.com/contest/1790/submission/194017127

→ Reply