iNNNo's blog

By iNNNo, history, 5 months 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
  • +179
  • Vote: I do not like it

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

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

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

Look who's doing purple testing

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

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

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

Hoping +ve Delta

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

    Forget about +ve delta dude. CF is brutal.

    • »
      »
      »
      5 months 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

      • »
        »
        »
        »
        5 months 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

      • »
        »
        »
        »
        5 months 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.

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

        how did you come up with the idea of B?

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

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

          • »
            »
            »
            »
            »
            »
            5 months 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

        • »
          »
          »
          »
          »
          5 months 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)

          • »
            »
            »
            »
            »
            »
            5 months 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

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

              Or that divides their bitwise XOR.

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

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

              • »
                »
                »
                »
                »
                »
                »
                »
                5 months 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.

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

            How is that derived?

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

        Not as close as me :(

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

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

      • »
        »
        »
        »
        5 months 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.

      • »
        »
        »
        »
        5 months 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

        • »
          »
          »
          »
          »
          5 months 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);
          
          • »
            »
            »
            »
            »
            »
            5 months 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 ?

            • »
              »
              »
              »
              »
              »
              »
              5 months 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$$$.

              • »
                »
                »
                »
                »
                »
                »
                »
                5 months 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.

            • »
              »
              »
              »
              »
              »
              »
              5 months 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.

              • »
                »
                »
                »
                »
                »
                »
                »
                5 months 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.

                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  5 months 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.

                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  5 months 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.

                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  5 months 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.

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

                  hmm got it. thanks

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

      What is +ve delta,dude?

      • »
        »
        »
        »
        5 months 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.

»
5 months ago, # |
  Vote: I like it -17 Vote: I do not like it

I'm Salah Eldeen Al-Ayoubi

»
5 months 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? ;)

  • »
    »
    5 months 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?

    • »
      »
      »
      5 months 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".

  • »
    »
    5 months 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...

  • »
    »
    5 months 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).

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

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

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

Can't wait!

»
5 months 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 :)

»
5 months ago, # |
  Vote: I like it -51 Vote: I do not like it

hope to reach specialist this round <3

»
5 months ago, # |
  Vote: I like it -16 Vote: I do not like it

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

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

Is this round mathforces or algoforces?

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

Good luck to everyone except no one!

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

Interactive tasks may occur in this round

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

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

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

Waiting for starship launch as well as div2

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

Hoping +ve delta after 2 bad contest for me

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

Good Luck Have Fun!!

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

sorry

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

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

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

good luck everyone:)

»
5 months 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

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

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

    • »
      »
      »
      5 months 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])

      • »
        »
        »
        »
        5 months 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

      • »
        »
        »
        »
        5 months 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".

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

mathforces

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

Samplecase forces ,or maybe I need a lot more practice

  • »
    »
    5 months 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

    • »
      »
      »
      5 months 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.

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

My solution to C without LCM 264475190

  • »
    »
    5 months 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

    • »
      »
      »
      5 months 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

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

Guessforces

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

Hint for C anyone? ;)

  • »
    »
    5 months 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)

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

    it involves basic math

  • »
    »
    5 months 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

    • »
      »
      »
      5 months 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

      • »
        »
        »
        »
        5 months 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

    • »
      »
      »
      5 months 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
    • »
      »
      »
      5 months 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

  • »
    »
    5 months 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.

»
5 months 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.net/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.net/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.net/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.net/contest/1979/submission/264452915

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

    can you please prove your solution for problem c

    • »
      »
      »
      5 months 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.

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

    how did you come up with the idea of B?

    • »
      »
      »
      5 months 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.

    • »
      »
      »
      5 months 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...

»
5 months 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?

  • »
    »
    5 months 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.

»
5 months 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.

  • »
    »
    5 months 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.

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

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

»
5 months 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.net/contest/1979/submission/264475276

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

    Hint: Use hashing

  • »
    »
    5 months 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.
»
5 months 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?

  • »
    »
    5 months 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.

  • »
    »
    5 months 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.
    • »
      »
      »
      5 months 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.

»
5 months 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.

»
5 months 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

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

Just completed my code for E rip

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

    how did u solve E.

    • »
      »
      »
      5 months 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

