_HossamYehia_'s blog

By _HossamYehia_, 2 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

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

waiting for the round.

»
2 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

  • »
    »
    2 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..

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

      there is NO XOR problems

      So you want XNOR problems?

      • »
        »
        »
        »
        2 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.

  • »
    »
    2 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

  • »
    »
    2 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.

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

      cap

    • »
      »
      »
      2 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 ?

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

        How did you approached B can you explain here please. It would be very helpful.

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

WOW .. Egyptian round . Good luck bro

»
2 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.

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

Good Luck EVERYONE! (◠‿◠)

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

 CAN ANYONE RELATE ;)

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

After a long time. Best of luck Everyone.

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

After a long long break. Missed the rounds badly.

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

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

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

No interactive problems?

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

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

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

finally a contest

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

An Egyptian round !!(❁´◡`❁)
I am so excited ❤❤

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

Good luck everyone ;)

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

As an Egyptian, I hope this round isn't all about bit masks

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

After a long day...

»
2 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

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

My first Egyptian round (My lovely country), so i'll memorize this round, i hope +ve delta for me and everyone.

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

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

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

long time no see kiddo, _HossamYehia_

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

Egypt <3

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

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

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

Finally after a long time..YAY!!!

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

As Egyptian I love how we are here.

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

I am best

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

Can't wait for the contest. The codeforces contest creators had enough vacation :)

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

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

»
2 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?

  • »
    »
    2 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.

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

Can't wait to see wangzheng2008's performance.

»
2 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.

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

Hope to become pharaon this round

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

Codepairses

»
2 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.

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

E has a strong ROI 2015 in Arkhangelsk problem 6 vibe

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

Bloody Hell. What a pairful round!

»
2 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

»
2 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...

  • »
    »
    2 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.

    • »
      »
      »
      2 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.

    • »
      »
      »
      2 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;
      }
      
»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

How to solve B?

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

    i was thinking in the direction that ith and (i+1)th friend must not be connected in the given m queries, though kept failing 3rd pretest

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

      bro you leave the case of all number are same in an array, eg; 1 1 1 1 1 if n=5, 6 6 6 6 if n=4 in this case the ans = n*(n-1).(becoz for every element there in (n-1) combination for 1 there is n-1 then for n it is n*(n-1)).

  • »
    »
    2 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.

  • »
    »
    2 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$$$).

    • »
      »
      »
      2 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.

      • »
        »
        »
        »
        2 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])$$$.

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

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

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

    me frfr.. A- easy B- meh cool C- easy, done, submitted----why does it not work!!!!! D- okay can do this, coded, submitted---- might just pass the TC,- TLE,TLE,TLE,TLE

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

    Yeah same for me, for me, I found C difficult. WA x4 and the memory limit exceeded. Quite painful since I was expecting to solve C :(

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

    I can't solve 1 problem

    In first one I did 10 wrong submissions which takes all the time, then I realize one case of all same number was missing

    Hope so To perform well enough in the next contest

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

    +1

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

TL on problem C

»
2 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")
  • »
    »
    2 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).

    • »
      »
      »
      2 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.

      • »
        »
        »
        »
        2 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.

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

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

  • »
    »
    2 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

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

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

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

Is there eratosphen's sieve solution of C?

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

    find first 3400 prime numbers and rest is easy.

  • »
    »
    2 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

    • »
      »
      »
      2 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

    • »
      »
      »
      2 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

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

        actually never mind

      • »
        »
        »
        »
        2 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.

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

          Yeah I didn't considered that case initially BTW Thanks

    • »
      »
      »
      2 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it
      • »
        »
        »
        »
        2 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)

    • »
      »
      »
      2 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.]

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

      plz show me calculate the time limite Find all the primes below 109−−−√ and factorize each ai. Check if some prime occurs more than once. this idea

»
2 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
  • »
    »
    2 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.

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

      I thought there are 10^8 operations at most. which can be done in 3 seconds. :/

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

    Since you iterating over the whole array (max $$$10^5$$$) and on every iteration you are finding out the prime factors of $$$a_i$$$ (max $$$10^9$$$) in square root time.

    Therefore the total time complexity is $$$O(n \sqrt{a_i})$$$, which in worst case would be over the allowed limits.

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

i don't no why,but i think B was Harder than C . :+(

»
2 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:

  • »
    »
    2 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
    • »
      »
      »
      2 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
      • »
        »
        »
        »
        2 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

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

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

        • »
          »
          »
          »
          »
          2 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

»
2 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.

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

You need to fix your contest i guess? :)

https://codeforces.com/contest/1771/submission/184796886

  • »
    »
    2 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 !

    • »
      »
      »
      2 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.

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

    sample explanation in B also does not have latex

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

      Even worse than the incorrect constraints

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

Problem B was stolen from 652C - Foe Pairs

»
2 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.

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

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

  • »
    »
    2 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.

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

      can you share your approach of B?

      • »
        »
        »
        »
        2 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 :(

        • »
          »
          »
          »
          »
          2 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

    • »
      »
      »
      2 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.

      • »
        »
        »
        »
        2 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.

        • »
          »
          »
          »
          »
          2 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.

          • »
            »
            »
            »
            »
            »
            2 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.

        • »
          »
          »
          »
          »
          2 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.

    • »
      »
      »
      2 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

    • »
      »
      »
      2 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

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

    this basically sums this contest up

  • »
    »
    2 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

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

Not bad for today! Thanks _HossamYehia_!!

  • »
    »
    2 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

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

      Could have gone worse. For me, it was my first contest

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

How to do C? :(

»
2 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

»
2 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.

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

    • »
      »
      »
      2 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!

»
2 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.

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

    can u explain ur sqrt decomposition logic ?

  • »
    »
    2 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.

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

It was hard :D

»
2 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?

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

Weird round. D was easier than C ;_;

»
2 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.

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

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

»
2 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://codeforces.com/contest/1771/submission/184799055

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

    Use long long

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

      you mean when print the answer, 1LL * answer? the contest is closed now so i cant submit revised code.. I'm so upset. I want to raise my score but I don't know what to do

»
2 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

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

    got it

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

      I guess because of overflow

    • »
      »
      »
      2 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

»
2 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 .

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

    for the second case nC2 will actually divide the answer by 2 but answer must be n*(n-1)

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

      nc2 is if all elements are same . 2nd example case the elements were different right

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

      no, it's not nc2 because you're not selecting two elements independently, you're choosing the second number on the basis of the constraints imposed by the first number, simply said, the first number's index could've been one of n, and the second number's index could be one of n-1, (all except the first number's index since they can't have the same index)

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

    If all elements are same the answer is $$$n(n-1)$$$.

»
2 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

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

    can u share ur solution plz ? :)

    • »
      »
      »
      2 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

      • »
        »
        »
        »
        2 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

        • »
          »
          »
          »
          »
          2 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

          • »
            »
            »
            »
            »
            »
            2 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 :(

      • »
        »
        »
        »
        2 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.

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

        This doesn’t pass in python

        • »
          »
          »
          »
          »
          2 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.

      • »
        »
        »
        »
        2 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 ?

        • »
          »
          »
          »
          »
          2 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

»
2 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 ...

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

C easy than A

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

منو لله حسام حبيب

»
2 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....

  • »
    »
    2 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.

    • »
      »
      »
      2 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 ?

      • »
        »
        »
        »
        2 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.

  • »
    »
    2 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.

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

      • »
        »
        »
        »
        2 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

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

      Any idea why my solution gives TLE here

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

      Will this pass in python as well?

    • »
      »
      »
      2 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.

      • »
        »
        »
        »
        2 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.

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

How to do D ꒦ິ^꒦ິ

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

https://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

»
2 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

  • »
    »
    2 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.

    • »
      »
      »
      2 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.

  • »
    »
    2 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.

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

    True. I got TLE using python

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

great contest thx

EDIT: after VAR and discover it may be unrated contest it is second worse contest after this

»
2 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.

»
2 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://codeforces.com/contest/1771/submission/184793847

»
2 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.
  • »
    »
    2 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

    • »
      »
      »
      2 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.

  • »
    »
    2 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...

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

    Yeah, I did same stuff in E.

  • »
    »
    2 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.

    • »
      »
      »
      2 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

  • »
    »
    2 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. ¯_(ツ)_/¯

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

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

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

As a participant, C and D were complete garbage

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

    How do you do C?

    • »
      »
      »
      2 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.

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

    D was ok, C is indeed.

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

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

      • »
        »
        »
        »
        2 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

        • »
          »
          »
          »
          »
          2 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

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

Is click here solution is too slow to pass problem C ? please check this anyone's

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

    You are iterating over the vector v three times, all the reqd steps can be done in a single iteration while factorizing the number. Try doing that. Also the constraints are very tight, so avoid using functions.

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

hey can someone tell me why this gives tle:

https://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

  • »
    »
    2 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

    • »
      »
      »
      2 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

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

»
2 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.

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

What is wrong with my A task submission ?

  • »
    »
    2 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$$$

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

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

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

what is wrong with this problem B submission 184799218

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

    Gives wrong output for below input:

    Click Here
»
2 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;
}
  • »
    »
    2 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.

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

      This was my first contest and I was unable to find this and I submitted it 3 times with other variations. Thanks!!

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

    Overflow if all elements are same

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

    The result may larger than int,you should use long long

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

    you must using unsigned long long int type for variable n

  • »
    »
    2 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";
    
»
2 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

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

    You can run into overflow with multiplying?

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

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

  • »
    »
    2 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

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

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

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

        u gone now

        • »
          »
          »
          »
          »
          2 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 :(

»
2 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.

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

    Same here vro

  • »
    »
    2 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.

    • »
      »
      »
      2 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

»
2 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.

  • »
    »
    2 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.

»
2 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.

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

Pretests were comparable to a steaming pile of shite

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

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

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

.

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

WTF was C?

»
2 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...

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

This is my first div 2 contest and I was able to solve 2 problems (system tests passed)

I solved the second problem using set and sliding window technique, the solution is pretty intuitive and simple to understand, hence I thought of sharing it.

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

void solve(){
	int n, m;
	cin>>n>>m;

	vector<vector<int>> pairs;

	for(int i=0; i<m; i++) {
		int a, b;
		cin>>a>>b;
		pairs.push_back({a, b});
	}

	// create an adjacency list with the pairs
	vector<vector<int>> AList(n+1);

	for(vector<int>& edge : pairs) {
		AList[edge[0]].push_back(edge[1]);
		AList[edge[1]].push_back(edge[0]);
	}

	// we can solve this problem using set and sliding window
	long long result=0;
	int l=0;
	map<int,int> window;

	for(int i=0; i<n; i++) {
		while(window.count(i+1)) {
			for(int v : AList[l+1]) {
				window[v]--;
				if(window[v] == 0)
					window.erase(v);
			}
			l++;
		}
		
		for(int v : AList[i+1]) {
			window[v]++;
		}
	
		result += i-l+1;
	}

	cout<<result<<endl;
}

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    ll t;
    cin>>t;
    while(t--){
        solve();
    }
    return 0;
}
»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

184778086 is not correct

184778210 also

184766650 also

»
2 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.)

  • »
    »
    2 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

    • »
      »
      »
      2 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.

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

Weak pretest.

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

»
2 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://codeforces.com/contest/1771/submission/184805467

  • »
    »
    2 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.

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

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

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

What would be the expected rating of the first 2 questions?

»
2 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

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

    No clue, but I would suggest to convert all your variables to long long and submit again.

  • »
    »
    2 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){
    
»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Is it possible to hack solutions and get points? I think I see some wrong solutions for some questions but I don't know how to hack. They just need different input.

»
2 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?

  • »
    »
    2 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.

    • »
      »
      »
      2 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.

  • »
    »
    2 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 :(

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

how to solve F?

  • »
    »
    2 months ago, # ^ |