Theo830's blog

By Theo830, 4 weeks ago, In English

1594A - Загадка последовательной суммы

Hint
Solution
Code (C++)

1594B - Особые числа

Hint
Solution
Code (C++)

1594C - Сделай их равными

Hint
Solution
Code (C++)

1594D - Количество предателей

Hint
Solution
Code 1(C++)
Code 2(C++)

1594E1 - Раскраска кубика Рубика (простая версия)

Hint
Solution
Code (C++)

1594E2 - Раскраска кубика Рубика (сложная версия)

Hint
Solution
Code (C++)

1594F - Идеальная ферма

Solution
Code (C++)
 
 
 
 
  • Vote: I like it
  • +241
  • Vote: I do not like it

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

Wow the editorial even before the system tests are finished!

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

Thx for the fast editorial! :)

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

Thanks for fast editorial

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

Thank you for the contest

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

Great problem set! Thank you

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

What is the intuition behind B?

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

    for all $$$n \geq 2$$$ and $$$k \geq 1$$$, $$$n^k > \Sigma_{i=0}^{k-1}n^i$$$

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

    Special number is n base number with only ones. So now we have to figure out how to calculate the k-th one And because it is just a matter of play between ones and zeroes, you are like in a binary number, so the k-th number will be the n-th base number with ones on the same spot as k

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

    It was the combination that we can create using powers of a number in increasing order

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

    The numbers that we need to form should have distinct powers and their coefficient should be either 1 or 0. For example if we take n = 4 and k = 17 then 17 = (10) base 4. So this would give an intuition that we need to do something with binary strings or bianry representation of a number K as we need coefficient as 0 or 1 of the powers. Now Lets see what we have to do K = 1 in binary = 1 K = 2 in binary = 10 K = 3 in binary = 11 K = 4 in binary = 100 and so on Now lets see how our answer comes out, As we need to find the Kth special number for base n so suppose that above binary strings were formed with base n and then convert them into their decimal equivalent respectively. For example from test cases where n = 3 and k = 4 so now binary representaion of k is 100. Just take this in base n = 3 so it comes out to be 1*3^2 + 0*3^1 + 0*3^0 = 9 and our answer. Similarly take n = 2 and k = 12. So 12 = 1100 in binary. As our base n is also 2 only answer again converts back to 12. You can further take more examples.

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

Oh , that was realy fast!

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

Testers for this round be like

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

    This is really rude. Testers did their best and gave invaluable feedback. No-one can know every problem that has been created. We are sorry for the situation but testers are not to blame.

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

      dumbasses always exist and they have a problem with the universe itself and nothing can be done about it.

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

      i think this was clearly meant as a joke..?? Keep chill guys

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

Nice contest. Thank you so much!!!!

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

That was really nice contest! Great statements, beautiful solution and very fast edutorial! (even faster than sys tests). I really enjoyed these 2h 15m in this contest, thank you!

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

E2 is pretty interesting I think.

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

Thanks for the fast editorial!

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

Nice round.

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

excellent contest with an interesting problemset , i got very close to solving 3 problems in a div2 for the first time ever , hopefully gonna do it next time :D

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

    same for me too! i was close to solving C and A,B was very interesting :D

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

D was completely copied from INOI 2021... how can you blatantly copy a problem

https://www.codechef.com/INOIPRAC/problems/AMONGUS2

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

    lmao

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

    how did they do this? 1) You highly underestimate the popularity of among us 2) As pointed by someone in the contest announcement comments that it is a little bit trivial for experienced coders to come up with that idea for the problem... check that comment I am lazy to link it.

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

      yeah but they can atleast put some effort..Like change some thing introduce some different parameter exactly copying a statement is too much

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

        We did not copy anything and would never ever do that as it ruins the whole point of problemsetting for both authors and contestants. This was an unfortunate coincidence and we are very sorry for it, we will be taking every measure to avoid it in the future.

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

          I really appreciate you guys effort...as i think it takes a lot of work to prepare a proper contest and i really respect you all for that.. and as for this it would have happened because of some mistake its just that a single problem, like this ruins your guys effort for all the other problems, and for the people participating it gives unnecessary advantage to some...

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

    SUS

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

    why y'all downnvoting its not like i am disrespecting ..I am just stating an obvious fact..Really cant get this community sometimes

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

