iNNNo's blog

By iNNNo, history, 9 days ago, In English

Hello, Codeforces!

I am glad to invite you to participate in Codeforces Round 951 (Div. 2), which will take place at Jun/06/2024 17:35 (Moscow time).

This round will be rated for participants with a rating below 2100. Participants with a higher rating can take part out of competition.

You will be offered 6 problems and 2 hours to solve them! Interactive tasks may occur in the round. Please read this blog to get familiar with this type of problems.

All tasks are authored and prepared by me. However, I'd like to thank Greg908 for discussing ideas about problems and useful feedback!

I would like to thank:

The goal was to create problems interesting to solve. Hope you'll enjoy them all!

Score distribution: $$$500 - 1000 - 1500 - 2000 - 2500 - 3000$$$;

Good luck!

UPD: Congratulations to the winners!

Div. 2:

  1. Tanikaze_Amane

  2. olmrgcsi

  3. PMPuns

  4. MegalovaniaJ

  5. Sylphrena

Div. 1 + Div 2:

  1. turmax

  2. jiangly

  3. kotatsugame

  4. peti1234

  5. BurnedChicken

Editorial is out!

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

»
9 days ago, # |
  Vote: I like it +11 Vote: I do not like it

Scoring is an AP! Been waiting for such a round.

»
9 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Look who's doing purple testing

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

    Yeah, we get it. Kinda common as an East Slavic name tho.

»
9 days ago, # |
  Vote: I like it 0 Vote: I do not like it
»
9 days ago, # |
  Vote: I like it +9 Vote: I do not like it

