Vladosiya's blog

By Vladosiya, history, 3 weeks ago, translation, In English

Hello! Codeforces Round #787 (Div. 3) will start at May/05/2022 17:35 (Moscow time). You will be offered 6-7 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 ACM-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-7 problems and 2 hours and 15 minutes to solve them.

Note that the penalty for the wrong submission in this round (and the following Div. 3 rounds) 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 teams: MikeMirzayanov, MisterGu, myav, Gol_D, Aris, SixtyWithoutExam, me Vladosiya.

Also many thanks to avevad, yorky, UncleSema, vsinitsynav, GoracioNewport, Tvorozh0k, any_nickname, I.AM.THE.WILL and Jostic11 for testing the contest and valuable feedback.

Good luck!

UPD:Editorial

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

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

Best of luck, everyone!

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

Hope the pretests are stronger in this one.

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

    Can you explain what happens if pretests are weak? I'm new in Codeforces and exploring the rules.

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

      Test cases which are used to check your solution during contest are pretests; subset of the actual test cases.So sometimes it happens that the solution pass the pretests but it's actually wrong.

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

      Because there are too many hacks in codeforces round 786,especially problem E

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

Good luck to every one!

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

As it is written by link

Well, the "Remember" hasn't been written by link yet :)

UPD: Thanks, it is updated.

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

Hoping that everyone does great and everyone gets a positive delta in this contest. All the best everyone!!!!!!

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

Any fool can write code that a computer can understand. Good programmers write code that humans can understand.

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

    Such as me,and I hope all the young coders will get a good mark in this contest and be benifited.And best luck to all the coders!

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

Hope I reach candidate master after this round!****

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

    Good one dud. But if you are serious, try AKing a Div2 round or smth because it is virtually impossible to go from pupil to CM in one Div3 round.

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

Excited for my 2nd contest

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

never give any contest for increasing your rating. Just give it to learn something new, and rating will definitely increase sometime!

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

    Yeah,participating in contests isn't just to increase your rating.What you must do is to learn more in the contsets,be honest,no cheating,and try your best!

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

Hoping to reach Pupil!

Marinush

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

Experiencing two consecutive Div 3 rounds for the very first time ❤️

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

I have a question, before the contest div 3 before rated, i had been a specialist, and i register at this contest, so they said that i will be rated, but after the contest div 3 before rated, i am a expert, and they( codeforces) said that i was trusted participant in contest (dont have asterisk before name in register in this contest ), so I will be rated or unrated? Thank you.

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

I hope the contest be good like the latest one yesterday

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

Good luck and have fun guys!

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

Pray for downvote

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

As a tester, I wish all the beginners good luck!

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

Hope I reach Radiant this round

»
3 weeks ago, # |
  Vote: I like it -26 Vote: I do not like it

Hello MikeMirzayanov,BledDest,vovuh,adedalic.System

I find out some plagiarism activity in Codeforces Round #786 (Div. 3).

Please check out submissions of problem 1674B - Dictionary,submissions are 155621247 and 155678427 They both have same function with same variable but just comment down it and wrote it again with some variable change. Please look out at it.

Proofs given below and also you can check submissions...

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it
Old But Gold
»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

good luck by the way has anyone Upgradeed to win11

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

I am excited about this round to be easy as the last Div 3 round. ♥

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

what is difficulty distribution for problms

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

    It's score distribution, not difficulty. Also, Div3 rounds do not have score distribution.

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

Hope everyone gets a good rank.

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

hoping to solve till/after D. solved only till C in previous Div3, could solve D, coz of spelling mistake

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

Excited to be slapped with some awesome concepts and learnings. Thankyou guys already for helping me in my path to specialist.

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

Excited to enjoy this round on my birthday! :)

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

That was an amazing contest! Thanks for the awesome problems!

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

good problems. Confused in E for half an hour. F and G are good educational problems.

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

