you are so quickly!

so fast!

I will kill myself over B. UPD: Found my error

I spent lot's of time considering 1:0 situations in problem B.

fast editorial

Clarification: SlavicG and I actually are best friends, he's just playing hard to get.

In problem E, my code was giving me expected/correct output in my local machine, but is giving wrong output during codeforce's testing 274941437

Could any one tell why is that?

G1<<E or F

I had the same intuition for F but I got stuck and I had no idea why my code was failing for the last provided test case. Values seem fine, but it keeps dumping to stack trace, isn't it just a O(n) loop with my factorials memoized?

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ull = unsigned long long;

#define debug 1

const ll limit = 2e5;
const ll mod = 1e9+7;

template<typename... Args>
void mycout(const Args&... args) 
{
    #if debug
    ((cout << args << ", "), ...); // Fold expression
    cout << endl;
    #endif
}

unordered_map<ull, ull> factorials;

const ull factorial(const ull n) 
{
    if (n <= 1) 
        return 1;

    if(factorials.contains(n))
        return factorials[n];

    factorials[n] = n * factorial(n-1);

    return factorials[n];
}

const ull pickKFromN(const ull n, const ull k)
{
    if(n <= 0)
        return 0;

    const ull top = factorial(n);
    const ull btm = factorial(k) * factorial(n-k);
    
    return top/btm;
}

int main()
{
    ios::sync_with_stdio(false); 
    cin.tie(0); 
    cout.tie(0);
    
    ll t;
    cin >> t;

    while(t--)
    {
        // k is odd
        ll n,k;
        cin >> n >>k;

        vector<ll> v(n);
        ll sum{};

        
        for(ll i{}; i < n; ++i)
        {
            cin >> v[i];

            sum = (sum + v[i]) % mod;
        }

        if(k == 1)
        {
            cout << sum << endl;
            continue;
        }

        sort(v.begin(),v.end());
        
        // eg 3 will be 2th element so index 1
        ll medianIndex = (k == 1 ? 0 : (k+1)/2 - 1);
        
        if(k == n)
        {
            cout << v[medianIndex] << endl;
            continue;
        }

        ll result{};

        // given median index
        // i can pick index elements on the left
        // then pick k - 2

        /*
            6 3
            1 0 1 0 1 1
            
            medianindex == 1
            0 0 1 1 1
              ^

            1*2*2 == 4
            1*3*1 == 3
            

            0 0 1 1

            i1 : 
        */
        
        for(ll i{medianIndex}; i < n; ++i)
        {
            if(v[i] == 0)
                continue;

            const ull leftElements = i;
            const ull rightElements = n-i-1;

            const ull pickLeft = medianIndex;
            const ull pickRight = k-(medianIndex+1);

            const ull left = pickKFromN(leftElements,pickLeft) % mod;
            const ull right = pickKFromN(rightElements,pickRight) % mod;
            const ull combined = (((v[i] * left) % mod) * right) % mod;
            
            mycout(i,result,combined);
            mycout(leftElements,pickLeft,left);
            mycout(rightElements,pickRight,right);
    
            result = (result + combined) % mod;
        }

        cout << result << endl;
    }

    return 0;
}

from math import *
for _ in range(int(input())):
  l,r=map(int,input().split())
  ans=0
  if l<3:
    ans=1
  else:
    if power(l):
      ans+=ceil(log(l,3))+1
    else:
      ans+=ceil(log(l,3))
  before=ans
  print(ans,"BEFORE")
  for i in range(l+2,r+1):
    if power(i):
      ans+=ceil(log(i,3))+1
    else:
      ans+=ceil(log(i,3))
  print(ans,"AFTER")
  if r>l:
    ans+=ceil(log((3*before)*(l+1),3))+(1 if power((3*before)*(l+1)) else 0)
  print(ans,"ANSWER")

Got the Logic Couldn't make it up.

In editorial of G2 , if a < x <= b, area should be a * (b + 1) but given (a+1) * b. May be it's a Typo SlavicG

I think G1 and G2 were much easier than E and F... the most basic binary search in both versions

Why my code 274894324 is getting WA on E? I did all exactly as in editorial

Just got an observation for E:
[1, 3) -> all elements require 1 operations to become 0
[3, 9) -> all elements require 2 operations to become 0
[9, 27) -> all elements require 3 operations to become 0
[27, 81) -> all elements require 4 operations to become 0
[81, 81 * 3) -> all elements require 5 operations to become 0
and so on.