Hoping +ve Delta

  • »
    »
    8 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Forget about +ve delta dude. CF is brutal.

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

      agreed, solved C before B , B took almost 90 mins. again i am going down from so close from expert

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

        lmao, author so obsessed with cyclic shifts he applied one to the problem ordering of B,C,D

      • »
        »
        »
        »
        8 days ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        how did you solve the B. I quite didn't get how the XOR would work in that.

      • »
        »
        »
        »
        8 days ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        how did you come up with the idea of B?

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

          dont know why but smallest set bit in xor is giving answer

          • »
            »
            »
            »
            »
            »
            8 days ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            I did it like this let rth term of seq a be coincides with sth term of seq b. Then we will have rth term as x^r and sth term y^s which are equal so x^r = y^s Taking xor on both sides we have r = x^y^s So for all values of s [1,...] we will have a value of r now this seq will continue until no bit of s coincides with set bit of x^y. When they do the coresponding value of r will be differnt for that s

            So number of possible results are the lsb in their xor

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

          The answer is pow(2,the number of identical last bits of two numbers)

          • »
            »
            »
            »
            »
            »
            8 days ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            It's easier to see it as the biggest power of 2 that divides the diference between x and y

            • »
              »
              »
              »
              »
              »
              »
              8 days ago, # ^ |
                Vote: I like it 0 Vote: I do not like it

              Or that divides their bitwise XOR.

            • »
              »
              »
              »
              »
              »
              »
              7 days ago, # ^ |
                Vote: I like it 0 Vote: I do not like it

              what made you come up with the idea of taking their difference?

              • »
                »
                »
                »
                »
                »
                »
                »
                7 days ago, # ^ |
                  Vote: I like it 0 Vote: I do not like it

                I just guessed that by the samples, when u notice that every answer in the output is a power of 2 then u tries to guess where it came from, I used the sample with the bigger numbers to confirm my intuition.

          • »
            »
            »
            »
            »
            »
            7 days ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            How is that derived?

      • »
        »
        »
        »
        8 days ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Not as close as me :(

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

        Damn you applied binary search, thought but couldnt make it on time

      • »
        »
        »
        »
        8 days ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        B is easy with the right observation approach. C was more tricky, and D kinda casework-heavy. Managed to solve up to D.

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

        can anyone help me by telling if this approach can work for b or not so lets say there is a common segment of length n between the sequences a and b.

        • let the starting element from a be :- a xor x
        • the starting element from b :- (a+k) xor y
        • here k can be any integer such that a>0 and a+k>0
        • now, sum of sequence from a :- (a xor x) + ((a+1) xor x) + ((a+2) xor x) + .. till n terms = (n*a + n*(n-1)/2) xor x (let it be sum1)
        • similarly from b = (n*(a+k) + n*(n-1)/2) xor y (let it be sum2)
        • now since both these sums are equal (sum1 = sum2) therefore, (sum1) xor (sum2) = 0

        • sum1 xor sum2 = ((n*a + n*(n-1)/2) xor (n*(a+k) + n*(n-1)/2)) xor (x xor y) = 0
        • therefore ((n*a + n*(n-1)/2) xor (n*(a+k) + n*(n-1/2)) = (x xor y)
        • after solving i found out :- a = (c xor (n*c + n*(n-1)/2 + (n*c) xor d) / n (here c = x xor y)
        • if for some 'n', 'a' comes out to be a natural number and a+k is also > 0 then we can binary search over all values of n.

        if anyone can help me , can this work

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

          I have no idea why you make it so complicated. B was literally this easy, I solved it in 5 minutes:

          ll ans=(X^Y)&-(X^Y);
          
          • »
            »
            »
            »
            »
            »
            7 days ago, # ^ |
            Rev. 2   Vote: I like it 0 Vote: I do not like it

            man, i am absolutely terrible at bit manipulation. even though i am noob at cp, but at bitmasks and all my mind just gets stuck. how do you even come to this 2^k conclusion. any tips ?

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

              Okay, so here's my thought process: If two XORs are equal, that means XORing both sides produces 0. Therefore, you can introduce a new variable, $$$Z=X \oplus Y$$$. So XORing something with $$$Z$$$ produces 0 when the other mask has the same bits. Therefore $$$a_{i} \oplus b_{i}$$$ must be $$$Z$$$. It is achievable when they differ in bits where $$$Z$$$ has 1, and have the same bits where $$$Z$$$ has 0. That means, if we know $$$a_i$$$, we know exactly what $$$b_i$$$ should be. So the last 0s in $$$Z$$$ means that there is a match between $$$a_i$$$ bits and $$$b_i$$$ bits. Increasing $$$a_i$$$ will result in an increasing $$$b_i$$$ as well. But when the bit flips at the first position where $$$Z$$$ has 1 in $$$a_i$$$, $$$b_i$$$ should flip too, which spoils the increasing pattern. Therefore, check the least significant bit of $$$Z$$$. It is well known, that x&(-x) returns the LSB of $$$x$$$.

              • »
                »
                »
                »
                »
                »
                »
                »
                7 days ago, # ^ |
                  Vote: I like it 0 Vote: I do not like it

                so it was like, the maximum range of numbers will be no of 0 bits at end . for example if it was two 0 bits , then the possible numbers would have been i,i+1,i+2,i+3 (similarly for j) and at i+4 the third bit would have changed for both i and j and it would have gotten equal and hence there xor would have become 0 whereas there is 1 bit at that position in Z.

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

              it was an observation problem. I read the problem and got a rough idea that solution might contain something like checking which bits are matching and not, and doing something from there on. Then read the test cases.

              The test cases were a huge giveaway for this question. The output of 8 (1000) for 4 (100) and 12 (1100) (first 3 bits match from LSB and ans is 2^3) hinted that we might need to check for first few matching bits in binary representation. So just pulled up a calculator, and converted all test cases input to binary, matched with output, saw the pattern. That's it.

              Pattern: 1000...(as many zeroes as no. of matching bits in both nos. from LSB)...000

              Now the idea was not directly ll ans=(X^Y)&-(X^Y), but it can easily be simplified to that. You do need to worry about that. You could have just converted both numbers to binary and checked bit by bit manually for matching bits from LSB, and got the right answer. The notation is just an easier and mathematical way to do the same thing, which just comes over time.

              • »
                »
                »
                »
                »
                »
                »
                »
                7 days ago, # ^ |
                  Vote: I like it 0 Vote: I do not like it

                damn. so as soon as i see a bit manipulation problem i should just straight away start thinking and writing in binary representation.

                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  6 days ago, # ^ |
                    Vote: I like it 0 Vote: I do not like it

                  bit manipulation by definition means bit — which in most cases refers to digits in binary form of numbers. Although I am only a specialist so you should take my words with some salt, but in general, bit manipulation problems are (almost?) always solved by using binary representation.

                  The tough part is not decide whether we have to use binary form for the bit manipulation, it is to identify whether the problem is of bit manipulation or not. To identify that, sometimes author of problem puts hints in problem statement, or constraints (like m<30, bcz 2^30 is 10^9, etc.), or in the sample cases (like this question, where analyzing cases gave away the entire trick). Sometimes there are no hints at all and we have to analyze the problem ourselves and come to a conclusion, other times a problem may look like "obviously" a bit manipulation problem but turn out to be something else.

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

                  okk. thanks for the advice. i will start practicing on some bit manipulation problems keeping in mind these things. btw what basic things would you advice me to learn for bit-manipulation like how to find OR of range of numbers and all.

                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  6 days ago, # ^ |
                    Vote: I like it 0 Vote: I do not like it

                  I learnt all this quite some time ago so I don't remember where exactly I learnt it from, but there are plenty of resources on google, maybe some resources on codeforces catalogue section also might be there.

                  Another and probably the most important thing you should do is once you have solved a question, see others' solution. That way you can see different techniques which might be useful at other places. For example, in this question, you can explore why (X^Y)&-(X^Y) gives the same answer as the pattern matching I stated above (giving the position of lowest set bit), and in the process you may learn many new things. Just try to always explore and learn. Read editorials and everything.

                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  6 days ago, # ^ |
                    Vote: I like it 0 Vote: I do not like it

                  hmm got it. thanks

    • »
      »
      »
      8 days ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      What is +ve delta,dude?

      • »
        »
        »
        »
        8 days ago, # ^ |
          Vote: I like it +10 Vote: I do not like it
        The uppercase letter Δ is used to denote: Change of any changeable quantity, in mathematics and the sciences (in particular, the difference operator[5][6]) — Wikipedia

        On Observation you may notice that the only changeable quantity after CF rounds ( or the most obvious one :P) is the rating of participants.

        " A positive delta " hence denotes a positive change in the changeable quantity.

»
9 days ago, # |
  Vote: I like it -17 Vote: I do not like it

I'm Salah Eldeen Al-Ayoubi

»
9 days ago, # |
Rev. 2   Vote: I like it +21 Vote: I do not like it

I'm wondering if any time when authors had indicated that interactive task "may" occur eventually it didn't appear. Since there is an exact number of tasks aka 6, I understand the author knows exactly what tasks are the final ones, unlike when you are not sure which tasks will be final and provide a spread (like 5-7 tasks) where indeed interactive tasks may but may not occur. Is there any reason to be not explicit in such cases? ;)

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

    Maybe they haven't decided between two tasks and only one of them will be in the contest?

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

      Yes, it might be the case, but I consider all the contests when interactive problems occur. In 80 or more percent of cases when an interactive problem was mentioned, it is formulated like "Interactive problem may occur" and seldom "One or more problems will be interactive".

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

    If an interactive task is coming, I hope it's not E or F again, it's always sad that I never get to try the interactive ones because they are obviously beyond my competetence...

  • »
    »
    9 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    It kinda partially happened in my contest 4 years ago, I stated that interactive problem(s) might have appeared, and in fact the only interactive found was Div1E (and no interactive in Div2 at all).

»
9 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Time to test my limits again , hoping for an interesting round :)

»
9 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Can't wait!

»
9 days ago, # |
  Vote: I like it 0 Vote: I do not like it

wishing to get +4 and not brick like I did last time when I needed +3 for cyan :)

