By awoo, history, 2 months ago, translation, In English

Hello Codeforces!

On Dec/12/2022 17:35 (Moscow time) Educational Codeforces Round 139 (Rated for Div. 2) will start.

Series of Educational Rounds continue being held as Harbour.Space University initiative! You can read the details about the cooperation between Harbour.Space University and Codeforces in the blog post.

This round will be rated for the participants with rating lower than 2100. It will be held on extended ICPC rules. The penalty for each incorrect submission until the submission with a full solution is 10 minutes. After the end of the contest you will have 12 hours to hack any solution you want. You will have access to copy any solution and test it locally.

You will be given 6 or 7 problems and 2 hours to solve them.

The problems were invented and prepared by Adilbek adedalic Dalabaev, Vladimir vovuh Petrov, Ivan BledDest Androsov, Maksim Neon Mescheryakov and me. Also huge thanks to Mike MikeMirzayanov Mirzayanov for great systems Polygon and Codeforces.

Good luck to all the participants!

UPD: Editorial is out

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

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

Best of Luck Everyone.

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

Thank you awoo for this educational Round. Can't wait to begin ! Good luck to all contestants!!!

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

Good luck broooo❤️

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

    good luck brooo!! without take part this contest!!

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

Ladies and Gentlemen I hope you all will get positive delta.

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

Good luck!

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

orz

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

After such a difficult contest yesterday, I hope to get a positive delta today :)
Wishing good luck to everyone!

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

I am looking forward to the problems of this contest, hoping to surprise me.

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

After difficult contest yesterday, I hope to change color of nickname

»
2 months ago, # |
  Vote: I like it -7 Vote: I do not like it

I am sb.

»
2 months ago, # |
  Vote: I like it -7 Vote: I do not like it

DON_F do you want to participate?

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

THANKS awoo!

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

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

sometimes less expectations give fruitful results.

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

Currently the standings seem to be showing both Div.1 and Div.2 participants regardless of whether the "show unofficial" checkbox is checked. This isn't too much an inconvenience, but still it makes us hard to see the actual standing based on the division. Can this be fixed ASAP?

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

read-the-problem-statement-carefully forces

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