Can someone please tell me why my solution for E gives wrong answer submission.

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

    Your val variable which stores the total number of nodes has been stored modulo 1e9 + 7. And then you are using val as a power. If you are calculating a^b%MOD then b has to be stored not modulo MOD but rather a different number. In this case I think its 1e9+6 so you had to store val modulo 1e9 + 6.

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

    Your calculation of $$$val$$$ is wrong.

    Fermat's little theorem says $$$a^{p-1} \equiv 1 \bmod p$$$, so you have to calculate the exponent modulo $$$p-1$$$ (in this case, $$$10^9 + 6$$$).

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

      Can you please give an example where this calculation of val fails. I am unable to understand why this gives wrong answer?

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

        $$$3^{10}=59049$$$ mod $$$5$$$ is $$$4$$$. But $$$3^0$$$ mod $$$5$$$ is $$$1$$$.
        I hope now you can come up with a similar example for mod $$$10^9+7$$$.

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

        he is saying that ((x^y)%mod)!=(((x^(y%mod))%mod))

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

Better approach for F, for case s > k:

For each block of size k,

Put, (k-1) continuous ones, and then put (k+1) to avoid subarray with sum k. (1, 1.. k-1 times) (k+1)

This is the basic case, when the farm isn't lucky, all other cases of the farm being unlucky will require higher value of s.

Sum left, after putting all ones = s - n

Extra Sum Required = (n / k) * k (for basic case, described above)

if sum_left < extra_sum, then "YES"

else, "NO"

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

    I had the same idea,but I failed to perfectly prove "when the farm isn't lucky, all other cases of the farm being unlucky will require higher value of s."

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

    Could you plz tell me how to prove it?thx

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

      Firstly you can porve that if only use k blocks,the minimum n is $$$2\times k$$$.

      Then you will find that the way to construct exactly fits the conclusion above,if only use k blocks,the minimum n is $$$2\times k$$$ first.


      The above conclusion can be proved by using Pigeonhole principle.

      If there is a legal way that has n less than $$$2\times k$$$,it should satisfy that for each $$$pre_i\bmod k$$$ must be distinct,because if $$$pre_i\equiv pre_j\pmod k$$$,the subarray $$$[i+1,j]$$$ will be equal to k,($$$pre_i<2k$$$).

      It is impossible because we have $$$n+1$$$ $$$b_i$$$,and $$$n$$$ $$$b_i\bmod i$$$.

      Then we has already proved the conclusion.

      Sorry,I'm not certain about whether my proof is correct.

      Hope it can help you :)

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

Speedforces, and fast editorial.

I missed " if(s==k){ cout << "YES\n"; continue; } " and got F wrong. :(

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

    Can you explain me problem please. I think , I am confuse about what is problem asking.

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

For problem $$$C$$$ it's just enough to check if any of the chars beetwen $$$[n/2+1, n]$$$ (1-indexing) is equal to $$$c$$$ , if it's then the answer is 1. $$$Proof$$$ : Any number between $$$[1, x - 1]$$$ and $$$[x+1, x*2-1]$$$ isn't divisible by x, so every index that isn't $$$x$$$ ,will be changeable. Time complexity — $$$O(N)$$$. My submission — 131189321. Btw, nice contest, thank u!

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

    Thank you for this, was trying to understand this in tourist's code lol

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

    You need to say why it's enough to check $$$[\frac{n}{2}+1, n]$$$, because if $$$x$$$ in $$$[1, \frac{n}{2}]$$$, $$$2x$$$ is in the second half, so in order to use $$$x$$$ it must be that the character at $$$2x$$$ is already correct. So we can use the second half without loss of generality.

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

      Your are right, in order to use x in the $$$[1, n / 2]$$$ we need to check $$$2x,3x..$$$ as well, but instead of checking $$$x,2x,3x...$$$ we just need a maximum $$$yx$$$ such that $$$yx <= n$$$, and if we mark that $$$yx$$$ then every number $$$x,2x,3x,4x..<yx$$$ will be changeable because $$$u$$$ $$$mod$$$ $$$p$$$ $$$!=$$$ $$$0$$$ when $$$u < p$$$. That's why my solution uses number $$$[n/2+1, n]$$$ because there is $$$NOT$$$ any number $$$x$$$ in that range such that $$$2x <= n$$$.

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

    thanks. I got stuck for this for a long time

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

Nice problems. Thank you!

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

Thanks for an amazing contest.I really like problem D and editorial is very good)

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