»
9 days ago, # |
  Vote: I like it -51 Vote: I do not like it

hope to reach specialist this round <3

»
9 days ago, # |
  Vote: I like it -16 Vote: I do not like it

Hope to return blue color for my handle ;)))

»
9 days ago, # |
  Vote: I like it +5 Vote: I do not like it

Is this round mathforces or algoforces?

»
9 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Good luck to everyone except no one!

»
9 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Interactive tasks may occur in this round

»
9 days ago, # |
  Vote: I like it 0 Vote: I do not like it

I always get stuck on C in a div 2 contest.

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

Waiting for starship launch as well as div2

»
8 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Hoping +ve delta after 2 bad contest for me

»
8 days ago, # |
  Vote: I like it +24 Vote: I do not like it
Score distribution
»
8 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Good Luck Have Fun!!

»
8 days ago, # |
Rev. 2   Vote: I like it -18 Vote: I do not like it

sorry

»
8 days ago, # |
  Vote: I like it +6 Vote: I do not like it

Best wishes for everyone's A, B, C and D.

»
8 days ago, # |
  Vote: I like it 0 Vote: I do not like it

good luck everyone:)

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

I want to thank to the cosmic entity which come from heaven that come up with Problem B was great problem. I mean who in the right mind thought , ya problem B looks super cool and amazing , people will observe the test case even if it takes 80 minutes , btw solved C in 20 minutes

  • »
    »
    8 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    how c in 20 minutes?what was the observation?(sample cases?)

    • »
      »
      »
      8 days ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      binary search on total sum and to check distribute in array with ceil(sum/a[i])

      • »
        »
        »
        »
        8 days ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        i did the same thing lol. I was actually surprised it worked xd

      • »
        »
        »
        »
        8 days ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        I didn't even think of binary search, I just found the Lowest Common Multiple and it worked. Sum should be < LCM if not "no solution".

»
8 days ago, # |
  Vote: I like it +13 Vote: I do not like it

mathforces

»
8 days ago, # |
  Vote: I like it +16 Vote: I do not like it

Samplecase forces ,or maybe I need a lot more practice

  • »
    »
    7 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Same, I didn't know why my solution to C of LCM is right until I read the tutorial

    • »
      »
      »
      7 days ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      I still don't know why I took the sum as 10^9 and it worked. I will take it, but I want to understand lol.

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

My solution to C without LCM 264475190

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

    I have proof for the binary search solution, but i dont have proof for the lcm solution

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

      I just came here and read the comments abt lcm. I'm really puzzled how it occurred to ppl and how they solved it using lcm. Only BS occurred to me at the moment

»
8 days ago, # |
  Vote: I like it +40 Vote: I do not like it

Guessforces

