Invitation to CodeChef Starters 174(rated upto < 2700)

#	User	Rating
1	tourist	3856
2	jiangly	3747
3	orzdevinwang	3706
4	jqdai0815	3682
5	ksun48	3591
6	gamegame	3477
7	Benq	3468
8	Radewoosh	3462
9	ecnerwala	3451
10	heuristica	3431

#	User	Contrib.
1	cry	167
2	-is-this-fft-	162
3	Dominater069	160
4	Um_nik	158
5	atcoder_official	156
6	Qingyu	153
7	djm03178	152
7	adamant	152
9	luogu_official	150
10	awoo	147

Please note that the contest's rated range and duration has both increased. Further, the round is being held in ICPC mode with 10 minute penalty.

We invite you to participate in CodeChef’s Starters 174, this Wednesday, 19th February, rated for users with rating < 2700.

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

Note the round is being held in ICPC mode with 10 minute penalty.

Joining us on the problem setting panel are:

Contest Admin and Statement Verifier : Shreyan Dominater069 Ray.
Text Editorialist — Nishank IceKnight1093 Suresh.
Tester: Sushil SmolBrain Raaja ,priyanshu.p, rewhile, kHarsh3715, hashman, VladiG.
Setters:Yugandhar_Master, wuhudsm.

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

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

Good Luck!

UPD: congrats for the winners!

1 2552 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 2601

Let freq[i] = the number of times i occurs in A.
Let m = max(A).

1. B contains one distinct number (x):
f(B) = x + freq[x].
So, answer >= m + freq[m] >= m + 1.
2. B contains 2 or more distinct numbers:
gcd(B) <= m / 2.
=> f(B) <= m / 2 + n
To change the answer, f(B) >= m + 1.
=> m / 2 + n >= m + 1
=> n-1 >= m / 2
=> m <= 2n-2
=> m < 2n

If m >= 2n:
answer = max(x + freq[x]) for all x in A.
Otherwise:
Use O(n * sqrt(A[i])) = O(n * sqrt(n)) fallback algorithm.

Comments (21)

Write comment?

alkaoser_Ck

4 days ago, # |

A codechef contest

→ Reply

Utsav_Kashyap

-54

I’m excited to participate in CodeChef Starters 174 and Good luck to everyone!!

antiMathforces

4 days ago, # ^ |

+35

stfu cheater

Dominater069

3 days ago, # |

+21

good luck and i hope you enjoy the problems.

Krrishchanchal

3 days ago, # ^ |

Is there any specific reason as to why contests are being held in icpc mode. I mean I am not against it but I really enjoyed the freedom to submit wrong solutions in a row.

pagol

2 days ago, # ^ |

Maybe "AI" People!

physics0523

+70

Why back-to-back <2700 rated? There are only around 20 active 2700+ and only excluding them is almost meaningless.

45 hours ago, # ^ |

hi, you make a valid point. I thought div1C (and maybe D) were somewhat standard for lgms, while EF would be hard enough (Nachia nearly proved me wrong, i have no clue how someone solves E in 16mins, have you seen it before?)

For the future, I will try rating for all if I have such a scenario. As you can see the rated range was updated late because I realized it was too hard (and also too nice) for 6*

+10

There is an additional reason we shouldn't cut at 2700. Due to the rating system of CC, newcomers have pretty high volatilities (though 2700+ with many contests has so low volatilities that in one contest their abs(delta)<=30). If strong newcomers(, or new accounts) with slightly lower than 2700, they will experience huge delta (kinda +50~+100), and 2700+[0,100] have nothing to do. TBH this phenomenon is common for lower divisions, but I think it shouldn't be happened at active rank 20.

hashman

2 days ago, # |

+14

As a tester, I forgot to test.

shruti1528

Contest starts in ~30min.

VladiG

As a tester, get better.

itsraajjjuuuu

46 hours ago, # |

I just opened problems in CC but I didnt submit any so it wont be rated for me right?

DebNayak05