I think this could be optimal.

I love E, F, G2. Brilliant idea!!!

Can anyone tell me how to test our code for an interactive problem?

For problem E why is this O(n) code getting TLE?(https://codeforces.me/contest/1999/submission/274854161)

I'm so used to "Sum of n over all cases doesn't exceed $$$ 2 \times 10^5 $$$ " :)

In which test case my submission 274924034 for E is failing.

I dont understand why this gives wrong ans; E

Your code here...
int fun(ll x){
  int count = 0;
  while(x){
    count++;
    x = x/3;
  }
  return count;
}

void solve() {
  ll l, r;
  cin >> l >> r;
  ll ans = 0;
  ans += fun(l);
  ans+= fun(3*ans*(l+1));
  for(int i = l+2; i <= r; i++){
    ans+=fun(i);
  }
  cout << ans << endl;
}

Why is my D solution so slow? 274970418 I am using the same two pointer strategy that the editorial mentions and get TLE every time. I have a single loop iterating through the string and that is it. Am I using any expensive operations without realizing it? Thanks in advance.

Can anyone tell that why in E O(n log n) doesn't work ? To be precise the overall complexity would be 2.5*10^6, which should pass in 1 sec. ? isn't it?

I got another simpler setup approach to E, perhaps.

We will make an array of the exponentiation of 3, like lt[0] = 1, lt[1] = 3, lt[2] = 9, lt[3] = 27, ..., lt[15] = 3^15. (Because r <= 2 . 10 ^ 5)

We will make a prefix sum before making the testcase. For each i, call j is the smallest number satisfying a[i] >= lt[j], (1 <= j <= 15).

For example, a[1] = 1, a[2] = 1, a[3] = 2, a[4] = 2, ..., a[8] = 2, a[9] = 3, a[10] = 3, ... After that we will make a prefix sum of a[] called f[]. For instance, f[1] = 1, f[2] = f[1] + a[2] = 2, f[3] = f[2] + a[3] = 4, ...

For each n, m in the testcase, to find the minimum operation needed, while n, m is typed from the keyboard, the answer will be pre[m] — pre[n-1].

Then plus the a[n], as we have to make n become 0 to minimize the operations, the final thing to do is f[m] — f[n-1] + a[n].

Link: My sub

Can anyone help me find out the bug in my code for problem D? It passed all testcases, but it got hacked, and I don't know how to find the specific testcase in which it failed at.

https://codeforces.me/contest/1999/submission/274881476

Thanks in advance! If this is against the rules of the contest, please let me know so I can delete this comment.

You know for the Showering question how did you not get a memory exceeded error??

#include <bits/stdc++.h>

using namespace std;


int main(){
  cin.tie(nullptr)->sync_with_stdio(false);
  int t,n,s,m;
  cin >> t; 
  int start, end;
  vector<int> time; 
  while (t--){
    time.clear();
    cin >> n >> s >> m;// 0 is free and 1 is busy
    while (n--){
      cin >> start >> end;
      while(start < end){
        time.push_back(start);
        start += 1;
      }
    }
    sort(time.begin(), time.end());
    int free_time = time[0];
    for (int x = 0; x<time.size() - 1; x++){
      if (time[x+1] - time[x] > 1 && time[x+1] - time[x] > free_time){
        free_time = time[x+1] - time[x] - 1;
      }
    }
    if (m - time[time.size()-1] - 1 > free_time){
      free_time = m - time[time.size() - 1] - 1;
    }
    if (s <= free_time){
      cout << "YES" << "\n";
    }
    else{
      cout << "NO" << "\n";
    }
  }
  return 0; 
}

I am also using a linked list to store the timings which aren't available. But test case 3 threw a memory exceeded error.

E is good, but isn't the data range a bit small? Many $$$O(Tn)$$$ algorithms can pass this problem, and it's hard to hack them.

For Problem E, I am running a loop here of size (b-a+1) each time. I tried hacking my solution on max size testcase $$$10000 \newline 1\;200000\newline....\newline....\newline1\;200000\newline$$$ . I don't know this solution got accepted? Can anybody tell the reason for the same or else try to hack it?

Submission link

Harder Version of F if anyone wants to try. Sum of Medians

Can any one give me more explain for problem F , i did not Understand tut :(

For F, with x numbers 1, this formula $$$\binom{x}{k/2+1} * \binom{n-(k/2+1)}{k/2}$$$ is correct?

The logic is that we take $$$k/2+1$$$ from $$$x$$$ numbers of 1, and whatever others elements are(taking $$$k/2$$$ from the left $$$n - (k/2+1))$$$ the median will be 1

Can someone solve E when l and r are large i.e upto 1e18 it could possibly turn out to be a good math problem.Please do write if you have any idea on how to do it?

I really appreciate problem E. I have seen the pattern: "To use the fewest number of operations possible, we should do the first step on the minimum number, since it has the fewest digits." after writing down a few cases, but I failed to come up with prefix sum part.

Thank you. Now I learn.

Can anyone let me know why this gives TLE.Even the solution code precomputes till 2e5.275010837

In problem E, function $$$f$$$ takes $$$O(\log_3 x)$$$ to compute on a number $$$x$$$, so your complexity is $$$O(n \log n)$$$, not $$$O(n)$$$. However, there is a simple way to compute $$$f(1), f(2), \ldots, f(n)$$$ in $$$O(n)$$$ overall, without utilizing any expensive math functions: notice that $$$f(x) = f(\lfloor x / 3 \rfloor) + 1$$$. The code is even shorter than before: 275014438.

G2 is just introduction to ternary search.

can anyone tell why my e code of o(n) is giving tle ? :- https://codeforces.me/contest/1999/submission/274942317

I regret not studying interactive problems!

#include <bits/stdc++.h>
using namespace std;
#define int long long


void solve(){
    int a,b,c,d;
    cin>>a>>b>>c>>d;
    int cnta=0,cntb=0;
    if(a>c&&a>d&&b>c&&b>d){
        cout<<4<<endl;    }
    else if((a>c&&b>d)||(a>d&&b>c)){
        cout<<2<<endl;
    }
    else if((a>c&&b==d)||(a>d&&b==c)||(b>c&&a==d)||(b>d&&a==c)){
        cout<<1<<endl;
    }
    else
    cout<<0<<endl;
}
int32_t main() {
	int t;
	cin>>t;
	while(t--){
	    solve();
	}

}

Can someone help which testcase I am missing

When will we get the rating updates? Im kinda excited

Can somebody point out what is wrong?: 274922968

If problem F was to count odd length subsequences having median as 1. What can be the solution?

Alternate solution to problem E, works in O(log3(r))

Basically make the smallest element (l) zero and then use that to make other elements zero as well. While we were making l zero (divide by 3k), we also multiplied some element by 3k and hence first we remove that. Then we just iterate over different powers of 3 (since they decide how many times we divide a number to make it zero) and find number of elements to divide by that number (the power tells us number of times this division is required)

`void tripleOperations(int l, int r)`
`{`
`    vector<int> power3;`
`    power3.push_back(1);`
`` 
`    while (power3.back() <= r) power3.push_back(3 * power3.back());`
`    int const n = power3.size();`
`` 
`    int ix = upper_bound(power3.begin(), power3.end(), l) - power3.begin();`    
`    long long ans = 2*ix;`
`    l++;`
`` 
`    while (ix <= n-1)`
`    {`
`        ans += (min(r, power3[ix] - 1) - l + 1) * (ix);`
`        l = power3[ix];`
`        ix++;` 
`    }`
`` 
`    cout<<ans<<'\n';`
`}`

In E,my submission fails at test case 1, where as it works well in my local machine as well as in online cpp shell. Can anyone let me know why it happened, Thanks.

Can anyone help me in G2? I am getting wrong answer Integer 0 violates the range [1, 1000] (test case 1) in Test 1. I even manually wrote exceptions, that if my variable is 0, output 1 instead. Still, I do not know why I am getting output 0 https://codeforces.me/problemset/submission/1999/275154103

275163443

Why my this solution for E giving me TLE? Isn't this only O(N)?

Thanks :)

why did i use RMQ on E? :skull:

In this contest, the question was just about if else and due to which it matched with some one. How can you declare that I was cheating in that contest. Please look into this matter. Thanks mine : aritg/274372105 23CS02002/274399627

getting the detail right on problem b was so easy yet frustrating

Alternative solution for A, write an if statement for each of the 90 possible inputs. This is very efficient because you don't use a for loop or any other costly operation such as division or modulo. My code: https://codeforces.me/contest/1999/submission/277148166

I screwed up so much on F during a virtual contest, only to realize I forgot an extra mod operation...

Worst question B