»
8 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Hint for C anyone? ;)

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

    LCM. (I just somehow guessed it, couldn't prove it in-contest either)

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

    it involves basic math

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

    Let $$$S=\sum x_i$$$

    $$$x_i*k_i > S \implies x_i > S/k_i $$$

    Sum over all $$$i$$$: $$$S > \sum{S/k_i}$$$

    Divide both sides by S: $$$1 > \sum{1/k_i}$$$. If this condition is true $$$S$$$ can be anything, otherwise no solution. But since we need integers simplest is to take LCM

    Sad I was one hour-late, problems look interesting

    • »
      »
      »
      8 days ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      how can S be anything? If you choose S as 1 even if it satisfies the above condition, it won't work right! Can you be a little more specific

      • »
        »
        »
        »
        8 days ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        S can't satisfy the condition or not. If you choose S=1 for k=3,2,7 as in samples then:

        x=14/41, 21/41, 6/41. Each $$$x_ik_i$$$>1

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

      Whats the problem in this code line ? I have used some multiplier times LCM to be the sum. ~~~~~ code ~~~~~

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

      in the editorial its being said that the condition 1>sigma(1/k) is a sufficient condition for answer to exist how can this be proven ? as such necessary condition i can prove using the method you used . vstiff iNNNo

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

    Just check if sum of money = $$$10^9$$$ is possible or not. I don't have any proof either.

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

I gave up on E, so here is your partial editorial

A:

Hint 1: What is the way to get the smallest maximum of a range of more than one element.

Hint 2: Look at only pairs of adjacent elements

Sol:

Search every pair of elements. Answer is minimum of the maximum of pairs — 1.

Code:

https://codeforces.com/contest/1979/submission/264409254

B:

Hint 1: Think about BITwise.

Hint 2: Look only at the first few elements in the list until items differ.

Sol:

Find the difference between a and b. Answer is the maximum power of 2 that divides this difference.

Code:

https://codeforces.com/contest/1979/submission/264415773

C:

Hint 1: Think of a way to equalize earnings.

Hint 2: What is the smallest number that is a multiple of all numbers.

Hint 3: How do we check if there is no solution.

Sol:

  1. Take the LCM of all multipliers.
  2. Put LCM/multiplier for each multiplier to guarantee earning LCM coins.
  3. Check if the amount of coins spent exceeds or ties LCM and return -1 if so.
  4. Else, print LCM/multiplier

Code: https://codeforces.com/contest/1979/submission/264427427

D:

Hint 1: How much change can one operation do to the string.

Hint 2: look at lengths of consecutive elements.

Hint 3: Is there any equivalent operation in the context of k-complete strings.

Debugging Hint 1: Pay attention to the last consecutive elements.

Sol: 1.Check each length of consecutive elements. 2.If all lengths are k, then output n. 3.If more than one length is not length k or last is greater than k, output -1. 4.Else, if broken length is less than k, set operation length to first c characters where c is the current charcter you are in the string. 5. If broken length is more than k, do the same but for the c — kth character. 6. Do the operation with the designated length or the easier to implement equivalent operation of reversing the remaining characters. 7. Check is string is k-complete. Code: https://codeforces.com/contest/1979/submission/264452915

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

    can you please prove your solution for problem c

    • »
      »
      »
      8 days ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Not really, but it is intuitive that all outputs must be the same, to maximize minimum output relative to input.

  • »
    »
    8 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    how did you come up with the idea of B?

    • »
      »
      »
      8 days ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Came up with answer with sample cases.

      I proved it by looking at first n numbers of each array. If the last k bits of both numbers are same, then for all numbers 0 to 2^k-1, the elements in the array must be the same. As the bits being compared to are the same.

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

      Can i share my not so concrete thoughts.. Let's say the longest common sequence is of length n , a_i = b_j , a_(i+1) = b_(j+1).. and so on. since a_i = i^x and b_j = j^y . Equating and simplifying gives i^j = x^y . For simplicity lets start i = 0 (i know i start from 1 but any (2<<k)-1 can be chosen as i )and find j correspondingly..then u wanna find largest n only...

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

holy cow i lost 55 min to find out i wrote var=- instead of var-=, how the hell i'm working in this sector?

  • »
    »
    8 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I work in mathematics related field, trust me the number of times I have read incorrect "number of balls in a bag" in a probability example is probably infinite.

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

it's really hard for us , honest pupils and newbiews to overcome cheaters

solution problem C was leaked . i didn't solve problem C though.

  • »
    »
    8 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I just became Newbie, solved A and B on my own thought this going good tried my hand on C thought it was tough and then the RESULTS. Only way to over come this cheaters is actually equipping ourselves to solve that particular problem.

»
8 days ago, # |
  Vote: I like it +1 Vote: I do not like it

I predicted solution for B, C using case 4 in test 1

»
8 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Should have solved C first instead of wasting whole time on D

Anyway, can anyone say how to solve D? I tried a lot. My idea was to divide the string into chunks of k size, and handle how many chunks are not of k size, excluding first and last chunk (handled separately).

Here is my submission, if anyone could debug it would be helpful : https://codeforces.com/contest/1979/submission/264475276

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

    Hint: Use hashing

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

    My crumbs of thoughts:

    • If the string is already valid, apply $$$p = n$$$.
    • Due to the nature of the operation, the suffix of it (after $$$p$$$) should already be valid, or at least only invalid at the end (not yet having k similar digits). Iterate backwards, find the first occurence after the last chain of similar digit that causes incorrect pattern, choose a certain $$$p$$$ to keep the suffix correct, apply the operation, and check if the result is valid — if yes then yes, if not then immediately -1.
»
8 days ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

Did more than 13k+ people get B from observation only or was it the case that it's proof was trivial and simple?

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

    I think this was a really nice problem.

    Ai = i xor x

    Bj = j xor y

    If Ai == Bj=> (i xor x) == (j xor y)

    => i xor x xor y == j

    We can replace x xor y = k

    So we want

    i xor k == j

    (i + 1) xor k == (j + 1) and so on.

    And now one nice thing is that if i xor k == j

    And (i + x) xor k == (j + x)

    Then (i xor (i + x)) & k == 0

    The above statement basically means that all the bits changed from i to i+x are unset in k.

    Using this we can find the answer.

  • »
    »
    8 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I think the line of reasoning can be like this:

    1. Look at examples, and see that all answers are powers of 2. Googling "log2(33554432)" gives an integer.
    2. Looking at the notes on the bottom (or by writing a test script), notice that xoring all integers will not cause any duplicates or missing numbers, but numbers are instead shuffled and gradually increase. Choosing $$$x=1$$$ causes adjacent elements to be swapped. If $$$x$$$ is even and $$$y$$$ is odd, then they cannot have more than 1 consecutive equal element. Testing powers of 2, choosing x=8 will swap adjacent blocks of size $$$8$$$, giving $$$[8,9,10,11,12,13,14,15,0,1,2,3,4,5,6,7,...]$$$. If y does not have the same bit set to 1, then any equal subarray between the two can have at most size 8.
    3. This leads to the strategy: pick the smallest bit $$$i$$$ that differs between $$$x$$$ and $$$y$$$, and take $$$2^i$$$. Trying this for the examples, it yields the same results.
    • »
      »
      »
      8 days ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Yes, I got the hint only by noticing that 33554432 is a power of 2, but it was too late as so many people had already submitted.

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

Random approach for C, I don't know if it is legal or not: 264455549.

Hack welcome.

»
8 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Went on solving a completely different problem due to the typo in D

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

Just completed my code for E rip

  • »
    »
    8 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    how did u solve E.

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

      Let's say we have a pair of points x,y and a,b at d manhattan distance, you can notice that the intersection of the pair of points will always be at x+-d/2,y+-d/2. Basically this means that out of the 3 points, atleast 1 pair of points must have a difference of +d/2 or -d/2 for both x and y coordinate. So, for each point out of n points you can just check if one of the 4 points exist or not, if they do, you can find the 3rd point using a set.

      For 3rd point, make two types of set, one set will be indexed by x+y and one by x-y, now you can just binary search for the third point.

      I still haven't accepted my code, so i might be making a mistake

»
8 days ago, # |
  Vote: I like it +14 Vote: I do not like it

I didn't feel that Problem C was easy. How come so many people have solved it? Was there something simple in the problem that I missed?

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

    It is a standard LCM problem.

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

      Please send the link of the problem.

      Also , why was the constraint on N so low (N<=50)?

      • »
        »
        »
        »
        8 days ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        TBH The constraint on N doesn't matter. The LCM sol would've worked if N <=10^5 as well. The constaint on max (a) does.

        My sol: https://codeforces.com/contest/1979/submission/264427427

        • »
          »
          »
          »
          »
          8 days ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          I meant the link of the standard LCM problem. Also then why didn't they set N <= 10^5?

          • »
            »
            »
            »
            »
            »
            8 days ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            By that I meant that it used standard LCM techniques. and I guess N<50, because with high N, it is impossible to create a solution.

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

        So that LCM of array may be small.

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

          I think that depends on the range of values of K.

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

    I also didn't find C obvious.

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

    It was leaked on internet. I wasn't able to do it, but I guess I was close

»
8 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Nice problems

»
8 days ago, # |
  Vote: I like it -15 Vote: I do not like it

Maybe that's skill issue on my side, but problem E is the worst problem I've seen in a year. It's just annoying copy-paste of several cases resulting in 200+ LOC.

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

    Yeah, saw that and gave up on implementing it.

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

    You can try to rotate the grid 4 times and each time looking for one direction only.

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

    My implementation was also terrible. However, it is my own fault. My casework started with two cases and didn't look that bad. Then two turned into four, and four turned into eight. At this point, I was too invested to turn back.

    Looking back, there were multiple ways to eliminate a big chunk of the casework. You can take this opportunity to learn useful techniques and avoid extensive casework in the future. Or you can shift the blame to the setters and fall for the same mistake next time. The choice is yours.

»
8 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Thanks for a good round! Pleased to come back for such a contest.

»
8 days ago, # |
  Vote: I like it 0 Vote: I do not like it

problem 3 was interesting . Enjoy the problem do you?

»
8 days ago, # |
  Vote: I like it 0 Vote: I do not like it

k is divisor of n cost me 4 WA and > 90 min

  • »
    »
    8 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    great passion...

  • »
    »
    8 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Shit, that is an essential hint. I still know how it will help me to reduce the time complexity but alleast now I have something to think lol

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

High rating guys are saying like questions getting relatively tough in nowadays contests,then how come large no of people are able to solve problems upto C,like around 9000 submission on C is insane.It's really getting demotivating.

»
8 days ago, # |
  Vote: I like it 0 Vote: I do not like it

What was the intution for D? My solution was O(N2) ;P

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

    Just use hashing for checking if the string after doing a given operation is equal to 000111000111... or 111000111000111... You have to do like rolling hashing or something like that in order to get the hash of the transformed string at each step

    • »
      »
      »
      8 days ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Well, I didn't understand any comment haha. I guess I got new stuff learn. I'll learn them and now and try again.

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

    Just brute-froced with hashes, I hope they won't FST :p

  • »
    »
    8 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    You notice final string should be K size blocks like 111000111(for k = 3). Then you notice transformation is taking prefix, reversing it and addind to the end of the string. Then it is kinda obvious prefix must end on the first symbol where something gets wrong(because else this "wrong" part will get between good blocks and we can't do anything about it). Also if you see a block with size greater than k you should leave k last symbols of it and take the rest.

  • »
    »
    8 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Trick is to release that only one possible location can be flipped to create a k-complete string.

  • »
    »
    8 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    find the first group whose size is $$$!= \ k$$$
    if group $$$size$$$ is $$$< \ k$$$ consider the group in operation
    if group $$$size$$$ is $$$< \ k$$$ consider first $$$k \ - \ size$$$ elements of group in operation
    then check if the resulting string is good

  • »
    »
    8 days ago, # ^ |
      Vote: I like it +3 Vote: I do not like it
    Somewhat of an explanation
»
8 days ago, # |
  Vote: I like it 0 Vote: I do not like it

How to solve E?

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

    we can notice that if triangle is correct and $$$(x, y)$$$ is one of point of this triangle, than $$$(x + \frac{d}{2}, y + \frac{d}{2})$$$ also belong to this triangle. now all we need is to check that third point exist.

  • »
    »
    8 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Transform cords by [x-y][x+y]. Now distance function is max of dX and dY. Aka the square. Then for point A with cords [X, Y] point B could be [X, Y + D] and C [X + D, (anything between Y and Y + D)]. Same with minus and Y cord.

»
8 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Hello where can I find the explanations and solutions for the questions?

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

Lucky again this round! \(^o^)/

B and C is pure guessing game for me and I guessed it!

And D is also kind of easy, maybe waste some time on debugging :)

  • »
    »
    8 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    No————

    I should have solved E if even luckier, now I submitted my code and got AC after contest QAQ

  • »
    »
    8 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Could you explain how to solve D? Thanks! I feel like I definitely overcomplicated my thinking.

    • »
      »
      »
      8 days ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      The valid k good string must have k 1, then k 0, then k 1... or k 0, then k 1, then k 0... For example, if k=3, then its something like 111000111000... or 000111000...

      If the string is already k good, then you can output n directly. Otherwise, you just need to check the first place it gets invalid(when continuous characters's cnt != k), try to do the operation and check: after the operation, whether the string become a valid k good string or not. If it become valid, then you find the answer, otherwise you can absolutely not find the answer and you can output -1.

»
8 days ago, # |
  Vote: I like it 0 Vote: I do not like it

MathForces!!

»
8 days ago, # |
  Vote: I like it +7 Vote: I do not like it

Codeforces should bring "report cheating" option..so many submissions on B and C.

»
8 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Clicked submit on D with 30 seconds left. It didn't go through. Is this normal? 1st time I've left it that late, so was a bit confused.

»
8 days ago, # |
  Vote: I like it +16 Vote: I do not like it

guessforces, no prove but ac

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

Am I the only one missread the statement of problem F?

Kostyanych tells you the number of vertex $$$v$$$ with a degree at least $$$d$$$

It takes me a long time, to realize that the number of, means the index of $$$v$$$, not how many vertexs $$$v$$$ satisfie the condition...

»
8 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Fingers crossed for a positive delta ... Guessing theorems is kinda interesting :)

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

Problem B was tougher than C, at least for me, back to pupil.

»
8 days ago, # |
  Vote: I like it +1 Vote: I do not like it

Question C, I implemented it using binary search, but can someone explain the monotonicity issue?

https://codeforces.com/contest/1979/submission/264454069

»
8 days ago, # |
  Vote: I like it 0 Vote: I do not like it

éditorial !!!!!!

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

I think tests for D are weak, because +-40000-optimization has passed: 264461313

»
8 days ago, # |
  Vote: I like it 0 Vote: I do not like it

quite curious, did none of the testers notice the typo in problem D?

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

I solved C without lcm. Lets S = 1e9 be the sum of all numbers. Then $$$x_i \cdot k_i > S$$$ for all $$$i$$$. Lets assign $$$\lfloor {x_i = (S + k_i)/k_i} \rfloor $$$ for $$$i \neq n. x_n = S - (x_1+x_2 ... +x_{n-1})$$$. if $$$x_n \cdot k_n > S$$$ we found solution.

  • »
    »
    8 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Same for me, but I used 1e9 + 7 instead. I find out that the bigger the S, the more probability the answer is valid, though I don't know how it works.

    • »
      »
      »
      8 days ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      I had the exact same approach in mind , but somehow I contradicted myself and didn't code it...:(

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

      I have some reasoning behind this. We know that $$$x_i > \frac{S}{k_i} \Rightarrow S > \frac{S}{k_1} + \frac{S}{k_2} \ldots \frac{S}{k_n} \Rightarrow 1 > \sum_{}{\frac{1}{k_i}} (*) $$$ Its not hard to see if (*) true then solution exist. Lets consider solution with smallest sum of $$$x_i$$$. Then $$$x_i$$$ should be equal to least integer that greater than $$$\frac{S}{k_i}$$$.(otherwise we can decrease it). So we can assign $$$x_i = \lfloor (S + k_i)/k_i \rfloor$$$ and choose big enough S.

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

    This reminds me of some math problems :)

    Very elegant. Thanks for sharing.

  • »
    »
    8 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Damn! Such a nice approach. Why didn't I think of this!

  • »
    »
    8 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    so elegant

