Why?

8 месяцев назад, # |

please explain F

→ Ответить

paIao

8 месяцев назад, # ^ |

← Rev. 2 →

You can use two pointers method.

My submission

→ Ответить

jonnnnnsinaga

8 месяцев назад, # ^ |

Find all possible subarray
For each subarray, find the maximum length possible using prefix sum and binary search
Calculate for the maximal value for all possible subarray

→ Ответить

MishkatIT

8 месяцев назад, # ^ |

You can solve this by using sliding window or two pointers approach.

→ Ответить

D347H

8 месяцев назад, # |

Duuuudeeee if I had like 1 minute, I would've solved the last problem yikes

→ Ответить

Goutham_808

8 месяцев назад, # |

A and B were pretty easy. C is just slightly above average and the code is repetitive. and I didn't able to 4th one. I got some math but it is throwing me an error in the first case itself but it solved almost 7 cases in it. Can anyone help me how to do it.

→ Ответить

Muhimen

8 месяцев назад, # ^ |

Create a array that will contain only the index of every B.

Now, iterate over the array using two pointers. If difference between two points exceed k(consecutive cells) simply add one to the answer and move your starting pointer.

→ Ответить

cumback03

8 месяцев назад, # |

Please explain F

→ Ответить

Muhimen

8 месяцев назад, # ^ |

Basically you will have to determine the maximum length of subarray of array a such that sum of every element in that subarray does not exceed k.

However the the catch is, the subarray you are creating from a, those indices must also form a valid subarray of h. And subarrays of h is constructed following the condition: hi is divisible by h(i+1).

So, for the following test case,

subarrays of h are: 4 4 2 and 4 1. Notice that every element is divisible by the next element.

One optimal subarray of a will be 3 2 4 since sum 9 is less than 12. And the length will be the answer.

2 4 1 is also a subarray that has a sum lower than 12. But it does not overlap in any subarray of h. Therefore this subarray is not optimal.

→ Ответить

cumback03

8 месяцев назад, # ^ |

← Rev. 2 →

Thank you .i also tried to implement the sliding window solution but i overcomplicated the idea or messed with the approach. This was my code and it always for 2nd testcase.

void solution()
{
   ll n,k;
   cin>>n>>k;
   ll arr[n+1];
   ll h[n+1];
   for(ll i=1;i<=n;i++) cin>>arr[i];
   for(ll i=1;i<=n;i++) cin>>h[i];
   if(n == 1)
   {
     if(arr[1]<=k) cout<<1<<endl;
     else cout<<0<<endl;
   }
   else
   {
     ll j = 1;
     ll result = 0;
     ll sum = 0;
     ll i = 1;
     while(j<=(n) and i<=n)
     {
        if(j == n)
        {
            if(i!=j and sum + arr[j] <=k)
            {
                result = max(result,(j-i)+1);
            }
        }
        else
        {
            if(h[j]%h[j+1] == 0)
            {
                sum += arr[j];
                if(sum <= k)
                {
                    result = max(result,(j-i)+1);
                }
                else
                {
                    while(sum > k and i<=j)
                    {
                        sum -= arr[i];
                        i+=1;

                    }
                    if(i<=j)
                    {
                        result = max(result,(j-i)+1);
                    }

                }
                
            }
            else
            {
                if(i!=j and sum + arr[j] <= k) result = max(result,(j-i)+1);
                i = j+1;
                sum = 0;
            }
        }
        j+=1;
     }
     cout<<result<<endl;
   }
   
}

→ Ответить

ysislm

8 месяцев назад, # |

great contest!

→ Ответить

kinshu2003

8 месяцев назад, # |


include<iostream> 
#include<bits/stdc++.h> 
using namespace std; 
int possible(vector<int> v,int mid){
    int n = v.size(); 
    int  wdth = 0; 
    for(int i=0;i<n;i++){
        if(v[i]<mid){
            wdth = wdth + (mid-v[i]); 
        }
        else{
            continue; 
        }
    }
    return wdth; 
}
int main(){
    int t; 
    cin>>t; 
    while(t--){
        int n; 
        cin>>n; 
        int w; 
        cin>>w; 
        vector<int> v; 
        for(int i=0;i<n;i++){
            int x; 
            cin>>x; 
            v.push_back(x); 
        }
        int low = 1; 
        int high = w + accumulate(v.begin(),v.end(),0); 
       int  ans = -1; 
        // binary search on heights 
        while(low<=high){
           int mid = low + (high-low)/2; 
            if(possible(v,mid)<=w){
                low = mid + 1;
                int cnt = mid; 
                ans = max(cnt,ans);
            }
            else{
                high = mid - 1; 
            }
        }
        cout<<ans<<endl; 
    }
}