Why using Sieve for D to generate list of primes of each number up to 10^7 TLE?

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

    Send code? I got it through even with Rust:

    fn sieve(n: usize, lpf: &mut Vec<usize>, primes: &mut Vec<usize>) {
        lpf.resize(n + 1, 0);
        for x in 2..=n {
            if lpf[x] == 0 {
                lpf[x] = x;
                primes.push(x);
            }
            for i in 0..primes.len() {
                let p = primes[i];
                if x * p > n {
                    break;
                }
                lpf[x * p] = p;
                if x % p == 0 {
                    break;
                }
            }
        }
    }
    
    let lpf = &mut Vec::new();
    let primes = &mut Vec::new();
    sieve(10_000_000, lpf, primes);
    

    Should be easy to translate to C++

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

      184970170 here's mine using sieve get TLE, also probably because i use "not good" sieve

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

        I think your problem is in IO... your sieve is fast enough (should be around 2-3 seconds), but iostream is slow.

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

          sorry im new, what do you mean with iostream ? because endl?

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

            Short Answer:

            • Add ios_base::sync_with_stdio(false); to the start of your code if you want to continue using cin and cout. In that case, do not use scanf or printf.
            • Also add cin.tie(NULL); to the start of your code. Do not use endl, but print \n instead. Note that if you test your program interactively like this, then you will not see any output until termination (i.e., all of the output comes in at once at the end)

            Long Answer:

            By default, cin and cout takes some extra time to synchronize with stdout (scanf and printf), e.g. to make sure cin doesn't read something that was already read by a previous scanf. To bypass this, you can either stop using cin/cout, or you can turn off the synchronization (ios_base::sync_with_stdio(false);) and be careful not to use scanf or printf.

            The other issue is only relevant if you are printing a lot of output (shouldn't be an issue for D here). Each time you use endl or cin, the output is flushed (i.e., whatever you were supposed to display from previous cout are gonna get displayed). Each flush takes some time. We can cut down the time by only invoking one flush at program termination. This requires never using endl and to ensure that cin does not invoke a flush (achieved by setting cin.tie (NULL))

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

              thx i dont get TLE anymore ,but now i got WA ;)

    • »
      »
      »
      2 months ago, # ^ |
      Rev. 4   Vote: I like it 0 Vote: I do not like it
      ll MX = 1000*10000;
      int mx = 0;
       
      vector<vector<int>> p;
      void prep() {
          p.clear();
          p.resize(MX);
          vector<bool> pr(MX, true);
          for (int i = 2; i < MX; i++) {
              if (p[i].size()) continue;
              if (!pr[i]) continue;
              for (int j = i; j < MX; j += i) {
                  p[j].push_back(i);
                  pr[j] = false;
              }
          }
      }
      

      Your code here... ~~~~~

      ~~~~~

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

        The second for is better done like this:

        // i is prime number
        div[i] = i;
        for (long long j = (long long)i * i; j < MX; j += i) {
            div[j] = i;
            pr[j] = false;
        }
        

        Firstly, we will iterate $$$j$$$ from $$$i^2$$$. Secondly, we will save only the minimum prime divisor for each number. This algorithm works for $$$O(C log(log(C)))$$$, but written by you $$$O(Clog(C))$$$.

        Now, all divisors of a number $$$n$$$ are searched like this:

        while (n > 1) {
            // check answer for div[n]
            n /= div[n];
        }
        
  • »
    »
    2 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I think generating primes till root(10^7) is sufficient for the problem.

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

    You dont need to generate prime numbers up to 10^7. Generating till sqrt(10^7) is sufficient.

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

      why?

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

        Sieve Factorization. Set a sieve of size $$$10^7$$$ where $$$sieve[i]$$$ is initialized to $$$i$$$. Then find all prime numbers up to $$$\sqrt{10^7}$$$ and use them to "mark" all composites up to $$$10^7$$$, i.e., set $$$sieve[i]$$$ to a prime factor of $$$i$$$.

        You don't need to generate the prime numbers after $$$\sqrt{10^7}$$$. We can still factorize all numbers after $$$\sqrt{10^7}$$$ this way, since all composites would be marked, and prime numbers are initially marked by themselves anyway.

        My submission: 184943623. Since we don't need the largest prime factor, we could improve this further by letting the $$$j$$$-loop start from $$$i^2$$$ instead of $$$3i$$$.

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

          So I tried a solution to generate all primes factor for all numbers up to 10^7. which should take N log log(N) ~100mil operations.

          Each number has another max 8 different prime factors, so the time to solve 10^6 cases is ~10^7. Why does this solution TLE?

          I know there's a better way to generate up only root(10^7) numbers but why does this solution TLE at 4 second ?

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

            The number of operations in a sieve is not $$$N \log \log N$$$, but rather, it is in $$$O(N \log \log N)$$$. The constant factor depends on the details of the sieve design, like whether you check even numbers or whether you generate primes beyond $$$\sqrt{N}$$$ or not. Your code seems to have none of these improvements, so the constant becomes pretty big.

            In general, a standard C++ code can comfortably perform $$$O(X)$$$ operations in 1 second when $$$X$$$ is of the order $$$10^7$$$. There are still exceptions where the constant factor is too big, but this is the general case for standard CP algorithms. However, when $$$X$$$ is of the order $$$10^8$$$, the constant factor matters immensely, and the finer details need to be sufficiently optimized to pass.

            For your approach, I expect $$$N = 10^5$$$ to run within 1 second comfortably, while $$$N = 10^6$$$ might fail 1 second but should be safe under 4 seconds, while $$$N = 10^7$$$ would definitely fail 4 seconds, and I doubt it would even pass 10 seconds, except maybe just barely. I might be wrong on these estimations, but that's what I would guess from experience. My suggestion would be to run your program to run only the sieve part (without reading any inputs or doing anything else) and check the time it takes to get a good estimation of whether it would work.

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

          Thank you, I learnt something new today — Sieve Factorization

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

      generating primes up to 10^7 is much more convenient as you can easily do that with linear sieve. Besides, given the number of test cases, traversing all the prime numbers up to sqrt(num) is a bit risky

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

        Well it may be convenient but it is not time efficient. There are around 500 primes in less than sqrt(1e7), but there are 664579 primes in the range 1-1e7

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

          With the whole sieve built with linear sieve, you can easily compute each query in LOG(n), I am not sure what you mean by time inefficient. Can you explain?

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

    I ised linear sieve of erastothenes and it didn't led me to tle !

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

Enough of these prime number questions...

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