»
8 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Thanks for a great contest, maybe I am biased but more math related problems helped me solve 3 (when I usually solve 1 or 2). D looked like fun too. Too bad I can't write basic code, xD.

  • »
    »
    8 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    The math helped me too, first I solved C in under 20 minutes.

    • »
      »
      »
      8 days ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      lol I just set $$$x_i$$$ where $$$i$$$ is the index of the minimum $$$k$$$ value to maximum possible ($$$10^9$$$), then set the other $$$x$$$ values accordingly and did a check

    • »
      »
      »
      8 days ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Ohh I wish I had skipped B to attempt C first, Bit Manipulation gives me a headache every time. Hope we get more such math related contests.

»
8 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Finally I got out of 1700

»
8 days ago, # |
  Vote: I like it 0 Vote: I do not like it

I am a little curious and would love to see the stats of blue,cyan,green,and gray users who submitted b,c

»
8 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Thanks for great problems, found D very interesting by solving with hashes

»
8 days ago, # |
  Vote: I like it 0 Vote: I do not like it

I tried my best and solved 3 problems for the first time in div2. I was confused in contest time about why some many people passed the problem C and thought about maybe be easy this time. Now I figure out the real reasons in comments section....

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

Finally becoming expert Thanks for such a great round

:D

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

Thanks iNNNo for the contest! Problems were quite good! I hope everyone was good today!

