Блог пользователя yash_daga

Автор yash_daga, история, 5 месяцев назад, По-английски

We invite you to participate in CodeChef’s Starters142, this Wednesday, 10th July, rated for till 5-Stars(ie. for users with rating < 2200).

Time: 8:00 PM — 10:00 PM IST

Joining us on the problem setting panel are:

Note: Some problems have subtasks

Written editorials will be available for all on discuss.codechef.com. Pro users can find the editorials directly on the problem pages after the contest. The video editorials of the problems will be available only to Pro users.

Also, if you have some original and engaging problem ideas, and you’re interested in them being used in CodeChef's contests, you can share them here. Hope to see you participating.

Good Luck!

  • Проголосовать: нравится
  • +91
  • Проголосовать: не нравится

»
5 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Hoping no problems will be there containing Game Theory. IMHO, CC should give Game Theory some rest.

»
5 месяцев назад, # |
  Проголосовать: нравится +24 Проголосовать: не нравится
»
5 месяцев назад, # |
  Проголосовать: нравится +14 Проголосовать: не нравится

Another week another contest not rated for 7* coders :sob;

»
5 месяцев назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

Amr Harb is the best.

»
5 месяцев назад, # |
  Проголосовать: нравится +8 Проголосовать: не нравится

Whenever you have subtasks you must have separate samples where sample 1 fits the constraints of subtask 1, sample 2 fits the constraints of subtask 2, etc.

»
5 месяцев назад, # |
  Проголосовать: нравится +2 Проголосовать: не нравится

SpeedChef

»
5 месяцев назад, # |
  Проголосовать: нравится +4 Проголосовать: не нравится

Was anyone able to solve Sum of Xors(SMXR)?

I thought it would be just (N*M*3)/2 but that's wrong, can someone please explain?

  • »
    »
    5 месяцев назад, # ^ |
      Проголосовать: нравится +3 Проголосовать: не нравится

    Try to think when K=6 and N=M=4.

    • »
      »
      »
      5 месяцев назад, # ^ |
        Проголосовать: нравится +6 Проголосовать: не нравится

      That was such a random guess, it is not a coding problem.

      • »
        »
        »
        »
        5 месяцев назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        What will happen when K is of 4*x+2 form? Do you think this is random guessing?

        • »
          »
          »
          »
          »
          5 месяцев назад, # ^ |
          Rev. 2   Проголосовать: нравится +3 Проголосовать: не нравится

          I looked at $$$N=M=4$$$, $$$K=6$$$ and immediately guessed that $$$F(K)=0$$$ for all $$$K$$$ except $$$2$$$ and $$$NM-2$$$, without proving that such a 'closed tour' actually exists.

          • »
            »
            »
            »
            »
            »
            5 месяцев назад, # ^ |
              Проголосовать: нравится 0 Проголосовать: не нравится

            As a matter of fact, one does not need a closed tour of alternating row and column moves for the construction, which further shows that my guess was not supported by much thought. For example, $$$N=M=6$$$, $$$K=10$$$ has a construction that is not a connected tour:

            ##....
            .##...
            #.#...
            ...##.
            ...##.
            ......
            
          • »
            »
            »
            »
            »
            »
            5 месяцев назад, # ^ |
              Проголосовать: нравится 0 Проголосовать: не нравится

            That may be your experience.

            • »
              »
              »
              »
              »
              »
              »
              5 месяцев назад, # ^ |
              Rev. 2   Проголосовать: нравится +13 Проголосовать: не нравится

              You know most people are guessing and not even trying to prove when accuracy is 8.2% (Div. 1), 1.23% (Div. 2), 0.6% (Div. 3), and 0.84% (Div. 4).

    • »
      »
      »
      5 месяцев назад, # ^ |
      Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится

      The comment below shows the correct arrangement not the one I cooked up.

    • »
      »
      »
      5 месяцев назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      Why is the sample test cases promoting the answer (n*m*3)/2? It would have been better if you had included similar corner cases in the samples.

  • »
    »
    5 месяцев назад, # ^ |
      Проголосовать: нравится +3 Проголосовать: не нравится

    You can get $$$F(X) = 0$$$ for $$$K \equiv 2 (\mod 4)$$$ for some constructions.

    For example, consider $$$N = 4, M = 4, K = 6$$$

    ##..
    .##.
    #.#.
    ....
    
»
5 месяцев назад, # |
Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится

[WRONG]

  • »
    »
    5 месяцев назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Sorting the array completely breaks the number of $$$[L, R]$$$ that satisfy the equation.

    For example consider the input:

    $$$n = 6, x = 1, A = [8, 8, 4, 4, 8, 8]$$$

    In this array, only $$$i = 3, j = 4$$$ satisfy the equation, so $$$F(L, R) = 1$$$ for all $$$1 \leq L \leq 3, 4 \leq R \leq 6$$$ giving an answer of $$$9$$$.

    However, if you sort the array, it becomes $$$[4, 4, 8, 8, 8, 8]$$$ which has $$$F(L, R) = 1$$$ for $$$L = 1, 2 \leq R \leq 6$$$ giving an answer of only $$$5$$$.

»
5 месяцев назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

Not a fan of "knowledge-based" problems like "Number Hunt". Its pretty much just "Do you know that the prime gap is small even at $$$10^9$$$?".

Maybe it makes sense to put it in Starters since they are meant to be "educational" contests, but it still feels out of place.

»
5 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

I think anyone who solved this problem before can solve today's sum of Xor in 2-3 minutes

»
5 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Today's E (LENGTHX) , its editorial was based on segment trees , any suggestions where to learn seg trees from ?

»
5 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

For xor sum , to prove all even $$$i \gt 4$$$ and $$$i \lt NM - 2$$$ , $$$F[i] = 0 $$$ , you can first construct $$$K = 6.$$$ However , it may get confusing when many $$$1s$$$ have been filled , to solve that case , observe that You can invert all $$$1s$$$ to $$$0$$$ and $$$0s$$$ to $$$1$$$ , and $$$F[i]$$$ remains same. Hence the case $$$K = 6$$$ is same as $$$K = NM - 6$$$ .

»
5 месяцев назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

include <bits/stdc++.h>

using namespace std;

int main() { int t; cin >> t; while (t--) { int n; cin >> n; vector v(n); int y = 0; for (int i = 0; i < n; ++i) { cin >> v[i]; y = y | v[i]; }

for (int i = 31; i >= 0; i--) {
        if ((y & (1 << i)) == 0) {
            for (int j = 0; j < n; j++) {
                if (((v[j])> (pow(2,i)))) {
                    v[j] = -1;
                }
            }
        }
    }
    int a = count(v.begin(), v.end(), -1);
    cout << a << "\n";
}
return 0;

}this code is for 4th que of div4 in codechef(array removal) and it got accepted in codechef but this code gives wrong output for the input(n=4) {2,8,9,10}

»
5 месяцев назад, # |
  Проголосовать: нравится +4 Проголосовать: не нравится

are u gonna do anything about wrong submissions that got accepted for array removal problem,it had massive impact in rankings of div2

»
5 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Cheaters Cheaters everywhere :

https://www.youtube.com/watch?v=lroJG3QAcRA

Today I was hoping to turn three star on Codechef but thanks to them

»
5 месяцев назад, # |
Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится

Sorry for mentioning you but the tester's code given for the problem Pairs Sum with Length x in today's contest does not work. Please fix it.
Submission link
mexomerf IceKnight1093.

  • »
    »
    4 месяца назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    There must be a mistake, this solution is for a prev version of the problem

»
5 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Number Hunt Detailed Video Editorial

https://youtu.be/fhOLz-Or9NA