feecIe6418's blog

By feecIe6418, history, 4 months ago, In English

Hello Codeforces!

I am glad to invite you to Codeforces Round 958 (Div. 2) which will start on 15.07.2024 17:35 (Московское время).

The contest will last for 2 hours with 6 tasks for you to solve. The contest will only be rated for those with a rating not higher than 2099, but high-rated competitive programmers are also more than welcome to participate out of competition.

The score distribution is: 500-1000-1000-2000-2500-3500

The contest will be impossible without the help from:

Good luck and have fun!

Update: editorial

Update: video editorial

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

»
4 months ago, # |
  Vote: I like it +20 Vote: I do not like it

wtf a div2 with 3500 problem? Why not add more problems and extend it to a 1+2?

»
4 months ago, # |
  Vote: I like it +34 Vote: I do not like it

A huge difficulty gap b/w C and D O_o!!

»
4 months ago, # |
Rev. 2   Vote: I like it +15 Vote: I do not like it

Unrated only for Legendary Grandmasters:-O

»
4 months ago, # |
  Vote: I like it +127 Vote: I do not like it

Wow feecIe6418 round! I missed you a lot!

»
4 months ago, # |
  Vote: I like it -39 Vote: I do not like it

speedforces!!

  • »
    »
    4 months ago, # ^ |
    Rev. 2   Vote: I like it +135 Vote: I do not like it

    Screenshot-2024-06-13-031757"> ...

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

      Maybe, they call speedforces because the difficulty level in between two consecutive problem is too high. The person having more skills/practice got beaten by the speed of some other participants just because he was unlucky in starting problems in some of the contests. And anyway both candidates won't be able to solve the next problem because it's too difficult that results in negative rating change. <- My perspective :)

      • »
        »
        »
        »
        4 months ago, # ^ |
          Vote: I like it -9 Vote: I do not like it

        this. in some contest solving first 3 problem FAST is sufficient to be expert of even CM but solving first 3 problem SLOW can result in gray performance < 10000 rank.

        this high variance of distribution of problem difficulty scares many div3 people including me.

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

          Right. Solving first 3 problem FAST (in 15 minutes total) is much much better than solving first 3 problem SLOW (in 2 hours). What's your point?

          • »
            »
            »
            »
            »
            »
            4 months ago, # ^ |
            Rev. 4   Vote: I like it +20 Vote: I do not like it

            yes but having extra room to upsolve (problem D) may help those who failed early e.g) multiple WA on pretest, already gray but problem D is too high: (problem_rating — current_rating) > 500 -> game over. However if difficulty gap between B and C or C and D is reasonable this cannot happen.

            so the fair contest should form problem rating of arithmetic sequence, imo

            • »
              »
              »
              »
              »
              »
              »
              4 months ago, # ^ |
                Vote: I like it -10 Vote: I do not like it

              Nothing is 100% fair, just solve faster. I don't see your point.

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

                lets make contest with 1 gray *800 problem with 4 *3500 impossible problem.

                just solve faster.. okay.

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

                  You know I didn't mean it like that, but ok enjoy your upvotes.

          • »
            »
            »
            »
            »
            »
            4 months ago, # ^ |
              Vote: I like it -19 Vote: I do not like it

            Yeah, so, about that...

            I don't understand what people mean when they say speedforces
            just set balanced rounds?
            stupid?
»
4 months ago, # |
  Vote: I like it +38 Vote: I do not like it

As I tester, I enjoyed the problems and encourage you to participate!

»
4 months ago, # |
  Vote: I like it +6 Vote: I do not like it

Goal: ABC in 30 mins, D before the 2 hour mark.

»
4 months ago, # |
  Vote: I like it +39 Vote: I do not like it

as a tester

»
4 months ago, # |
  Vote: I like it +9 Vote: I do not like it

Hopefully, the problem statement will be short and precise just like the announcement!

»
4 months ago, # |
  Vote: I like it +2 Vote: I do not like it

Goal solving ABC by the end of contest