»
8 days ago, # |
  Vote: I like it +22 Vote: I do not like it
»
8 days ago, # |
  Vote: I like it +4 Vote: I do not like it

$$$B$$$ $$$C$$$ I have no proof I guessed solution , $$$A$$$ semi-proof , only in $$$D$$$ I had solution with proof but not quick enough to submit in time , AC after contest , such a bad contest for me

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

Does anybody know why my submission to B (264416480) shows "Pretests passed" still? Or is it only on my side?

Edit: seems to be fixed now!

»
8 days ago, # |
  Vote: I like it 0 Vote: I do not like it

'C' was something else today!

»
8 days ago, # |
  Vote: I like it 0 Vote: I do not like it

The system testing today felt like a cool breeze bcz of such a short duration after last div3 with 150+ test cases only for problem c.

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

I felt so happy solving C after a long time, only to see later that it had 9k solves :')

Thanks for the contest nevertheless, it was amazing iNNNo and all testers.

»
8 days ago, # |
  Vote: I like it 0 Vote: I do not like it

264415415 My submission for A got WA because I didn't realize (1e9 — 1) = 999999999.0 instead of 999999999. It's so over for me

»
8 days ago, # |
  Vote: I like it +33 Vote: I do not like it

System test is far too weak ....

Even this $$$\mathcal{O}(n^2)$$$ memory and $$$\mathcal{O}(n^3)$$$ time complexity solution can pass the system test, and still I hack it:

https://codeforces.com/contest/1979/submission/264463080

  • »
    »
    8 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    bro wtf, I can up with a O(n) mememory and O(n^1.5) time complexity solution, and thought that would fail.

    • »
      »
      »
      8 days ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      You sure that is $$$\mathcal{O}(n^{1.5})$$$ ? If you connect each pair with an edge, the number of edges can be $$$\mathcal{O}(n^2)$$$ if you see my case, which leads to a $$$\mathcal{O}(n^3)$$$ time complexity to find a circle of $$$3$$$ .

      I'm not sure what you are thinking about, but if what you do is something different, please tell me.

      • »
        »
        »
        »
        8 days ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        No, I am talking abt a solution I came up with, in hindsight it is more like n^5/3

        • »
          »
          »
          »
          »
          8 days ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          That's kind of impressive, but it may still seem hard to pass. I'm really interested in the solution now lol.

          • »
            »
            »
            »
            »
            »
            8 days ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            Trick is there are two solutions. Both hash all points such that it is possible to look up a point in O(1) time.

            If d is small. For each item look around the permiter of all points of distance d, maintain two pointers that are d apart from each other, and see if there is a place where both pointers land on two points. This is a O(nd) solution

            If d is big. Put each point into a box based of (x+y)%d. Brute force ech pair of points, and find third point in O(1). This works in O([40000^2/d]^2). I think.

»
8 days ago, # |
  Vote: I like it +31 Vote: I do not like it

$$$O(n^2)$$$ solution for problem D passed system test

https://codeforces.com/contest/1979/submission/264433381

»
8 days ago, # |
  Vote: I like it 0 Vote: I do not like it

For those who used string hashing brute force in D, how did you compute the hash for a given $$$p$$$ quickly?

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

    Just precompute the hash and reverse for the original string.

    build two possible answer string hashes.

    let's say for input:

    8 4

    two possible answer strings are 11110000 or 00001111

    get hash value of both of these strings.

    Then finally for each p,

    1) get the reverse hash of the string consisting of $$$s_1$$$$$$s_2$$$$$$...$$$$$$s_p$$$

    2) get the forward hash of the string consisting of $$$s_{p+1}$$$$$$s_{p+2}$$$$$$...$$$$$$s_n$$$

    3) merge the two hashes you got from step 1 and step 2 to get the desired hash value of the string if you had choosen this specific p.

    4) Finally, check if the hash you got in step 3 matches with any of the two answer hashes.