Video Editorial for Problem D explaining the 2 coloring strategy for bipartite graphs

I solved the original problem in contest so I explain my exact thought process which might help some of you.

Note that I didn't do this contest because I saw D before starting and didn't want to take an unfair advantage.

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

    I know, You are a gem! Keep posting such valuable videos. You will surely have a great future ahead. I follow your videos and they are very helpful. Don't mind about the downvoters, such people always exists.

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

    ak2006 Nice editorial man, keep up the good work. I've seen your content as well it's really educational.

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

Can someone please explain E1?

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

    For the root node you have 6 colours to choose from, and for the rest you have 4. Then, the answer must be 6 * (4 ^ ((2 ^ k) — 2))

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

      got it. Thank you

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

      I did with dp i can have ans if n goes till 1e8 its sometimes very interesting to know that the solution was very diffrent[submission:131209883]

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

    You can have DP solution also which is easy to understand . Each node have to be carefully coloured respecting the given condition in problem .

    My implementation

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

      Thanks a lot. I was looking for this kind of solution which actually does what the questions says to compute the answer.Thanks again!

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

can someone explain me problem B?

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

    Basically, just think like this: For a given n, we need to find the kth integer in base n. Why so? If we need to get to that kth integer, we need to go through all the possible sum of powers of n, which happens to be the process of finding kth integer in base n.

    To understand it clearly, take n = 2.

    And for the solution, look for the set bits of k. And add all the powers of n to the set bit positions.

    Please ask if you need more elaboration on this.

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

      could you please elaborate it more?

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

      to get the kth number in base of n , we need to add to sum of powers in the indexes of set bits , for example in case of n=2 , we are getting all natural numbers , but these numbers have a base of 10 , i am confused with this base thing

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

        For n=2, we are looking at the kth number in base 2, which goes from 1, 10, 11, 100, 101 and so on.

        For n=3, we are looking at it in base 3, so 1, 2, 10, 11, 12 and so on. But:

        the question said that special numbers are sum of different powers, so the base can only contain 0s and 1s, so we will ignore 2, 12, 20 and so on.

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

      You are a gem. Humanity still remains in this world.

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

    just find binary representation of k and then add n^i where i is all set bits of k.

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

How can u think for B . is it number theory or something else ? And how can i be able to solve these type of questions? Pls somebody help me

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

    First, let's see what the array is if n=2.

    We already know that every integer can be represented via a sum of powers of two (and no two powers are equal). This happens because.. well.. every number has a distinct form in base-2, and the base-2 writing actually indicates you on what powers of two to add.

    Now, let's see for n=5 for example, what the array will be

    1 = 1(5) 5 = 10(5) 6 = 11(5) 25 = 100(5) 26 = 101(5)

    And so on.

    Observe that the base-5 writing of these numbers looks very similar to the base-2 writing of 1,2,3,4,5... So, we can state the following:

    If we know the base-2 writing of K, then we can just change the base to n (we keep the number as it was). And from here, I think it's pretty straightforward.

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

      can u please explain me , like for natural nos like 1 2 3 ... , they have a base of 10 , so y are we refering them to as having base of 2 here

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

      would you suggest me what should i learn according to me rating ?

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

    It's very basic properties of positional notation (positional numeral system). Read about it.

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