»
4 months ago, # |
  Vote: I like it +35 Vote: I do not like it

As a tester, I am sure about tolbi is Nutella.

Also participate this round, problems are very cool.

»
4 months ago, # |
  Vote: I like it 0 Vote: I do not like it

why isn't this on home page?

»
4 months ago, # |
  Vote: I like it +18 Vote: I do not like it

"I am glad to invite you to Codeforces Round (Div. 2)" . you haven't said div2's id XD

»
4 months ago, # |
  Vote: I like it -11 Vote: I do not like it

A + B + C = E.

»
4 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Thank you to all

»
4 months ago, # |
  Vote: I like it -24 Vote: I do not like it

Great! I hope to reach +1750 in this round

»
4 months ago, # |
  Vote: I like it 0 Vote: I do not like it

hoping to solve 3 problems

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

    Same

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

    problem statements are the main reason as we read a big story and makers make more confusing some good coders ignores the stories and go read testcases. some problem have confusing story and does not have testcase exxplained. took more time! good wishes ;)

»
4 months ago, # |
  Vote: I like it 0 Vote: I do not like it

@tkl2006 and @ishaandas1

I Want some tips on how to be eligible for system testing of these contests...

@feecIe6418 can also answer

»
4 months ago, # |
  Vote: I like it -8 Vote: I do not like it

1000?2000!

  • »
    »
    4 months ago, # ^ |
      Vote: I like it -11 Vote: I do not like it

    Every round should be unique so it's fine to have bit different score distribution

»
4 months ago, # |
  Vote: I like it 0 Vote: I do not like it

i have a strong conviction that this will going to be BIG speedforce for div3, fast solve ABC or ff.

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

    you were literally correct lol

»
4 months ago, # |
  Vote: I like it -8 Vote: I do not like it

OH! gyh I miss you a lot

»
4 months ago, # |
  Vote: I like it 0 Vote: I do not like it

omeganot orz

»
4 months ago, # |
  Vote: I like it -8 Vote: I do not like it

As a participant ,i love the testers.

»
4 months ago, # |
  Vote: I like it -8 Vote: I do not like it

Let's see if I can avoid bricking this contest.

»
4 months ago, # |
  Vote: I like it 0 Vote: I do not like it

hopefully i reach 1434 rating this round

»
4 months ago, # |
  Vote: I like it 0 Vote: I do not like it

I hope to reach 1100 in this contest (⁠ノ⁠^⁠_⁠^⁠)⁠ノ

»
4 months ago, # |
  Vote: I like it 0 Vote: I do not like it

I think this round is going to be mathforces

»
4 months ago, # |
  Vote: I like it 0 Vote: I do not like it

This is my first contest. Thanks to CodeForces.com. I will do my best for this contest.

»
4 months ago, # |
  Vote: I like it -25 Vote: I do not like it

You had Entire Saturday and Sunday. But no, we will host the round on Monday. wow.

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

    There is a Div. 2 round scheduled for this Saturday :)

»
4 months ago, # |
  Vote: I like it +6 Vote: I do not like it

i hope to be expert today

»
4 months ago, # |
  Vote: I like it +1 Vote: I do not like it

enjoy in contest.

»
4 months ago, # |
  Vote: I like it 0 Vote: I do not like it

oh this is the good chance that i can improve my rate :) HOPE CONTEST IS EZ!!!

»
4 months ago, # |
  Vote: I like it 0 Vote: I do not like it

C is 1000 points. Speedforces incoming.

»
4 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Hope I can be Expert in this contest!!!

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

GLHF

»
4 months ago, # |
  Vote: I like it +10 Vote: I do not like it

You meant to say that the contest would be impossible without the help from..., right?

Now it seems that we won't be able to solve any tasks unless we contact the creators :D

»
4 months ago, # |
Rev. 6   Vote: I like it -37 Vote: I do not like it

Mistake

»
4 months ago, # |
  Vote: I like it +1 Vote: I do not like it