i applied checked width for every height from lower to upper bound and applied binary search on heights it passed 3 test cases whats the problem ?

→ Ответить

linearspace

8 месяцев назад, # ^ |

use long long ($$$1 \leq a_i \leq 10^9$$$) 224508834

→ Ответить

kinshu2003

8 месяцев назад, # ^ |

Thanks

→ Ответить

ninjavin2001

8 месяцев назад, # |

Why showing penalty currently in the standings? I didn't do wrong submissions?

→ Ответить

I_need_7.0_IELTS

8 месяцев назад, # ^ |

penalty is total of time you need to get AC all problems. If you haven't AC a problem (except WA on test 1), then 10 minutes is added to your penalty when you AC that problem.

→ Ответить

tautology

8 месяцев назад, # |

pwild can you please explain this beautiful solution of yours for G?

→ Ответить

zackscott286

8 месяцев назад, # ^ |

Imagine the character 'B' will divide $$$s$$$ into some parts of consecutive 'A'. Then the answer is just the total 'A' in $$$s$$$ minus the minimum number of 'A' among all these parts.

→ Ответить

pwild

8 месяцев назад, # ^ |

zackscott286 already explained what the code does. To get there, note that we can get rid of any sequence of 'A' as long as there is a 'B' next to it, but that a single 'B' can only be used to eliminate either the sequence to its left or the one to its right. As the number of 'A' sequences is one more than the number of 'B', one of the 'A' sequences needs to stay, and we can always ensure that we only keep the shortest. The maybe somewhat surprising part of this is that this still works if this shortest sequence is empty, i.e. if the string starts or ends with 'B' or contains a substring 'BB'.

→ Ответить

tautology

8 месяцев назад, # ^ |

Thanks, clear now.

→ Ответить

om1429888

8 месяцев назад, # |

+10

MY INTUTION FOR THE LAST ONE IS. ONLY ONCE CYCLE EXISTS IN THE GRAPH IF IT DOES. FIND WHERE THE PERSON RUNNING CAN ENTER IT. THEN SEE WHO CAN REACH IT FIRST. IF THE PERSON RUNNING CAN REACH IT FIRST ITS A YES OR ELSE A NO. AM I RIGHT? I COULD NOT DO IT COZ I WENT TO EAT A CAKE.

→ Ответить

woonder

8 месяцев назад, # ^ |

You are right!

→ Ответить

29logN

8 месяцев назад, # ^ |

Yes, I solved H using this idea

→ Ответить

Pirate_King

8 месяцев назад, # ^ |

+14

WHY ARE YOU SCREAMING ????

→ Ответить

EMBailey

8 месяцев назад, # ^ |

They're excited about the cake! (I would be too.)

→ Ответить

DonSilvio

8 месяцев назад, # |

When you've spent a whole hour coming up with a solution for H when there are 1 to n*(n-1) edges, and only after the solution was found do you notice that there are only 1 to n edges =|

→ Ответить

SaraIschan

8 месяцев назад, # |

Thank you for this great contest! I'm so happy that I solved 3 problems in 30 minutes

→ Ответить

treasuryonly

8 месяцев назад, # |

Problem E is nice, came up with binary search fast but spent lots of time fixing the high bound, lesson learned for me.

Problem G is so nice, with short and clear statement, like it the best in this contest!

Thank you guys for the contest!

→ Ответить

8 месяцев назад, # ^ |

how did you fix the high bound?, I tried a lot of things still couldn't do it

→ Ответить

treasuryonly

8 месяцев назад, # ^ |

The key here is just to make sure it won't be overflow between long long and int.

In your submission with end=2e14 then mid will be 1e14, in function isPossible variable w may become 2e19 (overflow for long long) because n can be max 2e5.

→ Ответить

8 месяцев назад, # ^ |

thanks a lot!

→ Ответить

arutsudar

8 месяцев назад, # ^ |

← Rev. 2 →

When calculating the sum, if we exit the loop just after it exceeds x, then, we don't have to worry about the high bound.

(In your case it is in method check, for the variable cnt. If we add if (cnt > x) return false;, it would have probably worked, even with the maximum long value as the high bound.)

→ Ответить

treasuryonly

8 месяцев назад, # ^ |

Nice tip, thank you!

→ Ответить

MMonirHossain

8 месяцев назад, # |

For problem F: Given, (l≤i<r). Here, How l and r can be same? That means (l==r)?

Please explain some one...

→ Ответить

Matveyko

8 месяцев назад, # ^ |

Yeah, it is confusing. But you can choose subsegment of length 1 if a[i] <= k

→ Ответить

8 месяцев назад, # ^ |

Yeahh I also had a chat with them on this. They didn't mentioned anything about subarray of size 1.