»
8 days ago, # |
  Vote: I like it +9 Vote: I do not like it

The problems are interesting, but maybe the system tests are not strong enough

  • »
    »
    8 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Yes, D's system testing is simply not too watery

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

I really messed myself up misreading D lol

I blanked out on the first condition and thought something like 101101001011 would be 4-proper..

»
8 days ago, # |
  Vote: I like it 0 Vote: I do not like it
»
8 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Sorry, but I am unable to find the editorial has it been released yet?

  • »
    »
    8 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I have wriitten a partial editorial in the comments if you are intersted. Covers A-D.

»
8 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Finally able to WOW at CM! Like the problems!

»
8 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Wow such fast updation of rating, just after 1.5hrs of the round!

»
8 days ago, # |
  Vote: I like it 0 Vote: I do not like it

My funny binary search solution to C Link

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

would anyone mind telling me why this linear submission for D resulted in TLE on test 2?

https://codeforces.com/contest/1979/submission/264488685

thanks!

»
8 days ago, # |
  Vote: I like it -6 Vote: I do not like it

D was an absolutely boring problem without any idea underneath

  • »
    »
    8 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I found it useful if you want to practice hashes

    • »
      »
      »
      8 days ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Would it be doable without hashes?

      I have no idea what hashes are and I WA'd problem D

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

        It can be. Notice that unless the string is already $$$k$$$-proper, there's only one $$$p$$$ that might be correct, so apply it and then check the result string.

        More on that at my previous comment.

        My submission in contest (a bit cryptic): 264443229

        • »
          »
          »
          »
          »
          8 days ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          Oh I was trying to do that guess I implemented it wrong rip

      • »
        »
        »
        »
        8 days ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        I've noticed that some people's code in the D issue uses string addition, which I think will cause a timeout, but their code is ac, is the test point not rigorous enough, or is the string concatenation not o(n)?

»
8 days ago, # |
  Vote: I like it +1 Vote: I do not like it

Is it really correct to use binary search for problem C? Why do I feel like there's no monotonicity?

  • »
    »
    8 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    It's quite useless. Even if monotonicity exists, why not print the max value directly (if it works).

»
8 days ago, # |
  Vote: I like it +10 Vote: I do not like it

Tests on problem D are kinda sad. Many brute-force $$$\mathcal{O}(n^2)$$$ solutions passed because they typically come with very light operations such as erasing the first element from a string or comparing two strings. From what I see in the original tests the strongest test that counters this is $$$k=100$$$, but with this test the 'comparison' ends too early so these solutions normally took ~1.5s only.

With $$$k=1$$$ and an almost-$$$k$$$-proper string, dozens of such solutions fail. There are some variations needed for some solutions that has additional checks, or have opposite direction check etc, but the basic pattern is the same.

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

I am unsure how this contest became rated. In Problem B, the original problem statement referred to a subsequence, not a subsegment. Instead of updating the judge's validation code and rejudging the solutions, the problem statement was altered during the contest without any announcements !!!

Artyom123

  • »
    »
    7 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    is there any conflict with solution if it was subsequence actually? as subsegment is also a subsequence.

    • »
      »
      »
      7 days ago, # ^ |
      Rev. 3   Vote: I like it +6 Vote: I do not like it

      Yes, a big difference

      X = 0, Y = 18 (10010)

      Because in case of subsequence you should consider the zeros before the last 1 because if this bit is 1 in both the xoring is 0

      It's a totally different problem

»
7 days ago, # |
  Vote: I like it 0 Vote: I do not like it

I really like the sample testcase for the D problem It actually help me a lot for AC

»
7 days ago, # |
  Vote: I like it -8 Vote: I do not like it

okay so i participated in this contest, and i copied answer from my one account https://codeforces.com/profile/aadarshsingh12345 to my another account https://codeforces.com/profile/zaprodiaq .I have ID/password of both, you can verify whichever way you want.. can i get my rating back ?

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

    Participating with 2 accounts is also not allowed as its unfair because you can check whether your solution is correct in one account and submit on another without penalty.

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

      yes, i did it by mistake.. what are repurcutions ? and can i get rating back ?

      • »
        »
        »
        »
        7 days ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        I don't think so your rating will be back. Don't worry about this contest focus on future contests keep practicing if you improve your skills, ratings will automatically increase so don't worry about it too much.

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

    and this is my second account

»
7 days ago, # |
  Vote: I like it 0 Vote: I do not like it

ObservationForces, worst round i had ever attemepted.

»
7 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Codeforces -> Guessforces

»
5 days ago, # |
  Vote: I like it 0 Vote: I do not like it

much implementation type contest

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

Can anyone tell me why I have used "fflush(stdout)" but it still shows "Idleness limit exceeded"? My Submission

  • »
    »
    2 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    if(!flag)
    {
    	printf("-1\n");
    	fflush(stdout);
    	continue;
    }
    

    Not sure what this did in your main, but this line clearly doesn't follow the interaction rules, thus the interactor would hang indefinitely, causing IL.

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

      Thanks so much. I made a mistake in my understanding of the topic.