_HossamYehia_'s blog

By _HossamYehia_, 19 months ago, In English

Hello, Codeforces!

I am glad to invite everyone to participate in Codeforces Round #837 (Div. 2) , which will be held on Dec/11/2022 18:35 (Moscow time)

Please note the unusual time!

The round will be rated for participants of Division 2 with a rating lower than 2100. Division 1 participants can participate unofficially in the round.

You will be given 6 problems and 2 hours to solve them. This round was prepared by me and 4qqqq.

I'd especially like to thank:

This is my first official round on Codeforces. We are sincerely looking forward to your participation. We hope everyone will enjoy it.

The score distribution : 500 — 1000 — 1750 — 2250 — 2750 — 3500

We wish you good luck and high rating!

UPD1: We know about problem with C task. Now we are trying to fix it.

Editorial.

  • Vote: I like it
  • -547
  • Vote: I do not like it

| Write comment?
»
19 months ago, # |
  Vote: I like it +7 Vote: I do not like it

waiting for the round.

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

Egyptian Russian alliance. Hope it's gonna be a great round!

But where is "As a tester,...." comments XD

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

    As a participant, I wish all positive delta and that there is NO XOR problems..

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

      there is NO XOR problems

      So you want XNOR problems?

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

        xD NO. I meant that usually Egyptian rounds imply incoming XOR missiles.

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

    As a author... So, now "As a author" comment here. Wait for testers

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

      Finally, a 4qqqq round! Can not wait for it <3

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

    Heap_OverFlow Also as a author, You will enjoy the problems xD.

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

      cap

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

      I did A and B only they were kinda good. FSTed on C. I think pretests were very weak? But I rewrote it and barely pass the timelimit, also many submissions following same approach of sieving then factorizing barely pass the TL. I wonder what is the intended solution for this problem? When will the editorial be published ?

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

WOW .. Egyptian round . Good luck bro

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

As a division 5 participant, I can participate unofficially in the round.

Hope you'll prepare more interesting rounds.

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

 CAN ANYONE RELATE ;)

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

After a long time. Best of luck Everyone.

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

It's a long time for an Egyptian round ..

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

No interactive problems?

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

After a long time, 7 contests in 9 days. Great!

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

finally a contest

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

This is the most anticipated contest for me, keep up _HossamYehia_ :DDD

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

Morocco famous win and now Egyptian contest... African vibes coming

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

I am best

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