→ Ответить

nekoyukino

8 месяцев назад, # ^ |

There's no such $$$i$$$, so, no such constraint too. If $$$r=l+1$$$, we have to ensure $$$h_l$$$ is divisible by $$$h_r$$$. If $$$r=l$$$, there's nothing we have to ensure. You can also find such case in the 3rd example

→ Ответить

MMonirHossain

8 месяцев назад, # ^ |

I just ignored the note,, actually by reading the statement i was oversure that l must less than r.

→ Ответить

flamestorm

8 месяцев назад, # ^ |

Please red the blog https://mirror.codeforces.com/blog/entry/120638.

→ Ответить

MMonirHossain

8 месяцев назад, # ^ |

I read it,,but not satisfied

→ Ответить

B_Consistent

8 месяцев назад, # |

I think C and D should be swapped. C was harder question.I did not observe C, somehow I escaped with some implementation but costed me so much time.

→ Ответить

AkrmFahem

8 месяцев назад, # |

One of the best and most Balanced Div 4 i saw there was so happy to take part in it

→ Ответить

8 месяцев назад, # |

← Rev. 2 →

Can someone help me find issue in F? I am not finding any case where it is failing. TIA https://mirror.codeforces.com/contest/1873/submission/224511926

→ Ответить

KeJingfan

8 месяцев назад, # |

Does problem F, test 2, test case 1: n = 2, k = 15, a = {9, 6}, h = {1, 3} exists a contiguous subarray satisfies the condition that each i (l <= i < r), h_i is divisible by h_(i+1)? The expected answer is 1, but there is no h_i is divisible by h_(i+1), so I think there is no contiguous subarray satisfies the condition. Please explain.

→ Ответить

8 месяцев назад, # ^ |

Yess Exactly, I asked them in the chat while contest about subarray of size 1 and they gave me below reply -

Spoiler

→ Ответить

flamestorm

8 месяцев назад, # ^ |

+13

Please read the blog https://mirror.codeforces.com/blog/entry/120638.

→ Ответить

8 месяцев назад, # |

For Problem E how are we supposed to fix the upper bound while using binary search

I never thought upper bounds could be an issue. I assumed taking high bound as LLONG_MAX-1 should suffice always

→ Ответить

8 месяцев назад, # ^ |

I did same and got 5 WAs. This will result in integer overflow.

→ Ответить

arutsudar

8 месяцев назад, # ^ |

← Rev. 2 →

If we break the loop just after it exceeds x, then, it works even if we set the higher bound to the maximum long value.

@f20190909 Your submission 224516751 with additional check if (w > x) return false; worked here 224521160.

@LaughingBuddha Your submission 224509345 with additional check if (W < 0LL) return false; worked here 224521345.

→ Ответить

8 месяцев назад, # ^ |

Thanks bro, This should have popped up in my mind.

→ Ответить

8 месяцев назад, # ^ |

thanks a lot!

→ Ответить

8 месяцев назад, # |

I wonder why I have rank 6900 with 5 problems while there are people with 4 problems and rank 6000 or even higher. Should It be the one with more problems has higher rank and only if there is a tie the time penalty plays a role?

→ Ответить

8 месяцев назад, # ^ |

Please explain, this Is weird

→ Ответить

zackscott286

8 месяцев назад, # |

I was surprised by my friend's submission in problem E. He used greedy that I couldn't think it was possible LOL. His submission: 224456152

→ Ответить

Astroflexx

8 месяцев назад, # |

W Kendrick Lamar Problem Setters

→ Ответить

ARMINIUS

8 месяцев назад, # |

Nice contest! I really enjoy it

→ Ответить

JohanXLiebert

8 месяцев назад, # |

Were some of the problems in the contest inspired by Kendrick lamar?

→ Ответить

Osama_Fahim

8 месяцев назад, # |

Can someone please explain what is wrong with my approach for problem F void solve() { ll n, k; cin >> n >> k;

ll a[n]{};
inp(a, n);
ll h[n]{};
inp(h, n);

ll pref_sum[n + 1]{};
for (ll i = 0; i < n; ++i) {
    pref_sum[i + 1] += pref_sum[i] + a[i];
}

ll ans = 0;
for (ll i = 0; i < n; ++i) { 
    ll start = i;
    while (i < n - 1 && (h[i] % h[i + 1] == 0)) {
        if (pref_sum[i + 1] - pref_sum[start] <= k) {
           ans = max(ans, i - start + 1);
        }   
        else
            break;

        ++i;
    }
}

cout << ans << nl;

}

→ Ответить

8 месяцев назад, # |

Please try to hack this Problem F

→ Ответить

ElainaOwO

8 месяцев назад, # ^ |

done

→ Ответить