»
5 months 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?

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

    It is a standard LCM problem.

    • »
      »
      »
      5 months 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)?

      • »
        »
        »
        »
        5 months 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.net/contest/1979/submission/264427427

        • »
          »
          »
          »
          »
          5 months 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?

          • »
            »
            »
            »
            »
            »
            5 months 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.

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

        So that LCM of array may be small.

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

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

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

    I also didn't find C obvious.

  • »
    »
    5 months 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

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

Nice problems

»
5 months 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.

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

    Yeah, saw that and gave up on implementing it.

  • »
    »
    5 months 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.

  • »
    »
    5 months 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.

»
5 months 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.

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

problem 3 was interesting . Enjoy the problem do you?

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

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

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

    great passion...

  • »
    »
    5 months 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

»
5 months 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.

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

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

  • »
    »
    5 months 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

    • »
      »
      »
      5 months 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.

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

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

  • »
    »
    5 months 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.

  • »
    »
    5 months 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.

  • »
    »
    5 months 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

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

How to solve E?

  • »
    »
    5 months 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.

  • »
    »
    5 months 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.

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

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

»
5 months 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 :)

  • »
    »
    5 months 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

  • »
    »
    5 months 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.

    • »
      »
      »
      5 months 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.

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

MathForces!!

»
5 months 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.

»
5 months 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.

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

guessforces, no prove but ac

»
5 months 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...

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

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

»
5 months 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.

»
5 months 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.net/contest/1979/submission/264454069

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

éditorial !!!!!!

»
5 months 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

»
5 months 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?

»
5 months 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.

  • »
    »
    5 months 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.

    • »
      »
      »
      5 months 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...:(

    • »
      »
      »
      5 months 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.

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

    This reminds me of some math problems :)

    Very elegant. Thanks for sharing.

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

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

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

    so elegant

»
5 months 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.

  • »
    »
    5 months 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.

    • »
      »
      »
      5 months 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

    • »
      »
      »
      5 months 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.

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

Finally I got out of 1700

»
5 months 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

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

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

»
5 months 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....

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

Finally becoming expert Thanks for such a great round

:D

»
5 months 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!

»
5 months ago, # |
  Vote: I like it +22 Vote: I do not like it
»
5 months 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

»
5 months 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!

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

'C' was something else today!

»
5 months 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.

»
5 months 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.

»
5 months 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

»
5 months 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.net/contest/1979/submission/264463080

  • »
    »
    5 months 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.

    • »
      »
      »
      5 months 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.

      • »
        »
        »
        »
        5 months 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

        • »
          »
          »
          »
          »
          5 months 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.

          • »
            »
            »
            »
            »
            »
            5 months 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.

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

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

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

»
5 months 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?

  • »
    »
    5 months 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.

»
5 months 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

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

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

»
5 months 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..

»
5 months ago, # |
  Vote: I like it 0 Vote: I do not like it
»
5 months 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?

  • »
    »
    5 months 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.

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

Finally able to WOW at CM! Like the problems!

»
5 months 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!

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

My funny binary search solution to C Link

»
5 months 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.net/contest/1979/submission/264488685

thanks!

»
5 months ago, # |
  Vote: I like it -6 Vote: I do not like it

D was an absolutely boring problem without any idea underneath

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

    I found it useful if you want to practice hashes

    • »
      »
      »
      5 months 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

      • »
        »
        »
        »
        5 months 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

        • »
          »
          »
          »
          »
          5 months 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

      • »
        »
        »
        »
        5 months 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)?

»
5 months 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?

  • »
    »
    5 months 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).

»
5 months 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.

»
5 months 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

  • »
    »
    5 months 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.

    • »
      »
      »
      5 months 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

»
5 months 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

»
5 months 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.net/profile/aadarshsingh12345 to my another account https://codeforces.net/profile/zaprodiaq .I have ID/password of both, you can verify whichever way you want.. can i get my rating back ?

  • »
    »
    5 months 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.

    • »
      »
      »
      5 months 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 ?

      • »
        »
        »
        »
        5 months 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.

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

    and this is my second account

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

ObservationForces, worst round i had ever attemepted.

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

Codeforces -> Guessforces

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

much implementation type contest

»
5 months 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

  • »
    »
    5 months 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.

    • »
      »
      »
      5 months 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.