guys how did u fix wa16 in E??

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

    Here is a test case that might help:

    $$$\texttt{6}$$$

    $$$\texttt{2 1 3 1 1 2}$$$

    For me this was wrong: it is possible to have a sequence of size $$$3$$$ (excluding $$$0$$$'s),

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

    Just before failing on WA16 my states:

    vector <int> st[Maxs] = {{}, {1}, {2}, {1, 2}, {2, 1},
                             {3}, {3, 1}, {3, 2}, {3, 1, 2}, {3, 2, 1}};
    

    I passed it with states:

    vector <int> st[Maxs] = {{}, {1}, {2}, {1, 2}, {2, 1},
                             {1, 1}, {1, 1, 2}, {1, 2, 1},
                             {2, 2}, {2, 1, 2}, {2, 2, 1},
                             {3}, {3, 1}, {3, 2}, {3, 1, 2}, {3, 2, 1}};
    

    States represent the order of relevant stacks. Some duplicates should be allowed as 3 could consume the first duplicate.

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

      Can you explain your approach to E? Like how we are using these valid states.

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

Can someone please give a test case for which my code for B is failing?
https://codeforces.com/contest/1766/submission/184942949

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

    try "aaaa"

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

      It's giving YES as output. That's what it's supposed to give right?

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

    "aaaab" should output "YES"

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

    i checked ur code, it's giving no for bbaaaa, but the answer is yes, since we can write it in 5 i.e . less than 6 steps

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

    1 5 aaaab should give Yes

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

In 1766D I factorized |y-x| and got TLE... is there any solution without factorization?

Update:got AC(1762ms) by using sieve and java.lang.StringBuilder(System.out.println() TLE'd)

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

    Precompute the factorisation, or more specifically only the smallest prime factor. This can be done with a linear sieve (there's a cf blog on it). I posted my code 4 comments above.

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

    How did you factorized ? If you used seive, then I don't think it would have given you TLE!

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

    $$$O(\sqrt{n})$$$ will clearly TLE. Instead you can use $$$O(\log n)$$$ factorization using eratosthenes' sieve (or you may be able to squeeze pollard's rho in TL but I think it would be hacked afterwards)

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

      UPD: "you may be able to squeeze pollard's rho in TL but I think it would be hacked afterwards"

      Yes it did get hacked

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

        I use this method to factorial but due to some mistack not able to done during contest even after 4 TLE and 4 RE + 1WA.

        Spoiler

        184984459

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

    Same here. I have seen a lot of solutions that passed that way. It is either we have missed something in the implementation or most of the solutions that passed that way will be hacked.

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

    I factorized $$$y - x$$$ and did not get TLE: 184943623

    Note: I used a sieve to generate the largest prime factor for each odd number from $$$3$$$ to $$$10^7$$$. I could have just used any prime factor (by letting the $$$j$$$-loop start from $$$i^2$$$), which would've been faster.

    If you TLE'd, my guess is that your sieve might not have been a very good one (e.g., outer loop running till $$$10^7$$$ instead of its square root)

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

    Need factorized |y-x| carefully.

    We can save the min factor of any number less than 10^7. Now for factorizing |y-x|, we can remove its min factor, and do it again, until all of factor found.

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

      Need to save not min but any factor actually. This solution works faster than mine. Thanks for sharing it helped

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

    My issue (and I suspect a lot of other getting TLE on D) turned out to be using "<< endl" instead of "<< \n". 1e6 instead of usual 1e5 output lines turns out to be the magic threshold where output speed matters, and even such small issue can kill you.

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

      i got TLE i change endl to \n and add

      ios_base::sync_with_stdio(false);
      cin.tie(NULL);
      

      no TLE anymore but WA ;)

      before 184970170 after 184985603

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

please tell me there's a better solution for D aside factoring $$$|y - x|$$$. That was very painful.

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

    I don't think so, but looking at your submission, it can be optimised by using a linear sieve instead.

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

      I see, thanks. The observation was quite obvious, but getting my factoring to pass was very difficult.

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

How avoid WA16 in E?

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

Successfully solved D for the first time, E seems like a tough one, I can only think that 2 followed by a 1 with any number of 0s in between will create an extra subsequences and obviously 0s will also create extra subsequences, I tried to count that in how many sub-arrays a 0 will contribute an extra subsequence and similarly for [2...1] but didn't get the right answers, any similar ideas?

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

    My idea (didn't write up a complete solution btw, so take this with a grain of salt):

    The number of non-zero subsequences is at most 3. We can try to count how many subsegments will generate each possible number of subsequences.

    • No non-zero subsequences -> The subsegment contains only 0s. We can easily count how many there are.

    • Exactly one non-zero subsequence -> If we look at the non-zero values of the subsegment, we must not have a 2 followed by a 1 or a 1 followed by a 2 (so there is always a 3 in between)

    • Exactly two non-zero subsequences -> This seems to be the hardest, so I was planning to find this by subtracting the others off of the total.

    • Exactly three non-zero subsequences -> There are two sub-cases:

      • Second non-zero subsequence ends with 1: Subsegment contains a 2 followed by a 1 (ignoring 0s in between). Later, after some 3, we get a 1 (so both non-zero subsequences end with 1) and then a 2 (which must form a third non-zero subsequence). Ignore all 0s in between.
      • Second non-zero subsequence ends with 2: Symmetric to the other case

    The challenge I faced with these counts is on the 0s. It's not enough to just find some segment that fulfills a condition, because a group of 0s can merge easily with whatever fulfills the left side and also whatever fulfills its right side, and I couldn't figure out how to deal with this effectively.

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

      Yea the in between zeros will make it hard, the implementation would be huge, at least for me, there must be an easier solution, thanks for sharing this one, lets wait for the editorial.

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

        ez solution:my comment no nested loops and only one if statement

        only disadvantage: not understandable at all

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

how to solve problem C anybody ? any hints

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

    Think about simulating the process and about the possible movements you can do when at a certain position.

    Also keep in mind the given constraints that each column has at least one "B".

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

    Think about the distance between each adjacent W's. And what happens when it is even or odd.

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

    Simulating the process might lead to TLE.

    Hint : make a vector pair of the number of whites and sort it. Now for each white (say i,j) and its the next nearest white (say i1,j1) see that the answer is NO if (i1-i)%2 == (j1-j)%2 and YES if the before condition doesn't hold for all whites.

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

Hint for D?

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

    $$$\gcd(a + k, b + k) = \gcd(a + k, b - a)$$$, so for it to not be $$$1$$$, we want $$$p \mid a + k$$$ where $$$p$$$ is a prime factor of $$$b - a$$$. Therefore, we generate all prime factors of $$$b - a$$$, which is precomputed by sieving. Then, $$$p \mid a + k$$$ means $$$k = (-a) \mod p$$$. Take the minimum over all prime factors.

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

      I did D in the contest by taking my intuition to check for only prime factors of (b-a). Can you please why shouldn't I take composite factors?

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

        if any composite factor is the gcd then any of the prime divisors of that factor will also divide both numbers

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

184979418

My code for d keeps giving different output in sublime and different output when i submit it on cf

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

    In your code, you are giving -1 output for 1 case only, but there are different cases possible when there will be -1 as output. You might be running given test case in sublime, but when another test cases would have be checked, then your code gave TLE.

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

can someone pls explain how to solve e .

thanks in advance.

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

Am i the only one who wasted time by writing a stupid dp solution for C?

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

    DP was also my first instinct, but then I realized that the path was simply forced to go up/down if the other cell was also Black, and from then on the only possible continuation was going to the right, and repeat.

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

    Me, too, wasted some of my time by thinking in the direction of DP ;)

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

      I did a 2*n dp table where dp[i][j] is true if you can finish painting the jth column in the ith cell.

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

    lol i also did a dp solution haha new learning for me

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

      Can someone help me out in c? code: 185047353

      I did it by traversing both strings and comparing the positions of the white color. but it is failing on 2nd test case ;(

      i don't know exactly where it's failing.

      thanks in advance.

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

Hint for D ?

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

    Depends on how far you thought ahead.

    Hint 1
    Hint 2
    Hint 3
    Brief Overview

    My Submission: 184943623

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

      WonderFull explanation dude

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

      Can you please explain how you implemented the factorization part in your code?

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

        Are you familiar with the Sieve of Eratosthenes?

        The basic idea is that we prepare an array sieve of size $$$10^7$$$ such that the value of sieve[i] should be any prime factor of $$$i$$$. Initially, we set $$$sieve[i] = i$$$ for all $$$i$$$, with the intention of changing this later only for composite values.

        Now, for each $$$i$$$ in increasing order, check if $$$sieve[i]$$$ is still equal to $$$i$$$ (i.e., it never changed). If yes, then $$$i$$$ is prime. For each multiple of $$$i$$$, e.g., $$$ai$$$, we set $$$sieve[ai] = i$$$. Therefore, every composite number $$$i$$$ will eventually have $$$sieve[i]$$$ as one of its prime factors.

        (This can be improved in several ways. We can skip all even numbers, because it's easy to check evenness and deal with it separately without needing to utilize a sieve. When we check each $$$i$$$ in increasing order in order to find prime numbers and their multiples, we can stop when $$$i > \sqrt{10^7}$$$ since every composite number up to $$$10^7$$$ will have at least one prime factor $$$\leq \sqrt{10^7}$$$, so its sieve value would be set to some prime factor. Also, when finding multiples of $$$i$$$, we can start with $$$i^2$$$ since all the earlier multiples would've been covered by an earlier prime)

        After setting up the sieve, we can now factorize numbers efficiently. To factorize $$$x$$$, we read $$$sieve[x]$$$ to get one prime factor. We then divide $$$x$$$ by this factor, i.e., $$$x' = x/sieve[x]$$$. Now we can read $$$sieve[x']$$$ to get another prime factor. Repeat until $$$x$$$ is reduced to 1 in order to construct the complete prime factorization.

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

          what will happen if i generate all prime till 10e7 and linearly calculate the list of primes of y-x?

          why its giving tle ?

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

            Because it's slow. There are a lot of primes up to $$$10^7$$$. Even just generating those prime numbers will likely cause TLE, even before you try factorizing $$$y - x$$$.

            On the other hand, the efficient sieve factorization which I described that requires finding only the primes up to $$$\sqrt{10^7}$$$ is significantly faster, comfortably passing the time limit.

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

              Gotcha

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

              hi just to add on my approach is very similar to the one here, but I keep getting TLE. Does anyone know how I can optimise my code to pass D?

              My code: Code

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

                You're using a Boolean Sieve, which works great for checking if a given number is prime, but is not very efficient for actually factorizing many numbers. For each number you wish to factorize, you might have to check over 3000 prime numbers in the worst-case. With $$$10^6$$$ numbers to factorize, this would not pass the time limit.

                For Sieve Factorization, you need to make a small change to your sieve function. Instead of making the value False for a composite, make the value $$$p$$$ instead (the prime number whose multiples you're marking). There is no need to generate a list of primes. Now, to factorize a number $$$x$$$, you can read the value $$$p$$$ from the sieve list to get one factor, then divide $$$x/p$$$, read the corresponding value from the sieve list to get another factor, and so on.

                This way, the time taken to factorize a single number is proportional to the number of prime factors it decomposes into, which is at most $$$\log_2 (10^7) < 25$$$, much better than iterating over 3000 steps!

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

                  Hi thank you for the response! I can understand the first paragraph, but I am not sure of what you mean in the second paragraph, and how that will result in a shorter runtime. Do you happen to have any pseudocode to illustrate what you mean by "Now, to factorize a number x, you can read the value p from the sieve list to get one factor, then divide x/p, read the corresponding value from the sieve list to get another factor, and so on."?

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

                  chiralcentre Here is some simple Python code for it:

                  Preparing the Sieve
                  Factorizing an integer

                  The second block is a function that returns the list of prime factors to convey the general idea, but you can, of course, modify it accordingly to what you need.

                  You can also improve the sieve by not even allocating space for the even values, e.g., sieve[i] represents $$$2i + 1$$$, but that hurts readability, so I didn't do that here.

                  Let me know if you have any questions.

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

                  Thank you for the reply! I understand better now haha

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

Problem A's harder version.

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

Although I only solved up to C, this set was good!. After seeing other submissions on D I realized rather than looping through primes until sqrt(1e+7) (which is about 700 prime numbers) it's better to factorize the difference!

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

The feeling when you screw up C for more than half an hour because you forgot how c++ grid coords work... again. And then I got late for 2-3 damn seconds. Hate myself...

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

Solution for E:

First,calculate the contribution of 0 separately.

Next, enumerate the left endpoint $$$L=1,2,..., n $$$.

(Next we ignore 0)

We find that the answer is always no more than $$$3$$$.

$$$Ans=2$$$ : $$$a[L,R]=$$$ $$$... 1,2 ...$$$ , or $$$... 2,1 ...$$$

$$$Ans=3$$$ : $$$a[L,R]=$$$ $$$... [1,2] ... [3 ... 3 2 ... 2 1] ...$$$ , or $$$a[L,R]=$$$ $$$... [2,1] ... [3 ... 3 1 ... 1 2] ...$$$

If there is no above condition, $$$ANS=1$$$ or $$$ANS=0$$$ (all elements are $$$0$$$).

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

    I think my solution is the same. I split the array into subarrays whenever we encounter a 3, and then for each subarray, we store the occurrences of $$$[1, 2]$$$ and $$$[2, 1]$$$. Note that only the first occurrences of the subarray will contribute to the answer.

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

i think E is just case work. (correct me if i'm wrong) if you ignore all the 0, it can be proven that the maximum number subsequence will be <= 3

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

    I have a solution without any casework.

    let ignore sequence with single $$$0$$$ first since we can calculate its contribution to answer easily, then we can find that $$$3$$$ can only be at the first sequence, and there will be at most one extra sequence which only have $$$1$$$, and at most one extra sequence only have $$$2$$$.

    So we can just do $$$dp[\text{n}][\text{the last element of first sequence}][\text{flag1}][\text{flag2}]$$$ where $$$\text{flag1/flag2}$$$ represent whether we have a extra sequence with $$$1/2$$$.

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

In problem $$$B$$$, am I the only one who thought that the number of operations may be less than (n-1) ? :(

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

nice contest

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

Can someone explain problem C ? I did a dfs + visited hashset but it kept giving me TLE. https://codeforces.com/contest/1766/submission/184980253

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

    simulation

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

      I think I did the simulation but it kept giving me TLE.

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

    I dont know if a dfs passes, but could be done by a simple observation that each time a sequential BB occurs, I am attaching my code

    #include<bits/stdc++.h>
    using namespace std;
    #define pb push_back
    #define mp make_pair
    #define S second
    #define F first
    #define pu push
    #define po pop
    #define oo 99349092
    #define fast_IO ios_base::sync_with_stdio(false);
    #define null cin.tie(nullptr);
    #define lenn .size()
    #define ret return 0;
    void solve()
    {
        int n;
        cin>>n;
        string A, B;
        cin>>A;
        cin>>B;
        int p = 0;
        bool dp0 = 1, dp1 = 1;
        for(int i=0; i<n; i++)
        {
            if (A[i] == 'B' && B[i] == 'B')
            {
                swap(dp0, dp1);
            }
            if (A[i] == 'B' && B[i] == 'W')
            {
                dp1 = 0;
            }
            if (A[i] == 'W' && B[i] == 'B')
            {
                dp0 = 0;
            }
        }
        if(dp0||dp1)
        {
            cout<<"YES"<<endl;
        }
        else
        {
            cout<<"NO"<<endl;
        }
    }
    
    
    int main()
    {
        int t;
        cin>>t;
        while(t--)
        {
            solve();
        }
    }
    
    • »
      »
      »
      2 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Thanks.... this makes sense. Thanks a ton

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

    Hint : make a vector pair of the number of whites and sort it. Now for each white (say i,j) and its the next nearest white (say i1,j1) see that the answer is NO if (i1-i)%2 == (j1-j)%2 and YES if the before condition doesn't hold for all whites.

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

    huh , that's strange , I solved it using DFS :|

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

      I think it maybe bcoz u did in C++ and I did in Python(not sure tho). Anyways, I have figured out another way thanks to @WarriorOfLiberation. Thanks for trying to help though.

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

Hints for B ,Please ?

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

    if 'x' letter precedes a letter 'y', then when 'y' letter occurs again in the string check if there is a preceding 'x'. If there is a preceding 'x' to the second occurence of 'y', then it is guarenteed that answer is less than n

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

Problems were good , was a good contest

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

Speedforces :(

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

Is it possible to use Möbius inversion and binary search to solve D? Search the k and check the sum of [gcd(x+i,y+i)==1](0<=i<=k) is whether equals to (k + 1) in time limit. I spent a lot of time trying it but failed.

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

Another approach for C: Store the positions of W, in increasing order of column number. The following condition should be satisfied for the answer to exist : For any 2 consecutive position of W, if they were in the same row, then the difference between their position must be ODD, or else it should be EVEN. 184980206

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

Here are video Solutions for A-D, in case someone is interested.

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

Do we get or lose points for hacking in this round?

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

    Nope

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

      Okay, thanks. But I notice my rank is still increasing, is it because of virtual particpants?

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

        yes, due to virtual participants. Also, it could decrease if someone previously above you got solution hacked for some problem.

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

Nice E, hope to get to Master!

»
2 months ago, # |
  Vote: I like it +1 Vote: I do not like it
complete code

part of my code for 1766E

//magic numbers
	static int[] next1=new int[] {1,1,5,1,4,5,4,9,11,9,10,11,
			10,15,14,15};
	static int[] next2=new int[] {2,4,2,2,4,5,8,5,8,10,10,11,
			14,11,14,15};
	static int[] next3=new int[] {3,3,3,3,6,7,6,7,6,7,12,13,
			12,13,12,13};

wish I've come up with this idea before the contest ended

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

    Complete code ? Thank you, here's the meme for you.

    Why would you paste code without a link ? Improve your manners

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

    Explaination: In a subsequence only the last element matters. We count answer by counting 0s and non-zero sequences. For 0 at position i it contributes i*(n+1-i). We construct a FSM for another part of the anwser, where its states are represented by the last element of each non-zero sequence. By compute with brute force we can show that there are only 16 possible states: (none),1,2,3,12,21,32,31,22,11,112,221,312,321,212,121. Then we can number these states and make the state transition table manually. Remaining work is trivial.

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

can anyone tell me why my solution getting tle for problem d? https://codeforces.com/contest/1766/submission/184998801

thanks in advance.

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

Japan or2

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

Could anyone explain to me how this solution works? (I am skimming through various solutions for problem A and this one is interesting.) string s; cin >> s; int l = (int)s.size(); cout << 9*(l — 1) + s[0] — '0' << '\n';

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

    one-digit number -> 1-9: {1,2,3,4,5,6,7,8,9} = 9

    two-digit number -> 10-90: {10,20,30,40,50,60,70,80,90} = 9

    three-digit number -> 100-900: {100,200,300,400,500,600,700,800,900} = 9

    ...

    six-digit number -> 100000-900000: {100000,200000,300000,400000,500000,600000,700000,800000,900000} = 9 Thus in every n-digit has 9 numbers having interval is 10^n-1 for each only one non-zero digit

    so the ans will be : 9*(LenthOfTheNumber-1) + firstDigitOfTheNumber

    for example: n = 201

    length of n = 3 first digit of n = 2

    => 9*(3-1) + 2

    => 18 + 2 = 20

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

We want $$$gcd(x+k, y+k) = d , (d > 1)$$$ then

$$$ x+k \equiv y+k \equiv 0 \mod{d} $$$

$$$ x+k \equiv y+k \mod{d} $$$

$$$ x \equiv y \mod{d} $$$

$$$ x-y \equiv 0 \mod{d} $$$

to make $$$x-y$$$ divisible by $$$d$$$, $$$d$$$ must divide $$$x-y$$$

so we will get prime factors of $$$x-y$$$

suppose that prime factors of x-y is $$$p_1, p_2, p_3,...,p_m$$$

if we return to our first equation $$$x+k \equiv y+k \equiv 0 \mod{d} $$$

substitute $$$d= p_i$$$

$$$x+k \equiv y+k \equiv 0 \mod{p_i} $$$

we have $$$x-y \equiv 0 \mod{p_i}$$$

then $$$x \equiv r \mod{p_i} \;\;\;, y \equiv r \mod{p_i} $$$

after subsititution of x and y

$$$r+k \equiv r+k \equiv 0 \mod{p_i}$$$

so k must be $$$p_i-r$$$

I get Wa on the contest because I forget to get the min for all p_i

Mysumbission

TIME (810 ms)
»
2 months ago, # |
Rev. 3   Vote: I like it -18 Vote: I do not like it

1766A - Extremely Round

My submission -> 185002843

Can anyone please explain why I am getting TLE on test case two of the following code?

#include<bits/stdc++.h>
using namespace std;
int main()
{
    int t;
    cin>>t;
    while(t--)
    {
    long long n,s1=0,s2=0,s3=0,s4=0;
    cin>>n;
    for(long long i=1;i<=n;i++)
    {
    if(i<10) 
        s1=i+0;
    else if(i==10||i==20||i==30||i==40||i==50||i==60||i==70||i==80||i==90||i==100) 
        s2 = i/10;
    else if(i==200||i==300||i==400||i==500||i==600||i==700||i==800||i==900||i==1000) 
        s3 =i/100-1;
    else if(i==2000||i==3000||i==4000||i==5000||i==6000||i==7000||i==8000||i==9000||i==10000) 
        s4 = i/1000-1;
    else if(i==20000||i==30000||i==40000||i==50000||i==60000||i==70000||i==80000||i==90000||i==100000) 
        s4 = i/10000-1;
    }
 
   cout<<(s1+s2+s3+s4)<<endl;
 
    }
}
  • »
    »
    2 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    On this question t can be up to 10000 and n can be up to 999999. On the worst case scenario your code perform 10000 * 999999 operation that's why it is getting TLE verdict. It is better to memorize the answer from 1 to 999999 instead of calculating the result repeatedly.

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

      But in this problem we have 3 second per test case. I have only one loop having O(n). It can pass easily!?

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

        3 second for entire test case and for a single test t can be up to 10000.

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

        The time limit is not 3 seconds per test case, but 3 seconds per test.

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

I have a question for those who solved F (spoiler alert — it is about some part of the solution).

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

    Add edges from new_s and edges to new_t with a very negative value, and add edges from t to s with a very positive value, the new graph will not have negative cycles, find the min cost max flow in the new graph and delete new_s, new_t to run min cost flow from s to t.

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

For question D:

So I tried a solution to generate all primes factor for all numbers up to 10^7. which should take N log log(N) ~100mil operations.

Each number has another max 8 different prime factors, so the time to solve 10^6 cases is ~10^7. Why does this solution TLE?

I know there's a better way to generate up only root(10^7) numbers but why does this solution TLE at 4 second ?

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

    probably because push_back is slow

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

    Same code as yours but with C++20 (185029658) gives MLE. I suspect yours is MLE too.

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

      same idea used but with little extra help 184968390 ,184969180 and 184969946 as you can see the more primes I checked separately the better the time gets

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

        Thanks! Any idea on when it stops helping? If ve.size()==k then maxm*(ln(ln(k))) ops are saved in the sieve but I find it hard to estimate the overhead due to for (int p : ve){...}.

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

          I think we can go further from 47 but I don't know till when it will get better

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

For problem C: Hamiltonian Wall, I was getting the error. Can anyone point out where is the mistake?

t=int(input())
for _ in range(t):
    arr=[]
    x=int(input())
    y=input()
    z=input()
    arr.append(list(y))
    arr.append(list(z))
    b,w=False,False
    c=0
    flag=True
    for j in range(len(arr[0])):
        
        if arr[0][j]=='B' and arr[1][j]=='B':
            c+=-1
            
        elif arr[0][j]=='W' and arr[1][j]=='B':
            if w:
                if c%2:
                    flag=False
                    break
                else:
                    flag=True
            elif b:
                if not c%2:
                    flag=False
                    break
                else:
                    flag=True
            c=0
            w=True
        elif arr[0][j]=='B' and arr[1][j]=='W':
            if b:
                if c%2:
                    flag=False
                    break
                else:
                    flag=True
            elif w:
                if not c%2:
                    flag=False
                    break
                else:
                    flag=True
            c=0
            b=True
        else:
            flag=False
            break
    if not flag:
        print('NO')
    else:
        print('YES')
  • »
    »
    2 months ago, # ^ |
    Rev. 2   Vote: I like it -21 Vote: I do not like it
    def solveShit():
        m = int(input())
        s = [getStrs(), getStrs()]
        cnt =0
        cur = 1
        flag = False
        for i in range(m):
            if s[0][i]==s[1][i]:
                cur = not cur
            else:
                if s[cur][i]!='B':
                    break
            cnt+=1
        if cnt==m:
            flag = True
    
        cur = 0
        cnt =0
        for i in range(m):
            if s[0][i] == s[1][i]:
                cur = not cur
            else:
                if s[cur][i] != 'B':
                    break
            cnt+=1
        if cnt==m:
            flag = True
        if flag:
            print("YES")
        else:
            print("NO")
    
»
2 months ago, # |
Rev. 3   Vote: I like it 0 Vote: I do not like it

Can someone explain solution of Problem E?

Thanks in Advance.

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

Can Anyone Explain Why my Solution For D Gave TLE:(

https://codeforces.com/problemset/submission/1766/184955390

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

    got TLE with input 1,8388609 where diff=8334608=1<<23 and your solution consumed too much time for factorization. In fact answer is 1 when x,y are both odd numbers, so determine it first can save a lot of time

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

    also there's no need for push duplicated element to s1

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

    Just replace endl with '\n' and your solution will pass.I faced the same issue

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

I solved problem D offline, but no body hacked me. 184948549

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

(◕︵◕) I will be +99 at this contest but road to expert still so far.

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

    Man, just 1 more good contest to go. All the best!

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

My D using neal Pollard's rho code from last contest.

https://codeforces.com/contest/1766/submission/184943158

Passes under 2.5 seconds

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

    Is the code based on Brent's improvement on Pollard's Rho? FYI, The constant on the one with Brent's improvement is quite smaller than the vanilla one.

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

Why is it rejudged twice?

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

When will the editorial be out?

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

When can l get the rattings why it shows that the contest is unrated in my constets

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

    do you have any updates? when will the rating be out?

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

      NO,and I'm waiting for the results for a long time .Maybe tomorrow the results will be out.

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

        The results for the educational/div 3/div 4 rounds are coming in the afternoon or in the evening of the next day from the contest so they will be today but i don't know when.

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

I participated in the contest. I submitted by code for problem D(184941244) and it got hacked because Time Limit exceeded. After the contest I submitted the same code(185049594) and it got accepted. I want to bring this to the notice of the authors of the contest(awoo, BledDest,Neon, adedalic) and Mike MikeMirzayanov to consider this problem and come up with a solution to this.

Thank You

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

    Use '\n' in place of endl to reduce the time of your soln. My solution got accepted during the hacking phase with the same time as yours, but got TLE during system testing..

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

I participated in the contest. I submitted by code for problem D(184961915) and it got hacked because of Runtime Error. After the contest I submitted the same code(185050448) and it got accepted. I want to bring this to the notice of the authors of the contest(awoo, BledDest,Neon, adedalic) and MikeMirzayanov to consider this problem and come up with a solution to this.

Thank You

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

    This is also your solution getting TLE on test 3. You probably have an undefined behavior somewhere in your solution. I don't think the contest authors can do anything about that.

»
2 months ago, # |
  Vote: I like it -14 Vote: I do not like it

I got TLE in 1766D - Lucky Chains after the contest because of the usage of endl instead of \n I think the solution should be considered accepted as the algorithm is fine The TLE solution 184975152 The accepted one 185056871

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

    It's unfortunate that you were unaware of the timing delays caused by endl flushes, but the reality is that the submission did not pass the time limit. There is no subjective judgment on whether a solution should be "considered" accepted or not (just like how a submission that solves 99% of the cases but fails one specific edge case is still not going to be "considered" accepted). Please instead use this as a learning experience to avoid using endl in the future. This is an important component of fast I/O, and I can see that your code already attempts to speed up the I/O.

    On that note, I would also recommend that you properly learn what your code does, instead of memorizing or preparing a template of code you don't understand. Both submissions had cin.tie (0);, but the purpose of this (prevent early flushing) is basically cancelled out by the use of endl. By the way, cout.tie (0) doesn't do anything.

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

When will the results be out??

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

Release the updates :) :), I need to see my shiny new color

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

contest ratings are not updated yet. why?

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

Where is the editorial?

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

    While you wait you can ask here about the problems or see what other people wrote above

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

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

Where is my new slightly bigger rating???

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

Hello?It said "rated for the participants with rating lower than 2100".But the line chart in my profile shows that this Round is "unrated" for me.Is it a bug?

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

    It means the round is not rated YET, may not be a bug necessarily.

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

Change my color

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

So,what time does the rating change? qwq

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

How long will cyan have to wait to take over green?

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

Maybe this will be the first div2 contest which everyone got unrated lol

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

Is the contest unrated?

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

When is the editorial?

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

I'm a novice. B's first idea about KMP is KMP, but I don't have any idea about KMP. I hope to give some hints

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

    think about a substring of length 2

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

    I thought about KMP too in tne contest and have wasted a lot of time on this idea, because I didn't notice that $$$n$$$ is just the length of the string, rather than an arbitrary number. Otherwise this problem maybe far more difficult.

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

is it really unrated :(

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

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

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

    where are the rating changes :(

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

    i am not doing any cheating in contest ,i had give many contest at default mode of ide, till now i don't know it will be cheated at that ide. so please take my solution its my hard work on that solution i think u take it serious.

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

    i am not doing any cheating in contest ,i had give many contest at default mode of ide, till now i don't know it will be cheated at that ide. so please take my solution its my hard work on that solution i think u take it serious.

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

Will we get the rating today? MikeMirzayanov, we, thousands of participants, are eagerly waiting for the rating change.

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

MikeMirzayanov, awoo. Can we knwo why the rating hasn't changed? We have waited already two days with no information. Is there a problem with the rating system or will we get our rating at all? :/

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

When will the rating get updated? Is it unrated?

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

why the rating has not been updated?

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

when will the ratings be out??

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

it's my first contest ㅠ_ㅠ wanna get my rating..,,

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

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

Why is the rating not updated?

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

Is it was not rated?

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

ratings vro

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

When will the rating get updated? I was going to get under zero rated for the first time :(

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

No ratings till now.

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

@Codeforces , atleast give update about rating changes

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

It is deadforces? No ratings updated yet

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

This has been the longest waiting time before ratings to be updated in almost 2 years.

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

I'm refreshing the page since yesterday :( ...plz release the ratings fast or atleast give an update

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

DeadForces!

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

Harshly true that awoo wants more comments to announce the rating!

source: deadforces

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

Deadforces!

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

when did rates will be updated?

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

why the rating changes are not being updated ?? its been 3 days since contest ..

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

Hey guys, it has been 3 days since the contest started. Why does it take so long :(?.

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

My rating!When can I get my rating!TAT

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

DeadForces! Where’s my rating…=_=

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

deadforces :(

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

Cyan be waiting for too long now.

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

To everyone writing deadforces Glitches happen sometimes. Starting to make fun of such a wonderful platform is not funny. Codeforces is <3

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

    That's fine. But atleast they can inform about that.

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

    The problem is that so far to my knowledge we've not received any word from MikeMirzayanov or awoo about it. Is it a glitch? Are they working on it? Will we eventually receive our rating? Will the round be unrated? I hope they can at least give any update on this

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

i am not doing any cheating in contest ,i had give many contest at default mode of ide, till now i don't know it will be cheated at that ide. so please take my solution its my hard work on that solution i think u take it serious.

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

How do I prove that I have not cheated?

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

It would be so much easier to read the comments that discuss solutions if there were not so many people asking about the rating change. What is the problem with waiting? Obviously there is some issue and of course they must be resolving it.

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

is the rating out?? can anyone confirm?

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

Problem C

Greedy Approach:

We check every corresponding indexes of both the strings; Since we have to travel all B's therefore, whenever the same index characters are BB we switch the row => since if proceed ahead without traveling the B in the other row and move ahead, then we won't be able to come back to the other B. Now when the two chars are BW => then we must be on the first or else we can't paint and then our requirement for B in the next row is a must have on first row. Similarly with WB we must be on second row and we must be able to move ahead on the following second row. If on doing all this we reach last B then we can paint in reqd limits.

Code

DFS Approach:

First, compute the number of Black cells in the given matrix. Then, if under given constraints we are able to count all black cells then answer will YES else NO. We will try to implement painting from left to right. So to implement traversing with given constraints, we will use visited matrix and apply DFS accordingly. If on 0th row we look down and then right side neighbor, similarly if on 1st row we look up and then right side neighbor. Up and down movement first because we are moving L to R and when the up and down chars are same we must travel it or else we will move ahead and not come back.

Code