Was thinking on problem B for more than 40 mins and after a bunch of unsuccessful attempts using math it comes to be solvable bruteforcely :) A hilarious thing to make it so and i guess i have to remember sometimes that it is just div3 (even tho i'm 1100 still).

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

    how did you solve it it's giving me TLE and I don't know why

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

      its infinite loop because you don't break when the element equals to 0 and keep divide by 2

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

        try this 3 2 2 2

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

          working gives 3

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

            oh sorry i didn't try it in my ide but try this 3 3 0 0 0 first line is number of test cases + there is another bug in your code the loop should start from n — 2 not from n — 1 since you don't need to do anything for the last element edit : just realis you use 1 based index ignore the last line

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

I really enjoyed solving G. Great problems, very educational

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

i'm trying to understand task c in 1hr still not able to understand what they trying to say (maybe my english is weak)

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

    ?1?? This Tc give 3 I get this 45 min before end of the contest.

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

Did anyone solve F in Python? Keep getting TLE with python and MLE with pypy.

For future reference, here is a solution that is accepted in both python 3 and pypy 3 (surprisingly, about 2x slower in pypy): https://codeforces.com/contest/1675/submission/156014304

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

G is O(N*M^3) with very small constant factor?

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

    My solution was $$$O(nm^2)$$$

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

      I use dp[total number][last number] as status. How to improve?

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

        Convert the array $$$a$$$ into array $$$b$$$ where $$$a_i$$$ is the frequency of $$$i$$$. Then, the dp state should be (current_index, number of sections, length of section ending in the current_index). Submission (sorry for the bad explanation, hope you can understand from my code)

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

        Let $$$p[i][x][y]$$$ be the minimum of $$$dp[i][x][1]$$$ to $$$dp[i][x][y]$$$, and $$$pa$$$ be the prefix sum of $$$a$$$.

        Then $$$dp[i][x][y] = p[i-1][x-y][y]+abs(pa[i]-y)$$$.

        Note that $$$y$$$ is not greater than $$$n/i$$$ when enumerating, so the final time complexity is $$$O(nm\log(m))$$$.

        Here is my code: 156012337

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

          I guess I implicitly used the n/i condition so it is reduced to O(NM^2logM) at least.

          • »
            »
            »
            »
            »
            »
            2 weeks ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            I had an idea to do, like reverse the then problem will turn into minimum operations to make a non decreasing array then apply slope trick Optimization.. something like that. Is it possible ?

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

My approach for F: Vlad and Unfinished Business

We need to travel from $$$src$$$ to $$$target$$$. Root the tree at $$$src$$$. The path from $$$src$$$ to $$$target$$$ is now a vertical path. Call a node infected if we need to compulsorily visit it during our journey. Initially, the only infected nodes are $$$src$$$, $$$target$$$, and the given $$$k$$$ vertices.

Notice that if a node is infected, its parent would also be infected (since we cannot visit it without visiting its parent). Hence, we can propagate infection up the tree via a simple DFS.

To compute the answer, notice that any edge between 2 infected nodes would have to be traveled exactly twice. (One while going from parent to children, and the other while coming back). Hence, the answer is

2*(Count of edges where both endpoints are infected)

However, we do not need to travel back to $$$src$$$ from $$$target$$$. Therefore, we need to subtract the depth of $$$target$$$ from our answer.

Code

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

There is a bug. My solution to A was accepted, but it's missing in the standings.

UPD: fixed, thanks

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

I had a hard time understanding problem D

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

how to solve G

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

    a common idea in problems where you increase $$$a[i]$$$ at the cost of $$$a[i+1]$$$ or $$$a[i-1]$$$ is to consider prefix sums/suffix sums.

    in this problem, consider the prefix sum array $$$pref[]$$$. Each move of type $$$a[i+1]$$$ to $$$a[i]$$$ increases $$$pref[i]$$$ by $$$1$$$, and leaves all other values unchanged. Similarly, $$$a[i]$$$ to $$$a[i+1]$$$ decreases $$$pref[i]$$$ by $$$1$$$ and leaves everything else unchanged.

    Converse is also true: every increase/decrease of $$$pref[i]$$$ corresponds to some move in the original array. [for $$$i<n$$$ , since $$$pref[n]$$$ remains same].

    So problem is transformed to one operation which increments or decrements an index of the prefix array. Then you get the necessary and sufficient condition

    $$$C$$$: $$$a[i] \geq a[i+1] \iff pref[i] \geq 2*pref[i-1]-pref[i-2]$$$.

    Then you can define $$$dp[j][j1][j2]$$$ to be the minimal cost to convert $$$pref[1...j]$$$ so that $$$pref[j]==j1$$$ and $$$pref[j-1]==j2$$$, then you can figure out the states using condition $$$C$$$.

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

      Oh I got it. Thanks

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

      ah, I saw a problem recently that used this idea. Still, I couldn't remember it during the contest. Explains why I am still blue :(

    • »
      »
      »
      2 weeks ago, # ^ |
        Vote: I like it +4 Vote: I do not like it

      Thanks for the great explanation!

      I wrote this piece of code based on your explanation and got ac. However, I can't convince myself that it fits within the time limit. Here's the dp part of my code:

      Code

      At first glance, the time complexity looks like $$$O(NM^3)$$$, but considering the fact that it managed to pass the time limit comfortably at 46ms, I doubt if this is the actual time complexity. Could you please help me figure out the time complexity of my code (and also prove it)?

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

Can someone please explain why I am getting TLE in problem B? This is my code- https://replit.com/@StephenV1/TrickyComfortableLanguage#main.cpp

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

What problem C was all about:

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

problem c is really hard and it can solved by logic principles only!!

  • »
    »
    2 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    It seemed hard but it was a fun question to think of. So I was stuck to it and solved it.

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

Can someone please explain how to solve E ? Only thing I figured out was in total at most 26 moves every char in string can be converted to 'a'. So, k>26 will always yields aaa...a which is the smallest lexicographical string ( Correct me if I am wrong )

  • »
    »
    3 weeks ago, # ^ |
    Rev. 2   Vote: I like it +1 Vote: I do not like it

    your observation is correct. You just have to go from s(0) to s(n-1) in order and converting characters to lowest possible conversion at that point, you just have to maintain an array of size 26 to check how many characters you have already converted

    you can check one of the way in my solution :

    • »
      »
      »
      2 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Can you please explain the main logic. I mean the lowest possible conversion at that point means what ? Third part I understood that like if suppose 7th char was 's' and we did the calculation for it's conversion then if we get 20th or any further char again 's' then we will simply ignore that since 's' calculation is already done

      • »
        »
        »
        »
        2 weeks ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        suppose n = 5, k = 4, string = cgdfb,

        c -> a

        g -> e (thats the best conversion for this stage)

        d -> d(there is no conversion possible as k is used up)

        f -> e

        b -> a

        thats what i meant if k was 6 you could convert g -> c -> a

        • »
          »
          »
          »
          »
          2 weeks ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          Thanks, I understood now..I have to use already converted char value afterwards also..like if string is "ek" then ( e-> a in 4 moves & k->e in 6 moves & we already have e->a before so we will ignore this so total 10 moves for "ek" to "aa"...)..Thanks :)

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