Nice problems. Thank you!

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

    Yes,B was very nice problem

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

      Hey, can you help me here? I am getting the wrong answer for test case 105, 564.

      Apparently, I am doing something wrong with modulo operator>

      FastReader s=new FastReader(); int t = s.nextInt(); // Number of test cases

      for (int i = 0; i<t; i++) {
              long n = s.nextLong();
              long k = s.nextLong();
              int mod = (int)(1e9 + 7);
              long ans = 0;
      
              while (k > 0) {
                 int x = 0;
                 long sum = (long)Math.pow(2, x);
                 while (sum < k) {
                   x++;
                   sum = (sum%mod + (long)Math.pow(2, x)%mod)%mod;
                 }
                 k = (k%mod-(long)Math.pow(2, x)%mod + mod)%mod;
               ans = (ans%mod + (long)Math.pow(n, x)%mod)%mod;
              }
      
              System.out.println(ans%mod);
          }
      • »
        »
        »
        »
        2 weeks ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        I think you should not use Math.pow(). It uses float or double type inside and causes precision loss. Not good at Java, just as my personal opinion.

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

Excellent contest, System testing was also awesome :D

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

Maybe 1594C has an $$$O(|s|)$$$ method?

Here is my solution.

First, if we have a minium i such that $$$s_i,s_{i+1},...,s_n \neq c$$$ and the answer is $$$1$$$ operation with a certain $$$x$$$, it is obvious that $$$s_x = c$$$ and $$$\forall k \in N_+ \wedge kx \leq n, kx < i$$$.

If $$$i = 1$$$, we can't find that $$$x$$$.

If $$$i \neq 1$$$, let $$$a = i - 1$$$.

We can prove that if $$$a$$$ doesn't match the conditions above, we can't find that $$$x$$$. If $$$a$$$ doesn't match the conditions above and there exists $$$x$$$ such that $$$x < a$$$, $$$i \leq 2a \leq n$$$ and $$$\exists k \in N_+, a < i \leq kx \leq a + x < 2a \leq n$$$, so $$$x$$$ doesn't match the conditions above.

And if and only if $$$2a > n$$$, $$$a$$$ can be the $$$x$$$, because $$$2a > i$$$, $$$\forall i \in N_+ \wedge i < a, i$$$ is not divisible by $$$a$$$ and only at this time $$$\forall k \in N_+ \wedge k > 2, ka > n$$$.

Then we can use $$$O(|s|)$$$ to find this $$$a$$$ and output it, solving the situation when the answer is $$$1$$$ operation with a certain $$$x$$$.

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

Great Editorial!!

One can check this youtube channel for video editorials: Link

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

B harder than E1 !

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

upvoted

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

regarding C — "Make Equal" :

Can someone please tell me where my code gives the wrong output? The wrong answer is for test case 74 of preset 2 but I'm not able to see what it is. I've been trying to find my mistake for more than an hour.

idea — I tried to check if there is any index > n/2(n/2 + 1 for even numbers ) that has the correct character. If yes, then the required number of x is one. else 2.

Link to the submission

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

    I think your for loop should go from i = 2 to i <= n. You have written i < n. Plz check.

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

      My apologies, I mistakenly put the wrong code earlier. I have put my original code now. can you please take a look again /\

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

      can you please see my problem submission for problem B it is giving tle...

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

    you can link a submission or put the code in a spoiler

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

    check this test case: 1 13 b aaaaaaabaaaaa

    output :7 answer : 8

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

Contest was actually good, I coded F in O(min(s — n, n) / k), it passed pretests, then I changed in to O(1) but after the round it still works. Strange tests to be honest. Here is my solution https://codeforces.com/contest/1594/submission/131243246

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

    Actually yes, your code gives TLE on this test

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

I have a solution in problem C that runs in O(|s|) time complexity Firstly, I'll check if all characters in the string are equal to C and if so I will print 0(no need to do any operations).

Next, I check if I can use 1 operation only and construct a good string at the end by finding an index such that (s[i] == c) and (i * 2 > n) and doing 1 operation using this index i. Let's divide proving the second step into two parts: Proving that this operation is enough & Proving that if such an index doesn't exist then simply we can't change the whole string to be equal to c in 1 operation. 0) Choosing index i means that all indices <i are changed to C(since none of them are divisible by i) and since 2 * i>n then all indices between i+1 and n are changed to C too.

1) The chosen index must have s[this_Index]=c because we are always not changing any of its multiples including itself and building on this fact we need to choose an index i such that all characters on indices that are multiples of i(if any exists) are equal to c. The thing is that the (largest multiple of i that is <=n) *2 must always be >n hence that an index such that s[this_index] is equal to c and this_index * 2 >n must exist or there will be no way to do it in 1 operation.