And I keep falling! Am I getting more stupid or are CF contests getting more difficult?

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

    number of people who cheat are insane now. When ABC is hard cheaters will have the advantage because honest people wont be able to solve it but they can copy paste it from somewhere doesnt matter what the difficulty is.

»
4 months ago, # |
  Vote: I like it +29 Vote: I do not like it

The first one to pass problem E~

Also my first time to be the first to pass a problem on Codeforces! Happy~

»
4 months ago, # |
  Vote: I like it +11 Vote: I do not like it

Question D Looked so innocent to me, I thought it was only about Bipartiteness of the graph, Later I understood it's way more complex than that.

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

Fooled by score distribution! all eyes were on B and C, A surprised many.

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

I can't believe that more than 12k participants solved problem A all by themselves.

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

    Less than past contests, maybe cheaters needed some rest

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

    A is easy, am I missing something?

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

    Personally, I didn't come up with a formula for problem A. I just used multiset to simulate without thinking too much, with an extra optimization which is to not insert all the 1's inside the set again

    (My first solution got TLE because I underestimated the problem and didn't add the optimization lol)

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

    I wasn't able to solve A. I wasted too much time on it and because of that low rating in B and C.

»
4 months ago, # |
  Vote: I like it +51 Vote: I do not like it

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

Ther is a problem in a persian contest that is really similar to problem D.

Basically this problem there is no $$$a_i$$$ but the problem gives you a tree and asks you to set a positive integer value to all vertices in such a way that no to connected vertices have the same value and the sum of the values is minimum.

It is basically problem D but with $$$a_i = 1$$$ for all $$$i$$$.

It is not so far from problem D and i know two solutions for the problem in persian contest that can be changed to AC solutions for D by changing a few lines.

»
4 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Wasted 15 minutes reading OR as XOR :(

»
4 months ago, # |
  Vote: I like it +1 Vote: I do not like it

man, that was TOUGH :)

»
4 months ago, # |
  Vote: I like it 0 Vote: I do not like it

don't know why but I smell brute force in D.

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

    bro please clean your nose you are cooking wrong

»
4 months ago, # |
  Vote: I like it +9 Vote: I do not like it

probably the hardest div2 A I have ever seen

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

    I solved B & C but failed in A :<

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

      i solved A but failed in B idk why i missed some cases :( i need to work more

»
4 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Thanks for the contest. especially for task D. the first idea that comes to mind — two days is enough (painting tree in two colours) passes the sample but is wrong :(

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

A >>> (B + C)

»
4 months ago, # |
  Vote: I like it +11 Vote: I do not like it

OMFG got accepted E in the last 2 minutes. My first E in div2 for nearly 2 years.

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

    I was thinking of using segment tree and binary searching through the upto which range our ai is the current minimum. Is this approach correct. In theory this will work in O(N log^2N). What do you think

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

      It is still ambiguous. Can you say it more clearly?

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

        Let's say our original sum is F

        when A[i] is removed we calculate from 0 to i. The minimum idx which have min(idx, i) is A[i], lets say X . and maximum idx which have min(i,idx) is A[i], lets say Y. Then count the subarrays between [X,Y] in which i is included. Subtract this*A[i] from the F for this index ans

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

      instead of segtree + binary search, you can just use a stack...

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

        I haven't really solved problems using Stacks. And yea this is one of my weakness that my mind focus on Seg trees whenever something related to range comes. gotta work on that. And I will try to solve the problem with both approaches. Thanks for the info

»
4 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Damn, I got too many penalties on B for concatenating to a new string instead of just using normal variables.

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

A is harder than C, Nice.

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

    In what sense bro, i couldn't come up with any idea how to approach C :(

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

      lets say we have bits in positions 4,3,2,1

      what's the optimal here ? first lets take all bits then we take 4,3,2 then 4,3,1 then 4,2,1 then 3,2,1

      now its just in reversed order :) that's why I said what I said

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

        Cool!

        A is easy too....just think like : Break the current number(>1) in max possible 1 you can break, leave rest for next step.

        EX: S = 5, k = 2

        1 4

        1 1 3

        1 1 1 2

        1 1 1 1 1

        EX: S = 6, k = 3

        1 1 4

        1 1 1 1 2

        1 1 1 1 1 1

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

          if n would have been large this brute force would have failed, but within these constraints this solution seems okay

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

            Yes, after getting this logic i checked the constraints.

            since it's problem A i was sure that constraints will be low.

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

          But tell me the proof why every time we convert it to maximum 1..... We need to minimize the operations as well.... How would you conclude that this will take minimum operations??

          If it comes in your mind, then it is easy else it is very hard to think with proof for Div2A....

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

            This is the Brute force solution which one can think (obviously by taking some test case by themselves and proving whether this is a correct approach ensuring minimum operations).

            I think most of them denied this solution because they might have thought it would give TLE (and the pressure to solve A in minimum time too). So they chose to think in some optimal way and messed up (can you believe some used DP to solve it).

            After thinking this approach you can see i implemented it in the brute force way too, but you can see from editorial after getting this logic one can also write answer as (n + k-3) / (k-1) which didn't striked in my mind.

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

              Donyou mean by taking some testcase...if it is minimum then it is minimum.... You shoudl have concrete proof for it.

              How do you prove that Brute force will produce minimum operation

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

                Your possible approach becomes a solution once it is correct for every test case given along with the question(at least). And also if your are not satisfied you take some test case by your own and check if by any other method (like how it was done in qn) you can get a answer less that what you get by your approach.

                I think you didn't understand what i was trying to explain with the solution.

                Breaking the current element into max 1 will itself ensure you are choosing a minimum way(but not optimal, of course). Let's take another example:

                S = 4 , k = 4

                Break it into max 1 we can: 1 1 1 1

                No. of ops = 1.

                Suppose you're developing an approach so you might also think how about breaking it into:

                1 3 ( insert no more than k positive integers, and we have chosen only two i.e <=k)

                but this will not lead you to minimum ops.

                Just take a big n and small k within the constraints and simulate it yourself, you will get approach.

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

    Both the observation and implementation of A are simpler than C

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

    for the first time i couldn't solve A, but i was able to solve B and C.

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

    Did A in 9 mins, but was not able to do C even after throwing my whole mind at it for 1.5 hours.

»
4 months ago, # |
  Vote: I like it 0 Vote: I do not like it

It's interesting that the problems time limit is in ascending order.

»
4 months ago, # |
  Vote: I like it 0 Vote: I do not like it

ok i swear if the submission for D that im about to send ACs im gonna be so pissed (i was 3s late)

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

    also here's my approach for D

    observation 1: you only need to delete at most 3 times

    first deletion will split everything into trees of depth 0 or 1 (if it's depth 2 then the non-leaf can be deleted in the first move and it's guranteed to be better)

    2nd and 3rd deletion just "cleans" the trees of depth 0,1 i let dp[a][i] = min price to delete subtree i WHILE deleting node i at t = a

    then for all child v1,v2,...,vk of dp[1][i] = val[i] + min(dp[2][v1], dp[3][v1]) + min(dp[2][v2], dp3[v2]) + ... + min(dp[2][vk], dp[3][vk])

    dp[2][i] = 2*val[i] + min(dp[1][v1], dp[3][v1]) + ... (you get the idea)

    then the final result would be min(dp[1][0], dp[2][0], dp[3][0])

    however this gets wrong answer on pretest 2 (either it's wrong or it's my implementation that's wrong)

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

      just go with log2(n) instead of 3

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

        Can you tell what's the intution behind log(N) rounds

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

          i tried firstly with 3 got wrong ans then thought max it can be 100 looking at the constraint then got tle then i just felt since my logic and implementation is correct it must be logn

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

      8 1000 1 1 1000 10000 10000 10000 10000 1 2 2 3 3 4 1 5 2 6 3 7 4 8

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

        wow...

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

          so turns out i threw top 80 because of that

          still positive delta tho so yay..?

          at least it was better than last div2 where i solved a wrong version of E and spent forever debugging it (only to realize the mistake AFTER the contest)

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

      I tried the exact same thing ;-; , but using this logic idk why it didn't even pass the given tc , will have to upsolve later:).

»
4 months ago, # |
  Vote: I like it 0 Vote: I do not like it

so hard :( but nice problem. I think E is pretty good.

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

resolved

»
4 months ago, # |
  Vote: I like it 0 Vote: I do not like it

can anyone tell Whats the logic behind problem -d

my logic — just doing dfs and marking all alternate nodes in a tree then the answer will sum of all nodes + min(sum of marked node, sum of unmarked nodes)

  • »
    »
    4 months ago, # ^ |
    Rev. 5   Vote: I like it 0 Vote: I do not like it

    Think of a case like this one:

    1

    4

    100 5 5 100

    1 2

    2 3

    3 4

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

    it fails this test case

    1

    4

    1000 1 1 1000

    1 2 2 3 3 4

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

    i think its because lets say u have 4 straight connecting nodes and u can imagine like an array and counter test case will be something like 100000 1 1 10000 since best option is picking 1 and 4 instead of 1 and 3 or 2 and 4

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

    if the tree is 10 — 1 — 1 — 9 the answer is not 31, but 24. the optimal in this case is with 3 turns instead of 2 (I'm also thinking about the logic, but this was my counterexample of the dfs idea)

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

    this shouldn't work, counter scenario: think of an array where you need to maximize the total value you pick without picking adjacent elements! this can be solved by a simple dp; and so this each path in this tree can act as an individual array if you think

»
4 months ago, # |
  Vote: I like it 0 Vote: I do not like it

is there a direct bitwise formula for C I solved it but nevertheless found the bit manipulation I did quite complicated.

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

    Can you explain your logic in brief Please ?

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

    You can take a look at my solution here. You basically iterate over the bits from highest to lowest significance, and if the bit is on, you turn it off and print the rest of the bits as they were. Also don't print zeros and that's it.

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

    You can look at my solution if it is of any help

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

    take n in binary for example 23 is 10111

    the answer will look like :

    (the number of ones + 1)

    00111 10011 10101 10110 10111

    look at my submission

»
4 months ago, # |
  Vote: I like it +5 Vote: I do not like it

The number of submissions for problem C is beyond my expectations and nowadays looking at no of submission always demotivates me(i feel how this fast submission crossed 1000)

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

    true, It feels like I am too dumb for not solving A in 5 minutes.

»
4 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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

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

Not able to solve B after lot of attempts can't find the case where the code goes wrong.

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

    let me help you bro

    think of this test case 00000011100000000

    here in this test case in first move you will combine all prefix 0 with 1 in the second move combine all suffix 0 and in the third move apply operation on the remaining array so answer will be 1

    the corrrect approach is to combine all consecutive 0 into one '0' so that no one gets into waste and then checking is count of 1 is greater than 0 or not

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

    Just replace all consecutive zeros with a single single zero(make a new string) and then count c0 and c1 and apply the conditions given in the question.

»
4 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Can someone explain in short the idea for C ?

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

    For each number, just unset one set bit starting from msb to lsb

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

    My solution : keep searching the bit which is 1 from the smallest bit. When it is 1 , replace it with 0 and make the bits after it to be valid for A | B = N (So we can keep finding smaller number)

    (Sorry, My English is bad, I am not native speaker.)

    Example:
    - 14 = 1110
    - =>   1100
    - =>   10?? (only 1010 is valid for A | B = N)
    - =>   0??? (since 1010 | 0??? should = 1110 , 0??? can be 0110 or 0100
    and no more answer smaller.)
    
    • »
      »
      »
      4 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Therefore, the answer of 14 => 4

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

        Great. But How can you be so sure that in every number only one '1' is made zero ?

        like can't we make multiple '1' to '0' ?

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

          Because there are two rules we need to follow.

          1. Find the maxinum amount.
          2. You need to make sure every next number you find is smaller.
          

          To achieve the rules mentioned above, make only one '1' to '0' is a good method. ( If we make multiple '1' to '0', since we need to make sure A | B = N , then the total amount will be smaller than make only one '1' to '0' each time. )

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

    Lets build $$$a$$$ from the end.

    $$$a_k$$$ cant be larger than $$$n$$$ because that would mean $$$a_{k-1} | a_k>n$$$.

    It turns out that $$$n$$$ can always be put as $$$a_k$$$. (dont know how to prove that sometimes $$$a_k$$$ smaller than $$$n$$$ can result in bigger $$$k$$$)

    Now for every next number $$$a_i$$$ we construct (actually previous in $$$a$$$) we will try to decrease it as little as possible compared to $$$a_{i+1}$$$ while the $$$a_i | a_{i+1}$$$ is equal to $$$n$$$.

»
4 months ago, # |
  Vote: I like it +1 Vote: I do not like it

in C, is the len of the longest sequence equal to => (no.of set bits in n)+1, except for the cases where the no.of set bits is less than equal to 2..

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

    when no of set bits > 1, the answer is just no of set bits plus 1; otherwise, just print 1

»
4 months ago, # |
  Vote: I like it +13 Vote: I do not like it

Probably the best contest I ever gave on Codeforces. Got wrong answer on A then understood my mistake and then solved C with 1 minute 29 seconds remaining!!!!! Very happy rn.

»
4 months ago, # |
  Vote: I like it -23 Vote: I do not like it

Hello,

These problems were trash.

Yours faithfully.

»
4 months ago, # |
  Vote: I like it 0 Vote: I do not like it

solved a, b in 14 mins but could not solve C. Can some one throw some light. Am i missing somethng obvs?

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

    take n in binary for example 23 is 10111

    the answer will look like :

    (the number of ones + 1)

    00111 10011 10101 10110 10111

    look at my submission

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

    print number in binary format

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

    N = 13 {1101}

    unset the msb

    0101 = 5

    set the previous unset bit and unset the next bit

    1001 = 9

    do this again

    1100 = 12

    1101 = 13

    the length of this seq will be equal to == No of set bit + 1

    Special Cases(2^N)

    Length = 1

    sequence is 2^N only

»
4 months ago, # |
  Vote: I like it 0 Vote: I do not like it

started 1hr late solved B and C only stuck at a cause A, doubt was whether there exist an easy sol in constant time but would have implement in log(n) complexity rather if no time pressure. Will try best to wakeup early next time

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

    For problem A: imagine you have a block of length $$$N$$$, and you can cut it at $$$N-1$$$ different positions. During one move you can make $$$K-1$$$ cuts (this splits a piece into $$$K$$$ pieces). You want to make cuts at all $$$N-1$$$ positions, since this will result in $$$N$$$ pieces of size 1. This means the required moves will be $$$\lceil \frac{N-1}{K-1} \rceil$$$.

»
4 months ago, # |
  Vote: I like it 0 Vote: I do not like it

i think D was too hard

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

    I turned my head away from that problem and went to E as soon as i realise its prolly DP on trees LOL

»
4 months ago, # |
  Vote: I like it +1 Vote: I do not like it

Hello everyone, this contest is good. I solved 2 questions in 13 minutes, but I'm stuck on the 3rd question. Even though the 3rd question is challenging. There was a live stream running on YouTube called "Sharabi Lal". If someone official is watching, please block this. However, even if they do, they might create another channel. What can we do? Maybe you should increase the quality of the plagiarism checker or something similar. If someone is found cheating, you could mark their ID differently or publish the name of the cheater after the contest. Or maybe not. I'm just frustrated.

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

    Yes, you could also have a "Report Suspicious" button where someone could report if they suspect someone else of copying code.

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

    Please edit out the channel name else more cheaters would get to know about it and follow him.

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

Is D dp, trees or both?

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

    Basically Dp...try to traverse from one leaf node...

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

    DP, the move in which you kill a subtree's root must be different from the time in which you kill its children. You can have $$$dp[i][j]$$$ = the minimum cost to kill the subtree rooted at $$$i$$$, if you kill the root during move $$$j$$$. For $$$dp[i][j]$$$, we take $$$A[i]*j$$$ damage from the root, and then we then have to pick $$$j' \ne j$$$ for all the child subtrees.

»
4 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Rainboy round , I want to know which country he belongs to.

»
4 months ago, # |
  Vote: I like it +1 Vote: I do not like it

How to not choke in questions like A :<<

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

    What I try to do is Think simple and don't overcomplicated anything and be greedy(Although it doesn't work everytime)

»
4 months ago, # |
  Vote: I like it 0 Vote: I do not like it

This contest let me become purple and >1900 for the first time, i love the problems!!!(O.o)

»
4 months ago, # |
  Vote: I like it 0 Vote: I do not like it

What's the idea behind problem E?

»
4 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Why was my D-question never system tested?

»
4 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Hi everyony. It's written in the description that "The contest will only be rated for those with a rating not higher than 2099". But my rating hasn't changed yet. Should I just wait for some time or there is some kind of mistake?

»
4 months ago, # |
  Vote: I like it 0 Vote: I do not like it

I saw A tutorial it's really easy I think I couldn't solve it because I restricted my self that in each operation n should be divided by number <= k

»
4 months ago, # |
  Vote: I like it 0 Vote: I do not like it

I got WA in 270731172 during the contest. I submited the same code after contest and it accepted. 270754276. Why ?

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

    I don't think both codes are same, you must have made some changes

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

      Oh yes. I change local vector to global vector.

  • »
    »
    4 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    if(pow(2, bits-1) == n)
        {
            cout << 1 << endl << n << endl;
            return;
        }
    

    ur code fails here.

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

      It checks whether the n is power of 2 or not. Also this lines present in the AC code. I think I got WA because I use local vector and when I use global vector I got AC. I don't why.

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

        no, it got lucky AC

        pow(2, bits-1) returns double, and double precision is not that good.

        try to use (1 << (bits-1)) instead, it will get accepted whatever vector u use

»
4 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Problem D got me good. Oh well, We will get 'em next time.

»
4 months ago, # |
  Vote: I like it 0 Vote: I do not like it

good contest!

»
4 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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

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

    But tell me the proof why every time we convert it to maximum 1..... We need to minimize the operations as well.... How would you conclude that this will take minimum operations??

    If it comes in your mind, then it is easy else it is very hard to think with proof for Div2A

»
4 months ago, # |
  Vote: I like it 0 Vote: I do not like it

I Got 42 plus if not that skipped it would have increased by 60 or more

»
4 months ago, # |
  Vote: I like it +1 Vote: I do not like it

Hello

»
4 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Bruhhhh

I have been practicing DP and Greedy problems for the last week. Solved A quickly, realized it was just a single formula.

Solved B, using the another solution mentioned in the editorial.

Looked at C, thought it was gonna be easy and then saw the constraints. I have 0 experience in good bitwise and tree based questions and got cooked. I knew it had to do something with 2^64 and the loop running 64 times but not the logic lmfao. I was so disappointed with my performance, I wanted to solve atleast 3 questions but none of the topics I practiced came.

»
4 months ago, # |
  Vote: I like it +11 Vote: I do not like it

Finally became a CM, thanks for the contest!

»
4 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Do you guys know why some questions are skipped in judging?

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

    due to more than one submission of same question or cheating...

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

      What does it mean more than sending?

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

        i mean like submitting the already solved question's answer again during the contest.

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

          I'm sure none of these things are possible, how can I communicate this with Codeforce?

»
4 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Recently i got message from codeforces about same solution with Rudransh58 but i even don't know who is Rudransh58. It is totally conicidence that core idea of problem is same of both. The method of doing question is totally different of me and Rudransh58.It is totally unfair.

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

Dear Codeforces Team,

I recently received a notification regarding a solution coincidence for problem 1988C with solutions Rudransh58/270724137 and 2022ucp1403/270738520. I would like to address this concern and provide some context.

First and foremost, I want to assure you that I have always adhered to the rules and guidelines of Codeforces and have achieved my rating through my own efforts. I have not engaged in any activity that would violate the rules, including sharing or copying code.

I am unaware of how this coincidence occurred, but I can provide the following points to support my position:

Independent Work: My solution was developed independently based on my own understanding and problem-solving approach. Code Sharing: I have never used public platforms like ideone.com with default settings or any other medium to share my code. I take the confidentiality of my work seriously. Common Sources: It is possible that the coincidence is due to the use of common techniques or standard algorithms widely known in competitive programming. If there are any common sources that could have led to this similarity, I am unaware of them. I am committed to maintaining the integrity of the competitive programming community and am willing to cooperate fully to resolve this issue. If further details or explanations are required, I am ready to provide them.

Thank you for your attention to this matter.

Best regards, Rudransh58

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

    Your coding style completely changed between problems A/B and problem C. Even the indentation and formatting are different.

    Problem A and Problem B, which use <bits/stdc++.h>, include macros for ll and mod, and solve everything in the main function.

    Problem C, which uses different includes, no macros, uses a solve() helper function for testcases, and has different spacing/formatting.

    • »
      »
      »
      4 months ago, # ^ |
      Rev. 5   Vote: I like it 0 Vote: I do not like it

      It's because i've used diffrent moduled code which i've pre written on my vs code, so i did use diffrent includes, no macros, used a solve() function that's on my vscode!!, and changing the code writing style does'nt mean i've copied the code.

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

Respected MikeMirzayanov, feecle6418 and the system admin team of codeforces,

I recently received a notification regarding a solution coincidence for problem 1988C with solutions ksp.77/270714693, 07-priyanshu/270714907. I then got some more notifications regarding the same. I would like to address this concern and bring some facts to you.

In this regard, I would like to express that i always adhere to the rules and regulations of the amazing platform codeforces and its guidelines. I never intend to share my code with anyone or copy others code. Also, this is the first time my solution got skipped and i am experiencing something like this. Whereas, ksp.77's solution from last 5-6 contests are being skipped which is not the case with me.

I am unaware of how this coincidence occurred, but I can provide the following points to support my position:

Simple Code: My solution used variable names as 'v' for array, since i use 'v' in cpluscplus for vectors. Ans since the example test case was initally not passing when i was in initial phase of my coding my solution so i moved to Python. I usually use 'a' for variable name of array but since i just transalated my code myself so did not get the intiution to change the variable name. Also, the first loop was very standard method of bit shifting and must be available on internet beforehand and once the algorithm or idea of this question is understood , the second loop can be formed easily.

Common way of approach & python language: I checked the submission history for this solution and i find that many solutions in C++, C or java have the exact same approach but they have not been flagged similar to me. This could happend because python or PyPy syntax is standard and can look more similar to other compared to other languages like C++, Java , Python. Also, my solution was already very optimised.

Time of submission: For this problem I think i submitted before other who have been tagged similar to my solution.

Independent Work: My solution was developed independently based on my own understanding and problem-solving approach.

Code Sharing: I have never used public platforms like ideone.com with default settings or any other medium to share my code. I take the confidentiality of my work very seriously.

Common Sources: It is possible that the coincidence is due to the use of common techniques or standard algorithms widely known in competitive programming. If there are any common sources that could have led to this similarity, I am unaware of them. I am committed to maintaining the integrity of the competitive programming community and am willing to cooperate fully to resolve this issue. If further details or explanations are required, I am ready to provide them.

Thank & Regards, 07-priyanshu

(Thanks Rudransh58 for guiding me how to draft the above message as i faced similar situation as you)

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

Why many contests of july 2024 are skipped ?

what is the reason and how can i contact codeforces?

»
4 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Hello. I have a question: I got 1700 this round and I did see that my rating increased about 261 or so, but after 2,3 days, this became unrated!! Is this a bug? Could somebody please tell me why this would happen, please?

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

.