The contest will start at 23:35 in China:(

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

If I'm beginning in programmation. Should I participate or it will be too difficult for me?

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

    It will never be difficult. You will not Learn running unless you start walking. So participate in this contest and try to solve atleast one or two problem. Best wishes.

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

Can't wait to see wangzheng2008's performance.

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

I hope this African Round is as good as they are performing in FIFA World Cup with Morocco.

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

Hope to become pharaon this round

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

Codepairses

»
19 months ago, # |
  Vote: I like it -11 Vote: I do not like it

Why does this feel like a Div 1 round or maybe it's just tough for me.

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

E has a strong ROI 2015 in Arkhangelsk problem 6 vibe

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

Bloody Hell. What a pairful round!

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

let me guess, you forced online version of F because $$$O(mlog^2n)$$$ parallel_bs + BIT is faster than $$$O(mlogn)$$$ persistent_tree? :D

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

Why only 1 second limit for problem D? Java barely passes after optimizations & 3 TLEs...

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

    Cuz why not ?

    My solution had a complexity of $$$\mathcal{O}(n^2\log{n})$$$, using LCA and dp.

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

      Because it screws Java users... My solution is O(n^2) and it might fail on system tests.

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

      My n^2 solution for D runs very slowly, can you tell why

      #pragma GCC optimize("unroll-loops")
      #pragma GCC optimize("O3")
      #pragma GCC target("avx2")
      #include <bits/stdc++.h>
      #include <iostream>
      #include <fstream>
      #define ll long long
      #define mod 998244353
      #define mod1 998244353
      #define PI 3.14159265359
      using namespace std;
      vector<vector<int>>adj;
      vector<vector<int>>dp;
      vector<vector<vector<int>>>paths;
      void dfs(int v,int par, int vert, int startv, int&len)
      {
         
          len++;   
          if(len>2)
          {
              paths[len].push_back({startv,vert,par,v});
          }
          for(auto it:adj[v])
          {
              if(it==par)
                  continue;
              dfs(it,v,vert,startv,len);
          }
          len--;
      }
      
      int main()
      {
          ios_base::sync_with_stdio(false);
          cin.tie(NULL);
          cout.tie(NULL);
          cout<<fixed<<setprecision(12);
          cerr<<fixed<<setprecision(5);
          // SieveOfEratosthenes(1000000);
          int t=1;
          cin>>t;   
          int tx = t;
          
          while(t--)
          {
           int n;
           cin>>n;
           adj.clear();
           paths.clear();
           dp.clear();
           adj.resize(n+1);
           dp.resize(n+1,vector<int>(n+1));
           paths.resize(n+1);
           
           string vals;
           cin>>vals;
           
           int i;
           
           int ans = 1;
           for(i=1;i<=n;i++)
           {
              dp[i][i]=1;
           }
           for(i=1;i<=n-1;i++)
           {
              int a,b;
              cin>>a>>b;
              adj[a].push_back(b);
              adj[b].push_back(a);
              if(vals[a-1]==vals[b-1])
              {
                  dp[a][b]=dp[b][a]=2;
                  ans =2;
              }
              else 
              {
                  dp[a][b]=dp[b][a]=1;
              }
           }
           
           for(i=1;i<=n;i++)
           {
              for(auto it:adj[i])
              {
                  int len=1;
                  dfs(it,i,it,i,len);
              }
           }
           int cnt=0;
           for(i=3;i<=n;i++)
           {
              for(auto &it:paths[i])
              {
                  int lef = it[0];
                  int ri = it[3];
                  int l1 = it[1];
                  int r1 = it[2];
                  if(vals[lef-1]==vals[ri-1])
                  {
                      dp[lef][ri]=dp[l1][r1]+2;
                  }
                  dp[lef][ri]=max(dp[lef][ri],dp[lef][r1]);
                  dp[lef][ri]=max(dp[lef][ri],dp[l1][ri]);
                  ans = max(ans,dp[lef][ri]);
              }
           }
           cout<<ans<<"\n";
      
          }
           return 0;
      }
      
»
19 months ago, # |
  Vote: I like it 0 Vote: I do not like it

How to solve B?

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

    I will try my best to explain what I did, So a few observations first, The permutation is 1,2,3,4....n 1) Number of subsequences starting from 'i' are n-i+1.

    2) If we have a pair (1,2) that means that it includes all pairs (1,2),(1,3),(1,4)...(1,n) are included in it (because if we take any pair they will have (1,2) always). So if we have 2 inputs given as (1,2) and (1,4) so we can ignore (1,4) and take only (1,2) in consideration for calculation.

    3) Now take a case like this we have only (2,3) as the pair, So when we consider subsequences starting from 1, They are: {[1],[1,2],[1,2,3],[1,2,3,4]}. Now as we have (2,3) as a pair we have to stop before 3. So we have to consider the effects of the number after 1 to get its stopping point.(once read code comments to be more clear)

    4) if we only consider the pair (1,4), lets say n is 5. so the possible subsequences are 1,{1,2}, {1,2,3} == 4-1 {or b-a for a pair (a,b)}

    Code With comments

    Spoiler

    Sorry If I complicated in explaining something.

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

    Some observations:

    • If $$$[a, b]$$$ is a good subsegment, then all subsegments of $$$[a, b]$$$ are also good subsegments.
    • If the non-friend list contains a pair $$$(a, b)$$$, then any good subsegment that contains $$$a$$$ will not contain $$$b$$$.
    • If $$$[a + 1, b]$$$ is not a good subsegment, then $$$[a, b]$$$ is not a good subsegment.
    • If $$$[a + 1, b]$$$ is a good subsegment, and $$$a$$$ is friends with all $$$x$$$ satisfying $$$a < x \leq b$$$, then $$$[a, b]$$$ is also a good subsegment.
    • If the largest good subsegment that begins with $$$a$$$ is $$$[a, b]$$$, then there are exactly $$$b - a + 1$$$ good subsegments that begin with $$$a$$$ (all prefixes of $$$[a, b]$$$).

    Individually, these observations should be obvious, but this leads to the following solution:

    • First, for each person $$$i$$$, find the earliest person after $$$i$$$ who is not friends with $$$i$$$, i.e., find the number $$$j$$$ such that $$$i$$$ is friends with everyone in the interval $$$(i, j)$$$ but $$$i$$$ is not friends with $$$j$$$.
      • We can prepare this by simply maintaining a 1D vector nextstranger, such that when we read a non-friend pair $$$a, b$$$ with $$$a < b$$$, we set nextstranger[a] = min (next_stranger[a], b).
    • Suppose we know that the largest good subsegment that begins with $$$a + 1$$$ is $$$[a + 1, b]$$$. If $$$a$$$ is friends with everybody in the range $$$(a, b)$$$, then the largest good subsegment that begins with $$$a$$$ is $$$[a, b]$$$ (cannot extend to $$$b + 1$$$ because there must be somebody within that that doesn't know $$$b + 1$$$). But if there is at least one person that $$$a$$$ is not friends with in the range $$$[a + 1, b]$$$, then the largest good subsegment that begins with $$$a$$$ is $$$[a, nextstranger[a] - 1]$$$, since $$$a$$$ knows everyone afterwards up until nextstranger[a].
      • In other words, the largest good subsegment that begins with $$$a$$$ is $$$[a, \min (b, nextstranger[a] - 1)]$$$.
    • If we now iterate $$$i$$$ from $$$n$$$ to $$$1$$$ (descending order), we can now find the largest good subsegment that begins with $$$i$$$. The base-case is when $$$i = n$$$, where the largest good subsegment is obviously $$$[n, n]$$$.

    My submission: 184766262

    I used non to refer to nextstranger and cut to represent the person right after the longest good subsegment ends, i.e., for a given value of $$$i$$$, cut becomes the minimum of nextstranger[i] and the previous cut (i.e. the cutoff point for the largest good subsegment that begins at $$$i + 1$$$).

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

      can you please explain the variable cut? I couldn't understand it clearly.

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

        When considering the largest good subsegment that begins with $$$a$$$, the variable cut represents the cutoff point, i.e., the largest good subsegment that begins with $$$a$$$ is $$$[a, cut - 1]$$$ and it has length $$$(cut - a)$$$.

        How do we calculate the current value of $$$cut$$$? Let $$$cut'$$$ represent the cutoff point for the largest good subsegment that begins with $$$a + 1$$$, i.e. the subsegment is $$$[a + 1, cut' - 1]$$$. Now, if $$$a$$$ knows everybody in the range $$$[a + 1, cut' - 1]$$$, then $$$cut = cut'$$$. But if not, then we should set $$$cut$$$ to be the first person in this range that $$$a$$$ does not know (which we already calculated as $$$non[a]$$$). We can cover both of these cases by simply setting $$$cut = \min (cut', non[a])$$$.

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

Worst contest of my life, i hate it :( T_T

»
19 months ago, # |
  Vote: I like it -37 Vote: I do not like it

Really upset about problem C. I had a beautiful Python/PyPy solution but it kept timing out on pretest 3 :/

import math

for _ in range(int(input())):
    input()
    a = list(map(int, input().split()))

    # https://cs.stackexchange.com/questions/93030/
    if math.lcm(*a) == math.prod(a):
        print("NO")
    else:
        print("YES")
  • »
    »
    19 months ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    This solution is too long, because lcm(a) and prod(a) can be ~ 10^(n * 9).

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

      The included link says that that calculating the LCM this way can be O(n k), with n being the amount of numbers (10**5) and k being the amount of digits (9). So it should really pass, unless the Python implementation is inefficient.

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

        I think the problem is doing math.prod(a). I think the Python implementation of this function is inefficient because according to this forum thread, Python uses Karatsuba algorithm to multiply big numbers instead of a Fast Fourier Transform-method like Schönhage–Strassen algorithm

        The link about LCM you used also assumes multiplication is $$$O(1)$$$ time, which is not true when your numbers are this big, so taking the LCM of the whole array like this may also be slow.

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

    math.prod(a) is so huge number... power(10, 9 * 1e5)

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

    It's actually possible to get AC with your formula with some constant factor (and some other) improvements.

    for example: 184805714

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

How was the round? I personally found it a bit hard.

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

Is there eratosphen's sieve solution of C?

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

    Yes, but it will probably FST (184750417).

    Idea

    UPD. It passed

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

      Daaamn, I did exactly the same, but got TLE, so gave up on this idea: 184746680

    • »
      »
      »
      19 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it
      if (x > 1) {
        cnt[x]++;
        if (cnt[x] > 1)
          good = true;
      }

      What's the significance of this part of the code? How do we know for sure that this remaining part of x (if(x>1)) will be the prime number

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

        actually never mind

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

        There can be at most one prime divisor > $$$\sqrt{n}$$$.

        Proof. Let's prove it by contradiction. Let $$$p$$$ be the first such divisor and $$$q$$$ be the second. Then the least number divisible by both $$$pq > \sqrt{n} \cdot \sqrt{n} = n$$$. Contradiction.

        So this part of code is only needed if $$$x$$$ is a big prime number.

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

        I think it's because you keep all primes in map, so every incrementing of prime's count works for logn. Try to count primes under sqrt(1e9) in vector, and over sqrt(1e9) — in map, should help (Also, I would check if m[v[i]] > 1 after the prime decomposition)

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

      Hey can you tell me the idea/proof as to why this approach works?

      It would be a great help!.

      [UPD : nevermind i got it, thanks.]

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

Why am i getting TLE. What's the time complexity of my code. Please tell.

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

    If $$$n$$$ is a large prime or a product of two primes $$$p, q$$$ such that $$$|p-q|$$$ is small, your factorization algorithm degenerates into $$$O(\sqrt{n})$$$ which is unable to pass.

    I am so dumb that I have to nuke it with the Pollard Rho algorithm after failing 7 times, sigh~. Look my submission 184795924 when available.

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

Tfw you nuke C with Pollard's rho algorithm and Miller-Rabin because you're too stupid to solve it normally. :cry:

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

    Not sure of system tests though but the basic solution passed.

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

      I don't think that'd work, what about this input:

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

        I also think so it should not work.

        But let's see system tests are on now.

        Also A very bad problem in a cp contest who expects one to know these heavy math number theory algorithms. It is a very bad problem

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

          No, I'm wrong, it does pass on this input.

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

          i don't think A is that bad and also this problem doesn't require "heavy math number theory" at all

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

I feel in B, i'm trying to solve B in div1.

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

    Any idea why Runtime error for such a code?

    I also got it for few of my submissions. Still couldn't find out why !

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

      assert(condition) terminates the program with exit code = 3 which results into runtime error if the condition is not true.

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

    sample explanation in B also does not have latex

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

      Even worse than the incorrect constraints

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

Problem B was stolen from 652C - Foe Pairs

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

Probably the worst contest I've ever seen.

Glanced at all problems and know how to solve them in one minute with no any interesting points.

C: know how to factorize large numbers with pollard or things?

D: very obvious and classical dp from one dimension to tree. though I dont know what's wrong with my code.

E: standard dp -- crafting the largest H C F O I D ....

F: also very standard online ds problem. I didnt get time to solve it bcz of D.

Also A and B is very terrible. It's not beginner friendly and it introduces some tricky cases to let many newbies to fail.

I can't remember the last contest with such bad quality was — I assume it should be on 2015 or before. Anyway I did not AK this contest but I got a very bad impression on the whole problemset. That's it.

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

    I used sieve for C — worked well within the time limit.

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

    I disagree.. The contest was good. B was very good. (It required a bit more thinking unlike usual Div 2 B where you just see the problem and start coding, also no tricky edge cases were there for me least).

    Even though I wasn't able to solve C. I guess that's what makes the problem good. Must have missed some observation.

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

      can you share your approach of B?

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

        i was not able to implement it on time but i think we had to subtract all subarrays starting from 1 to n contianing x and y from n * (n + 1) / 2, for all unique pairs and after that we have to add those subarrays which were counted more than once. it was a question of permutation and combination i guess! i hate it :(

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

          when you're trying to solve an A or B problem in a div2 contest, try not to make it complicated, think it in an easier way

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

      If you think problem C is good bcz it checked if people with good factorization tools or not, then you should check other problem Cs in past contest rounds.

      Please improve your taste before improve your rating.

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

        I'm pretty sure that intended solution DOES NOT involve those weird factorization methods. (Although people overkilled it..but I don't care about "other" people).

        It has to be simple and elegant, and such problems are really good, whose solution is actually simple yet it doesn't strike easily.

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

          YEs exactly. Don't say a problem bad by just seeing it. There is a solution which passes within 100 ms. Try to find it rather blaming that problem man. Though I personally think time limit should have been more restricted to filter out this factorization solution. This factorization solution is seems pretty straight forward for me. Just personal opinion.

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

            Yea within 100ms you mean these totally wrong submissions which got accepted due to the weak tests?

            Just let you know, all < 100ms submissions have been hacked. I cannot learn anything from here.

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

          The problem is if you know some fast factorization tools (like pollard-rho), you can just use it with 0 minute of thinking.

          So it become kind of knowledge checking problem, if you know it, you kill it instantly, and if you don't, you will need to making observation and have more penalty then the other.

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

      if they wanted intended to be sieve, then they should have lowered the limits, my sol just uses a extra set and doesnt pass

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

      It was "good" because you solved it, let me guess! Segments for a B with some corner cases to think of is an utter shit for B div 2

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

    this basically sums this contest up

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

    can't agree more... I didn't see any interesting problems in this contest

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

Not bad for today! Thanks _HossamYehia_!!

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

    What was not bad ? Round has 3 nice problems with more or less short statements — A, C, F. Everything else is shit on a stick

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

How to do C? :(

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

Contests like these always bring my little bit hope left down, i just don't know what to say.. feeling so sad right now

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

Why this solution (184800271) for C gives WA???

I am generating all prime numbers up to $$$\sqrt{10^9}$$$ because if $$$xy=z$$$ then $$$min(x,y)\leq{\sqrt{z}}$$$.

Then I am looking for two multiples of every prime number generated.

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

    It's not enough to check until 10**4.5, you do need to check until 10**9. For example, you might have 2*192763567 and 3*192763567 in the data set (192763567 being prime).

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

      Just check and factorize every number until sqrt(n). The number remaining would be the remainding prime!

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

If only F were 512MB instead of 256MB. I'm depressed... My solution using sqrt decomposition.

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

    can u explain ur sqrt decomposition logic ?

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

    I managed to write a solution using sqrt decomposition that passes, but just barely. I had to implement range paint using a vEB tree instead of DSU (which turned out to have a better constant factor than making the log log n faster than the inverse_ackermann n for this problem).

    Explanation of the solution: Divide the array into B blocks. Then process each block individually like this: Look at each value that occurs in the array, but not in the block. Assume the left bound of some query is inside the block, and the right bound is outside the block. Then if the answer is a value that isn't in the block, it must occur an odd number of times outside the block. And which is the smallest of these for a given right bound does not depend on the left bound, since the left bound is inside the block, and the block doesn't contain the value. So by range-"painting" values you can compute the answer for every right bound, assuming the left bound is inside the block and that the answer is not a value inside the block. Range painting can be done in O(n log log n) with good constant factor using a vEB tree.

    Then to answer a query, you can look only at the block corresponding to the left bound of the query. Brute force count how many occurrences there are in the range of each value that appears in the block. There are n / B values in the block, so this can be done in O(n / B * log n) time by binary searching in arrays of positions of occurrences.

    Then take the minimum of this answer and the pre-computed answer for the right bound in the block.

    Total running time is O(qn / B * log n + Bn log log n). Code: 184822603

    Had to steal some fast IO from nor and vEB tree from mango lassi and nor to make it pass.

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

It was hard :D

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

Entire contest I was searching for some efficient solution of C, at last tried brute force and it worked. Do the brute force really for C or am I gonna get FST?

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

Weird round. D was easier than C ;_;

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

It's midnight in most of Asia and I'm regretting my sleep.

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

problem a is just same as https://mirror.codeforces.com/contest/459/problem/B but with *2

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

When approaching problem A, if the maximum and minimum values were different, i multiplied the number of maximum and the number of minimum and multiplied by 2, and if the same, i gave n * (n — 1). Why is A wrong? https://mirror.codeforces.com/contest/1771/submission/184799055

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

C is way too standard, but its hard to optimise your solution

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

    got it

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

      I guess because of overflow

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

      I can assume, if you are working with C++ the set of numbers can be of arbitrarily large primes, thus the lcm can be as much of 10^40(each of the ~10^5 numbers are different ~10^9 primes). I don't know if this can work in python due to the bignumbers

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

For A if the smallest number != largest number the number of occurrence of the smallest element * the number of occurrence of the largest element * 2 ;

else if all elements are same nC2 . why won't this work .

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

I feel that constraints on problem C should have been either tighter or looser because solutions using Sieve and then factorizing each number using a list of primes and storing number of occurrences of each factor are barely passing and even failing for a few submissions depending on how the code has been written, which isn't fair to everyone

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

    can u share ur solution plz ? :)

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

      I generated the list of primes up to 31622 (sqrt of 1e9), and 3401 primes are less than 31622 (I checked this after generating).

      After this, I created a map, facs, to store the number of times each prime factor has occurred in the prime factorisations of the elements of the array (this will require roughly 3400 operations at max to check for each prime number less than sqrt(ai)) and then if anytime, we get that a prime p divides ai and after doing facs[p]++ if facs[p]==2, then we are done and can output yes else if we have finished traversal then we can output no.

      You can check code here

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

        How do you estimate time complexity of this? I thought of same thing but I assumed no. of operations as 3*10^3 * 10^5 (correct me if I'm wrong here). I thought that's not the number of intended operations for given Time Limit forcing me to think other ways. I tried my luck by submitting some bullshit at last moment which of-course failed

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

          I got the same complexity, roughly 3.4*10^8 operations (you can do roughly 10^8 operations in 1 sec, so I gave it a shot), and somehow it fits in at 2.4 sec for me, which is why I feel the constraints were not fair to everyone as whether or not your code passes depends on your implementation too

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

            It took you 2.4 sec in C++, I'm sure it won't work in Python, until they come up with solution that works with all language this is a really bad problem :(

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

        damn, I just randomly checked 100*n pairs of indexes and if their gcd is 1 or not bc I thought it will give tle.

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

        This doesn’t pass in python

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

          I think it is possible to make it pass in python ... I think this user has done it.

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

        but how does this pass? , we have 1e5 elements in the array , for every one of them we will go through 31622 numbers to check , which then becomes 1e5 * 31622 , this is 3162200000 ~~ 3e9 , so i don't get how this is not a tle , can u plz explain ?

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

          nvm , i get it , we have 3401 primes , it becomes 3401*1e5 ~~ 3e8 :D

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

please tell the idea of C .. I thought sieve will simply give TLE so gave up that idea ...

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

C easy than A

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

Porblem C explain ... Basically How to find prime factors of a number<=1e9 in log(n)?? help....

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

    There are only 3401 primes smaller than sqrt(1e9) so you only need to check for those primes. Then, once you are done dividing by all the primes, if the number left is greater than 1 then it is another prime.

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

      so for each no in the array if I do this .. complexity can go upto 3401*n if all the numbers are a prime bigger than sqrt(1e9) . which will be 10^8 . Why wont it give TLE ?

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

        I feel like 10^8 operations shouldn't TLE for one second and also this problem gives 3 seconds anyway.

        To be fair, I know mod is slower than the other operations, so maybe one second is cutting it close but it should be fine for 3.

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

    Square root of 10^9 is 31622. There are atmost 3402 primes in 31622. There are 10^5 numbers and try to prime factorize by 3402 primes. Complexity O(n*3402) will pass.

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

      i Had this silly rule till now that 10^8 give a tle .... :(

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

        Same, I thought operations should be in order of 10^6 for a second time limit

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

      Will this pass in python as well?

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

      I saw your solution. My question is about your inner loop which at most can run 30 times. why you did not count complexity analysis. Can you give me an explanation, please? I think the complexity of your code would be O(n*3402*30). Please explain.

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

        No. It's always up to O(n*3402). Because of, while inner loop is true, d[i] reduce by d[i]/prime[j]. If you notice carefully you will see, middle loop up to sqrt(d[i]). So reduce d[i] always reduce middle loop.

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

https://mirror.codeforces.com/contest/1771/submission/184787882

Anyone knows why is this wrong at pretest 3? Idea: Check all routes from one leaf to another. I could understand this getting TLE'd, but not WA

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

Constraints on C in fact very tough. It is easy to notice that there is $$$P=3500+-$$$ primes up to $$$\sqrt{10^9}$$$. But I think a bunch of people thought that $$$O(n*P)$$$ would get tle. moreover, we have some sets or hashtables that also affect the time complexity. Also, $$$O(n*P)$$$ theoretically should get tle

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

    I thought it will get TLE, so I didn't write it. Too bad.

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

      Same for me, I don't recall ever seeing CF problems where the intended solution is that slow. I hope that there is a more "elegant" solution that I'm missing.

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

    You can avoid hash table by taking a 3500 length array for storing frequency of each prime, but I agree that it was not clear that $$$3.5e8$$$ modulo operations would pass in tl.

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

    True. I got TLE using python

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

Oh, in problem D, my solution works for $$$n^2\cdot26$$$, I thought it would pass, The asymptotics match, after all.

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

For D, I tried finding the longest palindromic subsequence for each leaf-to-leaf path.

Is this approach wrong, and if so could someone please explain why :3

My submission: https://mirror.codeforces.com/contest/1771/submission/184793847

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

What is the intended solution to C?

Is it the $$$O(n \cdot \pi(\sqrt{a_i}))$$$ solution? (where $$$\pi(x)$$$ is the number of primes less than $$$x$$$) I was hesitant to submit it for some time since ~4e8 ops in 3s felt risky.

Also, I don't know if I'm just being dumb, but in E why can't we just try all horizontal parts in $$$O(n \cdot m^2)$$$ and for each check the longest possible vertical segment in O(1)?

By "check the longest possible vertical segment in O(1)" I mean:

  • Store first bad above / below each point.
  • Store first and second medium above / below each point.
  • Use the above two to compute how far we can extend each part (top left, bottom left, top right, bottom right).
  • If we haven't used the medium in the horizontal segment, try it in all 4 parts (using second med above / below) and take the max of all.
  • »
    »
    19 months ago, # ^ |
      Vote: I like it +8 Vote: I do not like it

    about problem C. I was hesitating for about an hour, and only after giving up decided to submit 3e8 '/' operations and it did not TLE for some reason, still not sure why

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

      C++ can do about 1e8 operations per sec. So 3e8 is done in 3 secs. And this is number theory, everything's faster than should be because a lot of cases are just skipped.

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

    Good lord

    I desperately tried to find a better solution and brushed off the idea that it doesn't pass because of python. Because it would be so weird to have language problems in d2C (and because I was too lazy to rewrite it today)

    Also it means C was a very straightforward problem with tight constraints.

    And now I see that there are only 10 successful submissions in pypy3-64 and most of them had to use some magical rho algorithm I have no idea about...

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

    Yeah, I did same stuff in E.

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

    For problem C, I just used Pollard-Rho, which is complexity $$$O(n\cdot (a_i)^{1/4})$$$. My submission runs in time but still takes over one second, so I wonder if there is a faster solution.

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

      so you know that if x is not an prime number there will be a prime divisor of it <= sqrt(x) so it is max about sqrt(1e9) and the number of primes number up to sqrt(1e9) is about 3400 so you just need to fact the x by 3400 prime number

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

    I did something very similar to yours; the technique is similar to sweepline but easier: 184788266. Funny how I solved E before C. ¯_(ツ)_/¯

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

Never felt so frustrated... Thank you! :|

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

As a participant, C and D were complete garbage

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

    How do you do C?

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

      I didn't solve it. I have just looked through the solutions after the contest.

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

    D was ok, C is indeed.

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

      D seems quite standard. But, alright, I have seen worse Ds.

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

        idk how to solve it, i know array dp but not with tree

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

          Well, it's quite similar. You can make transitions in the order of d[v][u], where d is the distance between v and u. If you sort all the pairs by d, you can make dp transitions, which is basically dp on array, if you know the parents of the vertices on the path

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

hey can someone tell me why this gives tle:

https://mirror.codeforces.com/contest/1771/submission/184791207 i know its o(n * sqrt(N))) where N = 1e9 but what is the diffrent between this and the prime factorization approach since its also suppose to be the same complexity

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

    sqrt 10^9 is 3x10^4, in total it can degrade to > 10^9

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

      but people discussed above in the comments solutions that have the same complexity but it passed but maybe it fst after system test thanks anyway ps : n = 1e5, N = 1e9 just saying

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

        In the prime factorisation approach, you only check all primes till sqrt(1e9), which comes to be around 3e3. While you are checking all numbers till sqrt(1e9).

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

An unpleasant contest, a lot of newcomers fell for int in A, solutions on the verge of TL in C and D. When I was taught to do contests, they said it was not good to catch a constant or log, because there would be those who wrote a sloppy correct solution, but would not be able to pass it.

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

What is wrong with my A task submission ?

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

    int n;

    n*(n-1) is int, and overflows when $$$n=10^5$$$

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

Hi!! can anyone tell where can i find the editorial??

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

I'm unable to find out why this code fails for pretest 3 for A. please help me

#include <bits/stdc++.h>
using namespace std;
int main()
{
    int t;
    cin>>t;
    for(int i=0;i<t;i++){
        int n, a=1, b=1;
        cin>>n;
        int x[n];
        for(int j=0;j<n;j++){
            cin>>x[j];
        }
        sort(x,x+n);
        for(int i=0;i<n;i++){
            if(x[i]==x[i+1])a++;
            else break;
        }
        for(int i=n-1;i>0;i--){
            if(x[i]==x[i-1])b++;
            else break;
        }
        if(a==n || b==n)cout<<n*(n-1)<<"\n";
        else cout<<a*b*2<<"\n";
    }
    return 0;
}
  • »
    »
    19 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    You're using int, the product of a and b may overflow.

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

    solution:

    long long n, a=1, b=1;
    

    or

    if(a==n || b==n)cout<<1LL*n*(n-1)<<"\n";
    else cout<<1LL*a*b*2<<"\n";
    
»
19 months ago, # |
Rev. 3   Vote: I like it +1 Vote: I do not like it

EDIT: I'm sorry, this idea won't work, since it should trigger integer overflow. It passed pretests though, but will likely FST. This is what I wrote, if anyone is interested (but it is not supposed to pass):

C does not need a sieve or anything more complicated than Euclid's GCD algorithm.

All you need to do is maintain a running LCM. Initially, the running LCM is just the first element of the array. Check the GCD of the running LCM and the next value. If the GCD is not 1, then there must be an overlapping factor between this next value and one of the earlier values (doesn't matter which), so the output is YES. Otherwise, update the running LCM (by multiplying the current running LCM with this next element that we just found to be coprime to it) and move on. If we read the entire array, and the GCD was always 1, then the output is NO.

My submission: 184790195

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

    You can run into overflow with multiplying?

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

    Am I missing something or is SIGNED INTEGER OVERFLOW on vacation?

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

    Hi, your LCM will overflow very very fast.

    Here's a test that breaks your solution

    1 10 999999937 999999929 999999893 999999883 999999797 999999761 999999757 999999751 999999751 999999757

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

      Oh, crap, pretests didn't cover overflow. I'm sorry!

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

        u gone now

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

          I think this is the first time in a very long time that I only solved two problems in a Div2 round. My rating is gonna drop like a rock :(

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

My solution for A has fallen in the system test because i forgot to print a new line in in the case when all array is equal , i hope you can skip this mistake as it is a presentation error and it is also not included in the pretests , i was about to get back to specialist and i hope you MikeMirzayanov can consider it correct.

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

    same, but it's a dumb mistake from both us and those who made pretests lol. Also, C's pretests kinda weak too.

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

      i agree it's a dumb mistake but there should be a strong pretests so that i can look back and fix it , also it is not some corner case or overflow issues , i hope the system can consider our solutions correct

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

Fuck so close to solving D. It’s just going level by level and do DP.

no idea how to solve C.

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

    You just need to know that there are O(sqrt(M) / log(M)) primes from 1 to M. Then You can just check, if there are 2 numbers that both divide a prime below sqrt(10^9) ~= 35000. Also you should divide each number on all primes below sqrt(10^9). Then you'll have either 1 or a big prime. Then check if there are 2 primes.

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

What is idea for D, i know solution dp n^2 for 1d array with size n and that solution must be between 2 leaves in tree but thats it.

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

Pretests were comparable to a steaming pile of shite

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

Wow!! what this pretests. Screenshot-2022-12-11-201844

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

.

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

WTF was C?

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

I FSTed C 184739561 on test 16. I typoed and only factorized out 2 and 3. This passes 15 tests...

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

184778086 is not correct

184778210 also

184766650 also

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

Problem F is a specialization of 1479D - Odd Mineral Resource. (Technically, that problem doesn't ask for the minimum value but most solutions for that problem will find the minimum anyway.)

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

    In Odd Mineral Resource the queries are not online so parallel binary search + sweepline fenwick tree can be used, but in problem F a persistent segment tree is required. The two problems are still really similarly though

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

      True, I forgot about that. I tried the persistent segment tree solution for Odd Mineral Resource so it was the same to me.

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

Weak pretest.

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

:)

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

I'm just much surprised that how my solution for problem C got accepted in system testing (It shows that main tests are really weak), can anyone hack it? 184797036

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

Can this idea work or is just way too slow even with a better implementation? (Problem C):

https://mirror.codeforces.com/contest/1771/submission/184805467

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

    I think approaches with sieve on Python get TLE on this problem. I also kept getting TLE during the contest. But when I re-implemented the same approach with C++, I got AC.

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

Very weak pretests for $$$C$$$.

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

What is wrong with my solution of A? It fails on 24th test. 184739221

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

    I think you need to remove the "else" from:

    else if(v[i] == minn){
    to:
    if(v[i] == minn){
    
»
19 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Got TL on F in system tests. Replaced map with unordered_map, got at least 10x speed-up on test 30: before that I was getting TL on test 30, but with unordered_map it works under 150 ms. It was log(N) per query anyway, and I was still using std::map O(N) times, but changing coordinate compression container to unordered_map somehow miraculously sped up the program. Just wondering, is it okay that such a small change caused that much performance loss?

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

    „Small change”? unordered_map is a hash map whereas map is a BST.

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

      Yeah, but the size of the map was at most 2*10^5 (also at most 4*10^5 queries), and it shouldn't be anywhere close to time limit. As AlternatingCurrent pointed out, it seems like it is a problem from C++ standard library.

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

    The same problem was mentioned in this blog. It seems like a problem from c++ itself :(

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

how to solve F?

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

    Main idea is that if you take xor of numbers, numbers that will appear even number of times will cancel out from xor. To find smallest odd appearing number you can just binary search for minimal i that xor of numbers less or equal than i is > 0, with segment tree. To answer queries in a segment, you can use persistent segment tree. There are also cases when xor of numbers is zero (like 1, 2, 3) but there are numbers that appear odd number of times, but it can be fixed with just mapping numbers to random 64bit numbers, and the probability of xor being zero will be very low (don't know how to prove it).

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

      wow that's why there was mt19937 in accepted codes. thank you

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

      Here is the proof of probability of two randomly chosen subset's xor being equal is very low.
      please let me know if anything is incorrect..
      Say there are k basis elements out of n elements in the array..
      claim: Then the probability of xor of two different subset being equal is ~ $$$1/2^k$$$..
      (note that k can be atmost 64)

      Assume that, for first 64 numbers of array, we map them all to two powers(eg 1,2,4,8,....)...resulting in first 64 number being linearly independent to each other(ie: any of them cant be represented as xor subset of other)... and all further numbers(i>64) can always be represented as linear combination of first 64 numbers(ie: as some xor subset)...

      Directly to the proof: There are total $$$2^n$$$ subsets possible..
      Thus N = $$$2^n*(2^n-1)$$$ pairs of subset..
      Let Z be number of pairs of subsets with equal xor..
      claim: Z = $$$2^n*(2^{n-k}-1)$$$
      proof:
      1. There are $$$2^k$$$ unique xor values out of $$$2^n$$$ subsets xors.
      2. In that, each unique value is repeated exactly $$$2^{n-k}$$$ times..
      refer: https://stackoverflow.com/a/72195021/15971867

      \begin{Bmatrix} x_1 & x_1 & x_1 & \cdots & x_1 \cr x_2 & x_2 & x_2 & \cdots & x_2 \cr x_3 & x_3 & x_3 & \cdots & x_3 \cr \vdots & \ddots & \ddots & \ddots & \vdots \cr x_{2^k} & x_{2^k} & x_{2^k} & \cdots & x_{2^k} \cr \end{Bmatrix}

      Thus number of ways in choosing pair of subset such that their xor are equal, is number of ways choosing two different subset along same row in above matrix...
      (note that here each xi is the subset(xor-ed).)

      There are $$$2^{n-k}$$$ elements in each row..
      thus there are $$$2^{n-k}*(2^{n-k}-1)$$$ such pairs in each row, and there are $$$2^k$$$ rows, hence $$$2^k*2^{n-k}*(2^{n-k}-1)$$$ pairs total..

      So, probability of choosing pair of subset with equal xor value is
      P = Z/N = $$$\frac{2^n*(2^{n-k}-1)}{2^n*(2^n-1)}$$$
      ~= $$$2^{-k}$$$
      which is very low for k = 50..

      Note that, it seems even if we take all numbers as random from the beginning, still it works..
      So, for upto n<=64, if we choose n random numbers, then there are high chance that all of them being independent..(I dont know to prove this.)

      upd: I have proved it here that If you generate some n random numbers, then atleast first 50 of them will be linearly independent of each other.. (atleast first m, with probability 2^m/2^64 in general.)

      Here is the modified jiangly's solution with first 64 numbers as two powers and remaining are just filled with unused natural numbers starting from $$$2^{25}+1$$$. (i=64 to n are then shuffled to avoid hacking) ref:https://mirror.codeforces.com/contest/1771/submission/184878249

      note: it is better to choose random number instead of continuous numbers, cause if you dont shuffle them, then xor of all numbers between 4k1+1(or 3) to 4k2+1(or 3) for any k1<k2 will be equal..
      Also even if you shuffle, the code is prone to hacking... for example, By looking at above accepted code, it is known that there exist {$$$2^{25}$$$,$$$1$$$,$$$2^{25+1}$$$} in the array, hence for n = 65, by just choosing all 65C3 combinations in each query, one can exploit this triplet.

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

Hi! We know about problem with C task. Now we are trying to fix it.

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

Not a good contest, The time limits are absurd. The problems are weird. I literally had my heart in my mouth while systests. I think either solution should pass with ok margin or tle in pretests. Staying on the border with dumb luck passing or failing solutions doesn't make much sense.

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

The rating for Codeforces Round #837 (Div. 2) will be rolled back until the end of the investigation of the incident with problem C.

What was the incident? Was there a problem with the tests or something?

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

Can anybody help me find out what's wrong in my solution to question A.Thanks in advance

https://mirror.codeforces.com/contest/1771/submission/184726214

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

    Maybe in the general case output it takes it as an int. You could try to precompute the answer as a ll and then output it that way

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

    The C++ STL count function returns an unsigned int and you need to typecast it to long long while outputting, which you didn't and so you are getting WA due to overflow

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

    use long long

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

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

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

Bruh

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

For me, this round was very unusual and tricky. The problems were challenging and hard, but the contest was good. Solved B and F, but not A, C, D or E. <3

»
19 months ago, # |
  Vote: I like it -20 Vote: I do not like it

Problem B is exact copy of this problem: https://mirror.codeforces.com/contest/652/problem/C

Make this contest unrated.

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

    Well, a lot of easy problems look same. There are not many ideas for div2A and div2B. And ofc the idea of problem B is well known. And if we made every round, where problem A or problem B is not 100% unique, unrated, there would be no rated contests

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

Put the damn editirial slready , pls

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

    If my country was in World Cup Semi-finals I wouldn't care about editorial, wouldn't even do a cf contest lol

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

Dont know why people hating b imo b was very easy here is my submission link https://mirror.codeforces.com/contest/1771/submission/184805442

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

Have the ratings been finalised or still solutions are being rejudged?

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

problem D was easier than B in my opinion , i regret i didn't read it during the contest and kept trying to solve B

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

"I'd especially like to thank: MikeMirzayanov , for the amazing Codeforces and Polygon platforms."

Tbey are such amazing platforms that they even remind you (pretty adamantly) to tests the inputs for inconsistencies

»
19 months ago, # |
Rev. 3   Vote: I like it -17 Vote: I do not like it

i

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

Worst generator for C

By the way, it's harder to write the generator than to come up with this test. I think 256KB limit for the hack is sometimes tight.

»
19 months ago, # |
  Vote: I like it -12 Vote: I do not like it

I switched long long to int in problem C and it passed. :/

»
19 months ago, # |
  Vote: I like it -11 Vote: I do not like it

Can anyone help me with this or this submission where I got TLE for O(max(n,m)) complexity in problem B?

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

    you are creating a vector of size 1e6 in every test case.

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

      And also it'll give wrong answer (for m=0 atleast).

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

In problem C, I submitted the same code in pypy3 and pypy3 64bit but the code gave TLE in pypy3 64bit and AC in pypy3 .
- Is this a problem with pypy64 bit ? why this difference happened?

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

Unfortunately, it was found that the validator in the problem C allowed the case n = 1. We found all the participants whose result was affected by this issue (146 in total), for them the round will be unrated. For other participants, the round remains rated.

We apologize for this incident. :'(

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

    Ratings updated preliminary, it will be recalculated after removing the cheaters.

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

    Instead of declaring round unrated for some people, validator should have been corrected for above mentioned case. Due to mistake in creating test cases, declaring round unrated for some participants is totally senseless.

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

      Validator has been fixed and it affected mentioned 146 participants and their solutions have been rejudged.

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

    I saw this kind of judgement (some participants are unrated) sometimes, but how about the case for those who have good $$$+\Delta$$$ still with some negative effected troubles? I think the participants can choose their rated/unrated, or, everyone is unrated is fair. 146 participants are not a small number to decide to make the whole round unrated.

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

I'm a little frustrated with problem A. I was stuck on this problem for over an hour. In the condition of the problem, 1<=n<=10^5, but the problem fails when n is an int number.

Some submission in during contest — https://mirror.codeforces.com/contest/1771/submission/184727850

Fixed (int to long long) — https://mirror.codeforces.com/contest/1771/submission/184836287

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

So C needs a precise execution time estimation (provided that we don't use advanced number theory algorithms).

Some discussions on Codeforces about the number of operations C++ can do per second:

Blog 1

Blog 2

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

»
19 months ago, # |
  Vote: I like it -28 Vote: I do not like it

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

how to solve problem c?

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

    just check, if there minimum 2 even numbers in the array. If so, then yes. Because a pair of even number has at least one common divisor which is 2.

    Otherwise you have check with prime factorization using sieve.

    Just store the primes factors of every element of the array in a map.

    Every time, before storing a factor, just check whether this factor stored before or not.

    If not found, then print No at the end.

    If needed you can check my solution : 184772682

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

      According to your explanation, wouldn't the time complexity be like n x |{Primes}|? What if n numbers are all large prime numbers? Could you elaborate on the time complexity aspect?