Finally, if I didn't find such i that can fix the string in 1 operation then I will fix the string in 2 operations by making x = n and this will make all of s[i] = c for 1<=i<n and then use x = n-1 to make s[n] = c

My solution: https://codeforces.com/contest/1594/submission/131192419

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

Easier solution for 1594F - Ideal Farm.

for (int q = 0; q < Q; q++) {
	ll S = nl();
	ll N = nl();
	ll K = nl();

	if (S==K)
		cout << "YES\n";
	else if (S < K || S >= N+(N/K)*K)
		cout << "NO\n";
	else
		cout << "YES\n";
}
  • »
    »
    3 weeks ago, # ^ |
      Vote: I like it +9 Vote: I do not like it

    lol I sent the same, now I dont care about the right solution, I am just interested in tests' weakness

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

    Can you explain it a little? I saw the exact same solution somewhere else but couldn't understand. I have read the editorial though and I understand editorialist's solution. edit — : I think I got it now, this person explained it nicely. comment link

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

I liked problem B. Very nice contest.

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

I think it's just simply one of the most interesting contest i've written here.

Thanks!

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

Can you please explain the end of the tutorial of F? I. e.:

"Let m be the maximum number of elements that we can take.

We go through the last k elements ([s−k+1,s]) and we count the number of elements that have the same modulo k.

For each element in this range, if there are odd elements that have the same modulo, we can't take all of them because for every element x that we add in pre that we also add x+k to b. Thus one element would have a x+k out of range.

Therefore we count all the elements that have odd elements with the same modulo k and subtract them from s+k to find m."

I can't understand literally anything from here.

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

    $$$m = $$$ the maximum number of elements that we can take among the $$$[1,s + k]$$$. (We want to make $$$pre$$$ of size $$$n$$$ and $$$b$$$ of size $$$n+1$$$).

    We only need to build $$$pre$$$ but there should not same elements in $$$pre$$$ and $$$b$$$.

    We go through the last $$$k$$$ elements ($$$[s−k+1,s]$$$) and we count the number of elements that have the same modulo $$$k$$$.

    For each element in this range, if there are odd elements that have the same modulo, we can't take all of them (and add them to $$$pre$$$) because for every element $$$x$$$ that we add in $$$pre$$$ that we also add $$$x+k$$$ to $$$b$$$. Thus one element would have a $$$x+k$$$ out of range ($$$x + k > s + k => x > s$$$ which is obviously wrong) .

    $$$pre: $$$

    ($$$[s−k+1,s]$$$)

    ($$$[s−3k+1,s-2k]$$$)

    $$$...$$$

    $$$b: $$$

    ($$$[s+1,s+k]$$$)

    ($$$[s−2k+1,s-k]$$$)

    $$$...$$$

    Therefore we count all the elements that have odd elements with the same modulo $$$k$$$ and subtract them from $$$s+k$$$ to find $$$m$$$.

    I hope that now it's clearer.

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

    The solution means that we need to allocate the elements of $$$[1, s + k]$$$ into $$$2n + 1$$$ positions (some elements may not be allocated).

    Firstly we can observe that for every element $$$x$$$ assigned to pre there's a corresponding $$$x + k$$$ assigned to b, this means that the numbers with the same modulo $$$k$$$ must be allocated even number times. So we can divide all the numbers with the same modulo $$$k$$$ into the same group.

    Noticed that if there is an odd number of elements in a group, then the group cannot be fully allocated, so the total number of elements that can be allocated must be subtracted by one. It is easy to figure out how many groups of odd size we have, we can subtract the number of groups with odd size from $$$s + k$$$ finally we will get the number of elements that we can allocate.

    But note that $$$k$$$ must initially be assigned to b (because $$$b[0]=pre[0]+k=0+k=k$$$ ), so the number of groups in which module $$$k$$$ is equal to $$$0$$$ must be subtracted by $$$1$$$.

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

      The last paragraph is wrong. When the modulo k is 0 then it's like we take the element 0 in pre and k at pre. Therefore, you again have to subtract 1 when there are odd numbers that have 0 modlulo k.

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

        I just consider the elements in $$$[1,s+k]$$$, so the element $$$0$$$ doesn't count.

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