Idk how the heck C has 7000 solves . Believe me D and E are a lot easier than C.

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

    cheaters?

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

      I don't think so, maybe we are missing out on something easy observation.

      • »
        »
        »
        »
        2 weeks ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        I solved A-E, and short 10 minutes to submit F. This contest is harder than previous div3, but judging from the number of AC submission, I'm sure there are a tons of cheaters.

        • »
          »
          »
          »
          »
          2 weeks ago, # ^ |
            Vote: I like it +6 Vote: I do not like it

          Exactly . There is no way 7000 ppl would solve C and only 2500 solves on E. It's all because of cheaters.

          • »
            »
            »
            »
            »
            »
            2 weeks ago, # ^ |
              Vote: I like it +7 Vote: I do not like it

            C has fairly simple observations. There is a prefix of 1s, a postfix of 0s.

            So the thief is between (including both) the last 1 and the first 0.

        • »
          »
          »
          »
          »
          2 weeks ago, # ^ |
            Vote: I like it +4 Vote: I do not like it

          I don't think the contest was tough,
          Problem A : Implementation
          Problem B : Start from back
          Problem C: prefix should not have any '0' and suffix should not have any '1'
          Problem D: Basic dfs
          Problem E: Just do whatever is written, decrease current character as much as you can Problem F: I have seen these types of problems many times, fix the root and then every required edge will be visited twice except between the path from x to y (So, basically again a normal dfs with some basic dp involved)
          Problem G: It involved a nice DP, but it's fine, the last problem can be on the tougher side.

          Problems were of the same level as of a normal Div3 contest.

        • »
          »
          »
          »
          »
          2 weeks ago, # ^ |
          Rev. 2   Vote: I like it +8 Vote: I do not like it

          I didn't mean the questions were tough. I meant it should have smaller ACs compared to previous Div3. Also recently there are people who uploaded solution on YT mid contests. I don't see why it wouldn't happen again.

  • »
    »
    2 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    true! lol , I spent around like 40 min on this question but still didn't get how the test cases are working , so I solved A , B , D , E

  • »
    »
    2 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Problem D implementation was difficult. But the idea was simple.

    Problem C implementation was super easy. But getting the idea was very tough.

    • »
      »
      »
      2 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Can you explain your idea for problem D. I was getting TLE

      • »
        »
        »
        »
        2 weeks ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Steps:

        • Find the Leaf nodes
        Hint
        • Create a map to store the parent nodes of each of these leaf nodes.
        • For each of these leaf nodes, put it's parents in the map
          • Starting from the leaf node, navigate till the parent (using DFS), and store the list of integers
          • Make sure that you don't add already visited values (as it is mentioned that each vertex belongs to exactly one path)
        • Loop through all these items in this map, and print the parent nodes in reverse order. We are reversing this because, it is mentioned that paths always lead down.

        My Submission — 155988440

        There could be some other simpler solution. If anyone else can comment on this thread, on how this can be improved, that would be great.

      • »
        »
        »
        »
        2 weeks ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        determine the root vertex first. it's easy, because it's the only one vertex with a[i] = i. then run dfs from the root and start writing the path to an array, and we end the path if and only if we came to the leaf node (there is no way to continue it). So, we return current path to the main function and do same thing again unless all vertices are visited. sorry for my poor english :P

        Here is the implementation

        https://codeforces.com/contest/1675/submission/156019404

  • »
    »
    2 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    answer is pretty simple, I think most people guessed it right instead of knowing how it passed

  • »
    »
    2 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    solved C in 10 min and didn't try to solve D banging my head hard on B all the time thinking it shouldn't be that tough and finally solved only 2 :( I even tried solving in O(n) but turns out brute force will work just with few corner cases

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

My idea for F — Find the path from x to y. Let the path array be composed of nodes u1, u2, u3 ... ul, where u1 = x and ul = y. Then for every u, do a BFS considering u as the root, and store the distances in a array dis. Then the answer is length of path + 2*(sum of all distances of mentioned k nodes). But it got WA on test 2. Am I missing something?

Submission

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

jiangly's code is so concise!

»
2 weeks ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

can anyone please explain question E in simple English and explain the third test case? Please don't give any hint about the answer.

  • »
    »
    2 weeks ago, # ^ |
      Vote: I like it +4 Vote: I do not like it

    I am not sure if I can explain better than the problem description.

    We have to make the given string lexicographically minimum, by performing the given operation maximum k times.

    Operation: Choose any character in the String, and replace all of it by the previous character.

    For example, replace all 'c' with 'b' or replace all 'a' with 'z'.

    For String cba with k=2, we can perform 2 operations as below. cba -> bba -> aaa

    Note: Checking the test case below might be considered as a HINT.

    3rd Test Case steps
»
2 weeks ago, # |
  Vote: I like it +15 Vote: I do not like it

Thank you for the contest!

I especially liked problem C for the setting and problem F for key insight.

  • »
    »
    2 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Can you please explain to me the test cases for C, I couldn't even understand how the test cases are working! May be I am getting something seriously wrong on this problem, for test case -> ? ? 0 ? ? how the answer is 3? Should it not be 5?

    • »
      »
      »
      2 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      first and second one maybe the theif third one as well but the fourth and fifth can't be since the painting was already missed when the third one reported if he tell the truth and if its wasn't missed that means third one is the theif and also fourth and fifth one can't be the theif sorry for my bad english

    • »
      »
      »
      2 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      3rd person says that there is no picture in the room. so the only possible thieves will be 1st,2nd, and 3rd one

    • »
      »
      »
      2 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      ? ? 0 ? ?

      • We only have information from the third person
      • Either someone stole the painting before they entered the room (0), or they are the thief (and are lying).
      • Therefore the thief must be one the first 3 people
      • »
        »
        »
        »
        2 weeks ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        oh yeah, that's right once 0 is said it means that he is either lying or telling the truth. So overall I just have to check before how many '?' marks I have until 1 appears. Now this '1' can also be a victim so we have to include '1' too! This problem was nice! Thanks man!

    • »
      »
      »
      2 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      If friend 3 was the thief and lying, the painting was definitely taken then so it would not be there for 4 or 5. If friend 3 was honest, the painting was taken by friend 1 or 2 (it had already been taken) so it was definitely taken before 4 or 5 came.

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

        yep! I messed up my contest for this 1 problem :p though its a nice one!

    • »
      »
      »
      2 weeks ago, # ^ |
        Vote: I like it +12 Vote: I do not like it

      Apart from the existing comments, let me try to explain how I interpreted this problem C for Testcase ? ? 0 ? ?. May be it helps someone.

      • If 1st person is thief :

        • persons 2,4,5 can't remember — so, no issues
        • person 3 didn't see the picture — which is true
        • VALID
      • If 2nd person is thief :

        • persons 4,5 can't remember — so, no issues
        • person 3 didn't see the picture — which is true
        • VALID
      • If 3rd person is thief :

        • person 1,2,4,5 can't remember — so, no issues
        • VALID
      • If 4th person is thief :

        • person 1,2,5 can't remember — so, no issues
        • person 3 didn't see the picture — which becomes a false statement
        • which makes that 4th person is not the thief. So, INVALID.
      • If 5th person is thief :

        • person 1,2,4 can't remember — so, no issues
        • person 3 didn't see the picture — which becomes a false statement
        • which makes that 5th person is not the thief. So, INVALID.
  • »
    »
    2 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    will you please share the approach to the problem F

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

      My approach is as follows.

      Consider a rooted tree with root in $$$x$$$. Let important vertices be the ones that we will have to visit. First, mark the input vertices as important, and also the vertex $$$y$$$. Now, a vertex is important if it is marked or at least one of its children is important. This characteristic can be found recursively with a single DFS.

      So, we got a subtree $$$T$$$ of the original tree: we have to visit every vertex of $$$T$$$, and don't have to go anywhere else. Now, think what would we do if we had to return to $$$x$$$ in the end. Naturally, we would traverse each of the edges of $$$T$$$ exactly twice: once going from the root and the second time going back.

      Remember now that we don't have to return to $$$x$$$, just end up at $$$y$$$. Naturally, we will consider a path that ends up moving from $$$y$$$ to $$$x$$$, and then omit that last part. The number of steps is therefore twice the number of edges in $$$T$$$ minus the distance from $$$x$$$ to $$$y$$$.


      To me, the beauty of the problem is that some parts above can be omitted, leading to more and more tedious (but still quite working) solutions. So, the participant has a choice to either start implementing what they have, or ponder more to maybe cut out quite a bit of work. If a solution needed all of the above to pass at all, that beauty would have been lost.

  • »
    »
    2 weeks ago, # ^ |
      Vote: I like it +12 Vote: I do not like it

    Me after solving C

    Spoiler
»
2 weeks ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

Can anybody explain why so many RE on test case 7 in problem D with Python? My submission: https://codeforces.com/contest/1675/submission/155950425

  • »
    »
    2 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Probably running out of stack due to recursion? Test 7 appears to be a single path with every node on it.

    • »
      »
      »
      2 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      I thought so too, but here is my submission with increased recursion limit, but got the same. https://codeforces.com/contest/1675/submission/155959621

      • »
        »
        »
        »
        2 weeks ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        That just stops python giving a recursion limit error, you can still run out of memory and crash.

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

          "you can still run out of memory and crash"

          That yields a "Memory Limit Exceeded" (e.g.): https://codeforces.com/contest/1675/submission/155991461

          Which is different from the "Runtime Error" in the submission shared by khanter_

          • »
            »
            »
            »
            »
            »
            2 weeks ago, # ^ |
              Vote: I like it +4 Vote: I do not like it

            This works: https://codeforces.com/contest/1675/submission/156020448

            I added a generator function called bootstrap. This takes a recursion and processes it as a stack instead. It's extremely useful in python for large N recursion problems. I use C++ now but when I used python I always used bootstrap for recursion and strongly advise you to do the same.

            • »
              »
              »
              »
              »
              »
              »
              2 weeks ago, # ^ |
                Vote: I like it 0 Vote: I do not like it

              Got it, thanks a lot!

            • »
              »
              »
              »
              »
              »
              »
              2 weeks ago, # ^ |
                Vote: I like it 0 Vote: I do not like it

              I use only setrecursionlimit(300005), it got runtime error.

              I use setrecursionlimit(300005) and bootstrap, it got MLE.

              I use bootstrap only, it got AC.

              Can I conclude that one needs bootstrap ONLY for recursion/dfs problems?

              Thanks for sharing this tip!

              • »
                »
                »
                »
                »
                »
                »
                »
                2 weeks ago, # ^ |
                  Vote: I like it 0 Vote: I do not like it

                I’m not sure. Perhaps just the act of setting the stack limit that high occupies too much memory. In any case, when I used python (see all my submissions pre May 2021) I only ever used bootstrap and it was always fine.

»
2 weeks ago, # |
  Vote: I like it +1 Vote: I do not like it

when will be the editorial available?

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

I see some people cant get the logic of C so probably my approach will be useful: first of all i loop through the whole string and count a total number of occurrences of '0' and '1' in a string (separately for each).

Then i start a second loop and in that loop i also count a number of occurrences of '0' and '1' till i-th element. The first thing we need to see that only the last '1' can be a thief (because for any earlier '1' the will be a '1' later, which confirms that a painting cant be stolen earlier). The same goes for '0', but only the first '0' can be a thief (because for any further '0' there will be a '0' earlier, which says that a painting has already been seen to be stolen before).

Now we move to '?'. Here we had to see that '?' can be a thief only if all '0' are on the right side from '?' and all '1' are on the left side of '?'. The logic is pretty straight-forward: if there is a '0' on the left then the painting was already confirmed to be stolen (which cant happen because its being stolen on '?' only). The same we can see for '1': if there is a one '1' on the right then a painting will be confirmed to be seen (which cant happen because the painting has already been stolen on '?').

You can find my code here: 155985751.

I hope I could help somebody out by doing this, have a great one and see you all tomorrow!

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

Here are video solutions (for D-F)

»
2 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

In Problem C , if before 0 any ? occurs why he/she won't be considered as Theif ??

  • »
    »
    2 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Depends on what else we have before and after '0'. Give more detailed information/sample, please

  • »
    »
    2 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Before 0, if any ? occurs, he/she will be considered as Thief.

    Anything after 0 is only not considered as thief.

    Answer for ???????000 is 8. (Only last 2 person can't be considered a thief)

    I have tried to explain that in this comment — here.

    • »
      »
      »
      2 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      If you speak about '?' considering a thief you have to keep in mind what you have on both sides too. There might be some '1' in between or '0' before '?' that break the logic

      • »
        »
        »
        »
        2 weeks ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Yes. Got it.

        But, I was just trying to reply to that comment which was specific to the string that has a 0, and has ?s before it.

        If we have to consider all scenarios, then:

        Full logic for Problem C.
»
2 weeks ago, # |
  Vote: I like it +3 Vote: I do not like it

The statement of Problem C is a masterpiece.

It was the best text I've read this year.

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

Problem C, after you simplify the problem, it is only:

Set counter = 0

3 Cases:

  1. It is a '?' increment counter

  2. it is a 0, return counter + 1

  3. it is a 1, reset the counter to 1.

»
2 weeks ago, # |
  Vote: I like it -8 Vote: I do not like it
»
2 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Problem C becomes simple if you think it like this: Suppose the ith person is a thief, then from [i+1 to N], there would be no painting present in room, and from [1,i-1], there would be painting present, also every person apart from ith one must be telling the truth, so prefix[i-1] can only have 1's or ? and suffix[i+1] can only have ? and 0's.

»
2 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

well, i'm stuck with E again.

how can i find some problems like this and make some improvement, seems like something between greedy and dp.

want to become blue

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

    I have seen such hard greedy always in Div.3, but rarely in Div.2.

    Also, such problems are common on CodeChef, specially in Starters round.

    You can try Div3s on codeforces or give codechef

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

    Bruh you will make it. Don't worry it's not that tough. You just need one good round

»
2 weeks ago, # |
  Vote: I like it +1 Vote: I do not like it

Twice in a row that Geothermal FST in div3 contest.

»
2 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

So i am dealing with a problem regarding problem B-Make it increasing.

In first two try I applied the logic that a[n-i]/pow(2, n) <a[i] and so I solved it by taking log in both sides and thus finding value of n and adding it to the answer for all i from n-1 to 1. I used a online ide and in many ide my answer for the 6th test case was coming 11 but in codeforces it is giving 10. Please guide me coz i couldnt find where my logic breaks.Though i later solved it using two loops but I suppose using log will save a lot of time in case of larger arrays. I am attaching the code below. Thanking you all.

    bool ans=true;
    int count=0;
    for(int i=n-1; i>0; i--){
        if(arr[i]==0){
            cout<<-1<<"\n";
            ans=false;
            break;
        }
        if(arr[i]>arr[i-1]){
            continue;
        }
        else{

            int p=(log(arr[i-1]/arr[i])/log(2)) + 1;
            count+=p;
            arr[i-1]=arr[i-1]/pow(2, p);
        }
    }
    if(ans) cout<<count<<"\n";
  • »
    »
    2 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    You should avoid using log and pow functions as long as you can find other ways, as they might have precision issues. Here instead of using log to calculate p, you can instead run a while loop and keep dividing a[i-1] by 2 till it is greater than or equal to a[i] and greater than 0 as well.

»
2 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Falsely accused of cheating for problem B. It is a simple greedy problem. Many users have written the same solution but in a different way. It is a pure coincidence that my solution matches with guoziyue and i don't even know him/her. MikeMirzayanov I have given over 80 contests and have never cheated in any of them so please look into the matter and I didn't even use ideone.So, its a pure coincidence.

»
2 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Hey all, I have a question. For problems such as problem E, how to efficiently create an unordered_map of <character, position of character in alphabet>. For example name this unordered_map alphs: alphs['a'] = 1; alphs['b'] =2.. alphs['z'] = 26;

Note: by 'efficiently' i mean without copy pasting 26 lines and assigning each value one by one. i.e. create without typing too much or using few lines of code.

  • »
    »
    2 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    i am not sure if i am totally understand what u want but you can map the character to its position as follow: character = character — 'a' + 1 you don't even need an unordered_map (maybe im wrong) but if you for some reason want it here we go:

    Spoiler
    • »
      »
      »
      2 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      If I am understanding correctly, are you using the ASCII values of characters to find out the positions in alphabet? For example, ascii value of 'a' is 65. and ascii value of j = 74. so to find out position of 'j' in alphabet, i take ascii value of 'j', then minus the ascii value of 'a', then add 1. i.e. 74-65+1 = 10. Is that what you are doing. Also am i correct in understanding that that is what automatically happens in c++ when adding or taking away a character from an integer?

      • »
        »
        »
        »
        2 weeks ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        thats true when you do operations on characters it uses its asci which means 'a' — 1 is equiv to 65 — 1 which equals 64 similarly the formuala ch — 'a' + 1 is equivlant to subtract 65 (a) from the asci of the character which gives us the position of the character in the alphabet and we adding one because you want to count from 1 not 0 you can view it in another way: 'a' — 'a' + 1 = 1 'b' — 'a' + 1 = 66 — 65 + 1 = 2 and so on

»
2 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Thanks for round (210 on my way to 1800) !

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

In the constest Codeforces Round #787 (Div. 3) Problem D (1675D) My submition is (Juliano1 / 155992661)

The code framework I submitted comes from "算法笔记 上级训练实战指南",a algorithm guidebook published in China in 2021 (ISBN 978-7-111-54040-3)

the frame comes from pages 294 ~ 295 // 层序遍历 (traversal) (I will attach pictures at the end of the comments), just replace the "queue" in the framework with "stack" and at the end of the frame The binary tree PUSH operation is replaced with a PUSH operation of the common tree. The frame code is as follows:

void BFS(int root){ queue q; q.push(root); while(!q.empty()){ int now = q.front(); q.pop(); print(now); if(Node[now].lchild !=-1)q.push(Node[now].lchild); if(Node[now].rchild !=-1)q.push(Node[now].rchild); } }

and here is my code:

void dfs(int root, vector p) { stack s; s.push(root); int cnt = 0; int index = 0; while (!s.empty()) { int now = s.top(); s.pop(); cnt++; ans[index].push_back(now); if (p[now].son.empty()) { ans_len.push_back(cnt); cnt = 0; index++; } else for (int i = 0; i < p[now].son.size(); i++) s.push(p[now].son[i]); } }

It can ensure that my code does NOT HAVE CHEATING in the contest. The same part as other contestants is due to the use of similar templates PUBLISHED BEFORE THE CONTEST, so I apply for restoration of my results.

pictures:

»
2 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

sorry but it was a coincidence, i have used ideone in public mode by mistake because i don't have idea that someone can see my solution there that's why my solution has has been copied by somebody, and i promise it will not be repeated again. So kindly give me my ratings.

»
2 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

In Codeforces Round #787(Div. 3) Problem D(1675D) Codeforces System inform me about code leakage during the contest. My submission for the problem D is (shawonkumarsaha71/155995673) In the contest time VS Code is not working correctly (after 90 minutes from the beginning of the contest). so I use ideone for running code (https://ideone.com/EDGFDv). Unfortunately, in a hurry i didn't signin in ideone and for this reason this code is publicly visible. unintentionally, this incident occurred. I won't do it again.

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

Hey MikeMirzayanov, Aris, Gol_D, MisterGu, SixtyWithoutExam, Vladosiya, myav!

I got this mail stating, Your solution 155964614 for the problem 1675C significantly coincides with solutions rummansadik/155963028, rahulguptanitro/155964614. 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.

In the code, I stored the first occurrence of zero in z variable, and last occurrence of one in o variable, and then there were some condition if there were chances that string didn't have zero or one. The code was simple so it's merely a coincidence that our code matched.

I don't know this person and even the person is not from my country. And I never use online IDE for contests. So my code isn't available anywhere online.

Kindly provide me rating for the contest.

Regards, rahulguptanitro

  • »
    »
    2 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Moreover, I have given 100+ contests on codeforces and have a very clean records. I am still struggling here on codeforces. And this mail today highly demotivated me.

»
2 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Sorry to say,I used ideone for my code and it maybe public over there and that's why someone may be copied and i've got Attention massage from Codeforces.I'm very new in contest and i made a mistake unintentionally. I didn't get my rating for 1 similar code solution in #787 (div 3) where i solved 3. But didn't get any rating.Please consider for this time. I will be aware from next time.Thanks

»
2 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Good contest Problems were also interesting.