Nope, it won't be rated.

45 hours ago, # |

Can anyone point out how to check good pair ? I know doing cur=0 after finding mexi is wrong

Meximal Sum


void solve() {
    int n;
    cin >> n;
    vi a(n);
    for (int i = 0; i < n; i++) cin >> a[i];

    set<int> s;
    int mexi = 0;
    for (int i = n - 1; i >= 0; i--) s.insert(a[i]);
    while (s.count(mexi)) mexi++;

    vll prefix(n);
    prefix[0] = a[0];
    for (int i = 1; i < n; i++) prefix[i] = prefix[i - 1] + a[i];

    vi indices;
    int cur = 0;
    for (int i = 0; i < n; i++) {
        if (a[i] == cur) cur++;
        if (cur == mexi && i<n-1) {
            indices.pb(i);
            cur=0;

        }
    }

    if (indices.size() < 2) {
        cout << "-1 -1\n";
        return;
    }
    ll maxi =-1e9;
    // print_vector(indices);
    ll sum = accumulate(all(a),0ll);
    for(int i =0;i<indices.size()-1;i++){
        ll o =prefix[indices[i]];
        ll K = prefix[indices[i+1]] - o;
        
        maxi=max(maxi,sum-2*K);
    }
    ll mini = (prefix[n - 1] - prefix[indices.back()])-prefix[indices.back()] + 2 * prefix[indices[0]];
    cout << mini << " " << maxi << endl;
}


int32_t main() {
    fastio;
    int I_love_eating_Sand = 1;
    cin >> I_love_eating_Sand;
    while (I_love_eating_Sand--) solve();
    return 0;
}

case3

40 hours ago, # |

Extremely easy guess solution for problem GCD Add Size.

I knew that multiplication of primes rises faster than the array size which is just an add operation and multiplication always is faster.
From this I realized that I just have to look at divisors of a number upto a certain value and max till $$$sqrt(n)$$$. I experimented with this value and go 50 to be working

This is my solution.

Main Code

Solve

void solve() {
    int n;
    cin >> n;
    vector<int> arr(n);
    for(auto& val : arr)
        cin >> val;
    unordered_map<int,int> mp;
    for(auto& val : arr) {
        for(int j=1;j*j<=val && j<=50;j++) {
            if(val%j == 0) {
                int num1 = j;
                mp[num1]++;
                int num2 = val/j;
                if(num2 == num1)
                    continue;
                mp[num2]++;
            }
        }
    }
    int ans = 0;
    for(auto& val : mp) 
        ans = max(ans, val.first + val.second);
    
    cout << ans << "\n";
}

I still don't have a proof for this but I had this intuition for multiplication rising much much faster than addition and I just guessed it to be 1e5 then 1e3 and then 50 and it worked. Anyone having some definite proof or a counter case Dominater069?

Neev4321

33 hours ago, # ^ |

← Rev. 2 →

+11

Counter Case

Your Output:2602.
Expected Output: 2603.

Edit: This shows that you must check all factors till $$$sqrt(A[i])$$$, which is the same as checking all factors.
Also, where does the multiplication of primes intuition come from?
$$$gcd$$$ does not necessarily grow with primes.

31 hour(s) ago, # ^ |

Thank you for this. The main idea which I thought of was say there are numbers like $$$p1*p2$$$ and both greater than some number which I took 50 then it is always beneficial to take the largest number +1 rather than finding a common multiple among them and then adding length to it. I mean a single number with multiplication of a number greater than some threshold is always more than finding a common value(GCD) + length.

28 hours ago, # ^ |

Your idea works, but the chosen cutoff must be 2n (Submission).

I tried to use latex but it gave this message and does not let me post: "The comment contains source code without markup.".

27 hours ago, # ^ |

This is good. Thank you.

Akshat_Gupta._

21 hour(s) ago, # |

← Rev. 4 →

I don't know why my code give wrong answer for the 6th test case for MEXSUM ~~~~~ My submission

wuhudsm's blog