in problem D i submit thiscode but it recieved wrong answer it use directed edges but when i convert edges to bidirectionl it get accepts codewhy this happens?

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

    Bruh, how can you still be expert with that amount of solved problems lmffaaaoooo

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

    I have similar query as well. Did you get to know the reason why this happened?
    Code with Directed Edges: Directed
    Code with Undirected Edges: Undirected

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

      because if 2 says 3 is a liar and 1 says 3 is not a liar then see from first two possibilities are there for 2 and 3 they r 2 is liar while is not or 2 not liar and 3 is. Based on this we can get information about 1 since 1 says 3 is not a liar then if 3 is a liar then 1 is also (see the reverse edge) and if 3 is not a liar then 1 is also not. Thus if we have 2->3 and 1->3 this can be rewritten as 2->3 and 3->1 hence bidirectional

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

        yeah, I got your point. Thanks for the explanation. Can you please further tell, why solving with a directed graph gives a wrong answer. I mean, if you have some counter case.

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

          1 4 3 1 2 imposter 3 2 crewmate 4 2 imposter

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

My feedback -
I just read F and despite multiple readings couldn't figure out what exactly it means. I tried guessing but couldnt come up with something. I wasnt participating but just decided to look at F in middle of the contest, but would have submitted something on F if I had a soln.
- Animal pen doesn't make any sense. Something which animals eat could have been better.
- There is no clarification if there are total n pens or if there are n types of pens with infinite quantities of each type.
- What exactly do you mean by "empty pen"? You haven't defined what exactly is "empty pen"/"non-empty pen" is.
- "all animals in all pens". I tried reading it as "you have to distribute n pens among k animals such that ....." Couldn't come up with something to fill those .... here.

Although authors tried to give a formal definition? But a more formal definition would have been better. Formal definitions should be absolutely formal just like the definition after "The problem is the same as" in the editorial. Someone who just reads it should be able to grasp what is being asked and it shouldn't involve references to the story.

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

    Did you perhaps misunderstand what pens are? [Pen](https://en.wikipedia.org/wiki/Pen_(enclosure))

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

      Yeah. I did. Thanks.

      Sorry for my bad English :P

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

      I've been living in the UK for three years and I've never heard the word 'pen' in this context. Anyone who knows that pen is a thing to write with should be careful about using a word with double meaning...

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

        Then what is the word for pen which the UK citizens use? Animal pen is quite common usage.

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

          I think they use the word "pen", but to use it, you must talk about animal pen, which nobody does among city citizens.

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

        You guys never came across this?

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

Me last night on problem A:

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

    I done the same!!! LOL

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

    What does it function means?

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

      You mean "ctz"? "Count trailing zeros (in binary)", i.e., $$$\operatorname{ctz}(n) =$$$ largest integer $$$s$$$ such that $$$2^s$$$ divides $$$n$$$. C++ has it in supported architectures as __builtin_ctz, or there is an old algorithm using bitshifts and compares which is essentially hand-coded binary search.

      Or you can always fall back on the naive $$$O(\log n)$$$ approach.

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

I thought problem E2 was really cool.

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

    can u please explain me the approach i cannot solve it and also do not got it from editorial

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

      The idea is that if we have a node $$$x$$$, whose color we arbitrarily fix, and nothing in the subtree of $$$x$$$ is fixed (in the sense that there are no restrictions on nodes below $$$x$$$), then we have $$$4^{sz - 1}$$$ ways to fill out the subtree. There are a lot of nodes of this type; in fact, 99.999% of the nodes are nodes of this type.

      There are also other types of nodes: nodes in which some child or child of a child, etc is fixed. These cases are a little bit harder and to do so, we can just memoize on its two left and right children. Fix the color on the left child, fix the color on the right child, and then take the sum of the products of sub[left] and sub[right].

      131252148

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

A nice round, thanks for the fast editoria!!!

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

In problem c,I set p is the c's latest position.if p>n/2,only operation ones,x=p,otherwise,operation twos,x=n-1 and x=n,but I wrong.I can't understand why wrong.131226305

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

    There is no assignment of 0 when defining P in your code. I think it may be an error here.

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

So fast!! Best ever!

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

Good thing problem B was from aime lol.i got positive delta.best round ever.easy google

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

in problem E1, "a white node can not be neighboring with white AND yellow nodes", I belive the preposition used should be "or" instead of "and". I only read the formal statement, got confused, and ended up solving another problem for half an hour before realizing how dumb I am :(

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

I think problem F's difficulty at most be *1800.

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

    I still don't know solution. I didn't read editorial yet. Only for problems I solved.

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

I think in problem C O(nlog(n)) can be reduced to O(n).

Notation: n=|s|; c=required char to be set
If all s[i]==c then ans=0
Else if at any of these positions (n/2 + 1,....,n), s[i]==c, then using x=i we can set all the rest positions in just 1 operation
Otherwise, all of these positions (n/2+1,....,n) will have s[i]!=c. So, they can't be changed in just one operation. So, answer will be 2 with x= n-1 , n

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

why rating point for this contest is too low? 5 problem only for 7pts :'(

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

Thanks a lot!

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

can some one please tell me how to solve e2 i am unable to get it from editorial(my mistake not of editorial)

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

    In short, whole idea is to forget about whole tree and find out how many ways to color nodes which are on paths from root to already-colored. Then, multiply by 4 to the corresponding power. And to find out first thing, make dp[v][c] which would tell how many correct ways to color vertex v into color c and its subtree in any colors (without taking into account nodes we're not interested).

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

Your text to link here... I tried to solve question C but I got the wrong answer. I read the editorial and my approach was similar to it. Can some pls suggest to me what I missed in my soln.

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

I have finsolved B. But I don't understand why k-th element doesn't equal k? For example, for module 7 and n = 3 we have sequence [0, 1, 2, 3, 4, 5, 6]. What special in 1e9+7?

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

Great set of problems with good underlying logics.

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

Can someone explain to me Question C?

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

Can someone explain how to code problem E1 in java? I have understood the logic but I'm getting TLE error. Please help, thanks in advance.

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

    You should use your own power function. You can see how I coded it in the editorial to implement it yourself.

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

More contest at 18 05

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

Great Contest. Nice set of problems!

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

i was stuck at B so i didn't looked at C oh man C was a easy one

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

There is O(s) solution of problem C — Make Them Equal
Explanation:
Iterate over the whole string and if the i-th is K then push the index to a vector named good.
As we iterating from 0 to n-1, the good is sorted.
now if the greatest element aka index of good is greater or equal to the half of the size of the string, then we can prove that this is possible in 1 operation

if ( good[good.size() — 1] >= s.size()/2 ) => 1 operation

the except cases are same as the Editorial.
Here is my submission:
131204546

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

in problem F: Why are we going through the last k elements?

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

    I have no idea what editorial is telling about but this should help:

    Our goal is clearly to construct (judge if this is possible) prefix-sum array such that it has length n + 1, first element is 0, last element is s, the array is strictly increasing and the array doesn't have x and x + k simultaneously for any x (then and only then we would have subarray with length exactly k).

    Instead we will try to construct longest possible such array (and if it's length would be > n + 1, we can easily "shrink" (decrease it's length) it to obtain construction of array of length exactly n + 1).

    Now for each rem = 0, 1 .. k-1 let's look how many elements at most of this (prefix) array can be equal to rem MOD k.

    Clearly for particular "rem" one of optimal constructions is rem, 2k + rem, 4K + rem and so on. So you only need to count how many numbers in interval [0, s] are equal to rem MODULO k. Suppose their count is x. Then you can take at most (x + 1) / 2 of them to the prefix array. Do this for every rem = 0,1 .. k-1 and you will know what is the greatest possible length of this prefix array. The only corner case is when s == k, because you are always forced to contain 0 and s in the prefix sum array as first and last elements.

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

      Could you please explain why could we easily "shrink" this array?

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

        Ok, I figured it out. The elements need to have the same rem, and their difference is already 2K. It would be just greater if we shrink.

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

      probably >=n+1. Thanks for the explanantion.

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

    Because if we don't put the last k elements in pre, b will not have the elements from s to s+k.

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

Those two code are same.The only difference between them is variable type, int and long long int. But one got accepted, another got runtime error. For int type variable got AC, long long int got RE. why ?

AC code: 131311594 RE code: 131309828

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

Finally become expert QWQ. Continue learning!

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

Video Solutions

A B C

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

I have a doubt in D: My solution is giving Runtime error while using vector of map for storing graph and works fine when I use vector of vector. Can anyone help? Here is link to my solution.

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

can anybody see my solution for problem B, it is giving TLE...i don't know why https://codeforces.com/contest/1594/my

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

Can anyone plz explain B without binary way?

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

I think my solution to the problem C is easier :)

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

    Can you explain the intuition behind your solution ?

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

How to solve D by DSU ?

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

let the value of k be greater than 64. Can we still use this-> (1LL<<k)??

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

bad editorial

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

    Can you be more specific about what you didn't understand?

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

      If you could write comments on your code explaining why you wrote this specific line then it might be easier to understand your code.

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

Thanks for the contest. Nice problems and fast editorial!

Question: is it possible to solve B without using bitmasks?

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

can anybody please explain why is my solution not working for problem d? solution link : https://codeforces.com/contest/1594/submission/131297133

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

    I am also getting same verdict on testcase 2 line 40 :(

    Update: Try this case 4 3 1 2 imposter 3 4 crewmate 2 3 crewmate

    Your code will give -1. But actual ans is 3.

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

Fun fact this is the third problem called Make Them Equal

1154B - Make Them Equal

1417D - Make Them Equal

1594C - Make Them Equal

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

In problem D, What is the intuition behind connecting fake node with A and B nodes if person A said that B is a crewmate.

Also, how to do the problem with dp / dsu as it is there in one of the problem tags

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

    because if person A said that B is a crewmate, then A and B must belong to the same type, so if there is fake node between them, when we use dfs to paint node, they must be painted the same color.

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

After hours of reading the Problem F editorial, I still can't understand the last part about finding M. If someone else has the same problem as me, this might help.

Suppose we have distributed the array A. Let's build a prefix sum Pre[i] = Pre[i-1] + a[i]. Pre[i] is distinct and increasing. If there are i, j such that Pre[i] = Pre[j] + k then there must exist a segment on A which it's sum equal to k.

Now we want to check if there is a way to build Pre[i] that does not exist Pre[i] = Pre[j] + k. Pre[i] is distinct and Pre[i] is a value in range [1...S]. If we chose Pre[i] = x then we can not chose x+k, if we don't chose x+k, we can chose x+2*k .

For every p = [0...k-1] (remainder when divided by k), we can take from S number x = t*k+p (t <= S-p/k). The maximum way to choose number x(s) is t=(0, 2, 4, 6,...). Except p=0, the best way to choose is t=(1, 3, 5, 7,..) since Pre[i] > 0. For every p, the maximum way to choose x (or t) is Tp.

Now, M = sum of all Tp (p=[0...k]). If M>=n then there is a way that does not exist Pre[i] = Pre[i]+k, the answer is NO, otherwise, the answer is YES.

You don't have to count Tp separately, use some modulus and divine operation and you can get M easily.

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

Thank you for the contest

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

In problem E2, I use priority_queue to process node from bottom to the top, but it lead to TLE in case9, here is my code, anyone can tell me why it fail?

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

Can anyone help me figure out why my solution is giving RTE in problem D? I am using DSU and small to large merging. 133162809

»
42 hours ago, # |
  Vote: I like it 0 Vote: I do not like it

https://codeforces.com/contest/1594/submission/133176237 why I am getting Wrong answer. which case i haven't considered.

  • »
    »
    38 hours ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    It looks like you only use operations for $$$x = 2$$$ or $$$x = 3$$$. In this case, for example, you cannot change the $$$6$$$-th position in the string, because $$$6$$$ is divisible by both $$$2$$$ and $$$3$$$.

»
27 hours ago, # |
  Vote: I like it 0 Vote: I do not like it

DIV 2. B The test case explained for n=3 has 1 and 3 in the sequence but how can we write 1 and 3 as the sum of two different powers of n???