Thanks for participating!
Idea: mesanu
Tutorial
Tutorial is loading...
Solution
t = int(input())
for test in range(t):
a,b,c,d = map(int, input().split())
rs = (b > a) + (c > a) + (d > a)
print(rs)
Idea: mesanu
Tutorial
Tutorial is loading...
Solution
#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
void solve()
{
int n, x;
cin >> n;
set<int> a;
for(int i = 0; i < n; i++)
{
cin >> x;
a.insert(x);
}
if((n-a.size())%2 == 0)
{
cout << a.size() << endl;
}
else
{
cout << a.size()-1 << endl;
}
}
int32_t main(){
int t = 1;
cin >> t;
while (t--) {
solve();
}
}
Idea: flamestorm
Tutorial
Tutorial is loading...
Solution
#include <bits/stdc++.h>
using namespace std;
void solve() {
char g[9][9];
for (int i = 1; i <= 8; i++) {
for (int j = 1; j <= 8; j++) {
cin >> g[i][j];
}
}
for (int i = 2; i <= 7; i++) {
for (int j = 2; j <= 7; j++) {
if (g[i][j] == '#' && g[i - 1][j - 1] == '#' && g[i - 1][j + 1] == '#' && g[i + 1][j - 1] == '#' && g[i + 1][j + 1] == '#') {
cout << i << ' ' << j << '\n'; return;
}
}
}
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int tt; cin >> tt; for (int i = 1; i <= tt; i++) {solve();}
// solve();
}
Idea: SlavicG
Tutorial
Tutorial is loading...
Solution
#include <bits/stdc++.h>
using namespace std;
int a[5] = {600, 60, 0, 10, 1};
int good[16] = {0, 70, 140, 210, 280, 350, 601, 671, 741, 811, 881, 951, 1202, 1272, 1342, 1412};
void solve() {
string s;
cin >> s;
int x;
cin >> x;
int tot = 0;
for (int i = 0; i < 5; i++) {
tot += (int)(s[i] - '0') * a[i];
}
set<int> t;
for (int i = 0; i < 2022; i++) {
t.insert(tot);
tot += x;
tot %= 1440;
}
int res = 0;
for (int i : t) {
for (int j = 0; j < 16; j++) {
if (good[j] == i) {res++;}
}
}
cout << res << '\n';
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int tt; cin >> tt; for (int i = 1; i <= tt; i++) {solve();}
// solve();
}
Idea: flamestorm
Tutorial
Tutorial is loading...
Solution
#include "bits/stdc++.h"
using namespace std;
#define ll long long
#define forn(i,n) for(int i=0;i<n;i++)
#define all(v) v.begin(), v.end()
#define rall(v) v.rbegin(),v.rend()
#define pb push_back
#define sz(a) (int)a.size()
ll query(int l, int r, vector<ll>& p) {
return p[r] - (l ? p[l - 1] : 0);
}
void solve() {
int n, s; cin >> n >> s;
vector<ll> a(n), p(n);
forn(i, n) {
cin >> a[i];
p[i] = a[i];
if(i) p[i] += p[i - 1];
}
int ans = INT_MAX;
for(int i = 0; i < n; ++i) {
int l = i, r = n - 1, pos = -1;
while(l <= r) {
int mid = l + r >> 1;
if(query(i, mid, p) <= s) {
pos = mid;
l = mid + 1;
} else r = mid - 1;
}
if(pos == -1 || query(i, pos, p) != s) continue;
ans = min(ans, n - (pos - i + 1));
}
cout << (ans == INT_MAX ? -1 : ans) << "\n";
}
int32_t main() {
ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
int t = 1;
cin >> t;
while(t--) {
solve();
}
}
Idea: flamestorm
Tutorial
Tutorial is loading...
Solution
#include <bits/stdc++.h>
using namespace std;
void solve() {
int n;
cin >> n;
int cnt[10] = {};
for (int i = 0; i < n; i++) {
int x;
cin >> x;
cnt[x % 10]++;
}
vector<int> v;
for (int i = 0; i < 10; i++) {
for (int j = 0; j < min(cnt[i], 3); j++) {
v.push_back(i);
}
}
int m = v.size();
for (int i = 0; i < m; i++) {
for (int j = i + 1; j < m; j++) {
for (int k = j + 1; k < m; k++) {
if ((v[i] + v[j] + v[k]) % 10 == 3) {cout << "YES\n"; return;}
}
}
}
cout << "NO\n";
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int tt; cin >> tt; for (int i = 1; i <= tt; i++) {solve();}
// solve();
}
Idea: flamestorm
Tutorial
Tutorial is loading...
Solution
#include <bits/stdc++.h>
using namespace std;
const int MAX = 200007;
const int MOD = 1000000007;
void solve() {
int n, k;
cin >> n >> k;
int a[n];
for (int i = 0; i < n; i++) {
cin >> a[i];
}
int ok[n];
for (int i = 0; i < n - 1; i++) {
ok[i] = (a[i] < 2 * a[i + 1]);
}
int tot = 0;
for (int i = 0; i < k; i++) {
tot += ok[i];
}
int res = 0;
if (tot == k) {res++;}
for (int i = k; i < n - 1; i++) {
tot += ok[i];
tot -= ok[i - k];
if (tot == k) {res++;}
}
cout << res << '\n';
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int tt; cin >> tt; for (int i = 1; i <= tt; i++) {solve();}
// solve();
}
Idea: mesanu
Tutorial
Tutorial is loading...
Solution
#include "bits/stdc++.h"
using namespace std;
#define ll long long
#define forn(i,n) for(int i=0;i<n;i++)
#define all(v) v.begin(), v.end()
#define rall(v) v.rbegin(),v.rend()
#define pb push_back
#define sz(a) (int)a.size()
struct DynamicMaxSubarraySum {
struct node {
ll pref, suf, val, sum;
};
int N;
ll neutral;
vector<node> t;
DynamicMaxSubarraySum(int _N, ll assign_value) {
neutral = assign_value;
N = _N;
t.resize(4 * N);
forn(i, 4 * N) t[i] = {0, 0, 0, 0};
build(1, 0, N - 1);
}
void build(int i, int l, int r) {
if(l == r) {
t[i].pref = t[i].suf = t[i].val = t[i].sum = neutral;
return;
}
int mid = (l + r) >> 1;
build(2 * i, l, mid);
build(2 * i + 1, mid + 1, r);
t[i] = merge(t[2 * i], t[2 * i + 1]);
}
node merge(node a, node b) {
node c;
c.pref = max(a.pref, a.sum + b.pref);
c.suf = max(b.suf, b.sum + a.suf);
c.val = max({a.val, b.val, a.suf + b.pref});
c.sum = a.sum + b.sum;
return c;
}
void modif(int i, int l, int r, int pos, ll val) {
if(l > pos || r < pos) return;
if(l == pos && r == pos) {
t[i].pref = t[i].suf = t[i].val = t[i].sum = val;
return;
}
int mid = (l + r) >> 1;
modif(2 * i, l, mid, pos, val);
modif(2 * i + 1, mid + 1, r, pos, val);
t[i] = merge(t[2 * i], t[2 * i + 1]);
}
node query(int i, int l, int r, int tl, int tr) {
if(l > tr || r < tl) return {0, 0, 0, 0};
if(l >= tl && r <= tr) return t[i];
int mid = (l + r) >> 1;
return merge(query(2 * i, l, mid, tl, tr), query(2 * i + 1, mid + 1, r, tl, tr));
}
void modif(int pos, int val) {
modif(1, 0, N - 1, pos, val);
}
node query(int l, int r) {
return query(1, 0, N - 1, l, r);
}
node query(int pos) {
return query(1, 0, N - 1, pos, pos);
}
};
void solve() {
int n; cin >> n;
vector<int> a(n);
forn(i, n) cin >> a[i];
map<int, vector<int>> vv;
forn(i, n) {
vv[a[i]].pb(i);
}
DynamicMaxSubarraySum st(n, -1);
ll mx = 0, ans = -1;
for(auto i: vv) {
vector<int> v = i.second;
for(auto x: v) st.modif(x, 1);
if(mx < st.query(0, n - 1).val) {
ans = i.first;
mx = st.query(0, n - 1).val;
}
for(auto x: v) st.modif(x, -1);
}
int ansl = -1, ansr = -1;
for(int i = 0; i < n; ++i) {
if(a[i] == ans) a[i] = 1;
else a[i] = -1;
}
ll sum = 0, lastl = 0;
mx = 0;
for(int i = 0; i < n; ++i) {
sum += a[i];
if(sum > mx) {
mx = sum;
ansr = i;
ansl = lastl;
}
if(sum <= 0) {
lastl = i + 1;
sum = 0;
}
}
cout << ans << " " << ansl + 1 << " " << ansr + 1 << "\n";
}
int32_t main() {
ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
int t = 1;
cin >> t;
while(t--) {
solve();
}
}
Thanks for the fast editorial
I loved the contest, especially problems F and G.
whats wrong with this https://codeforces.me/contest/1692/submission/160657931 P.S. found.
How to solve H without using trees?
For example using a Kadane's algorithm. My submission that using it is here.
But if we apply Kadane's algorithm for every possible value of a wouldn't the complexity will be O(n^2)?
for each a, store positions of a[i] = a then the complexity is O(nlogn) because use have to compress value of a[i] or store them in map
I used Kadane's algorithm, where I kept track of the indices of each number, and inserted a certain amount of negative 1's between each index.
As explained in the editorial, for a fixed $$$a$$$, you can replace $$$arr[i]=1$$$ if $$$arr[i]==a$$$ else $$$arr[i]=-1$$$.
Now, you can find max sum subarray in this newly obtained array without using Segment Tree.
Observe that the max sum subarray will always start and end at indices where $$$arr[i]==1$$$.
Using this observation you can just iterate over indices where $$$arr[i]==1$$$ and use Kadane's Algorithm to find max sum subarray.
Since, there are only $$$n$$$ distinct values of $$$a$$$ possible, overall time complexity will be $$$O(n)$$$.
For more clarification, you can see my submission
I don't understand how you found the constant a in this case
No, I am not saying $$$a$$$ is constant but $$$a$$$ will definitely appear in the given array. So we can just iterate over all the distinct elements of the array and then considering current element as $$$a$$$ calculate the answer. Maximum over all elements will be the final answer.
but wouldn't that be O(n^2) because for every distinct a[i] you need to check the maximum subarray?
For every distinct $$$a_i$$$ we will iterate over indices of its occurrence. Now sum of number of indices for all distinct $$$a_i$$$ will be $$$n$$$(obviously). So inner loop will run only n times for the whole array.
Time complexity: $$$O(n+n)=O(n)$$$
again, there can be n distinct a[i] numbers, and if you iterate each one that would be n*n?
Think about it. If there are n distinct numbers then number of occurrences of every number will be 1. So inner loop will run only 1 time for every element not n times.
Great explanation , thanks!
Correct me if I'm wrong, but creating the map $$$m$$$ will require $$$\mathcal O(n\log n)$$$ time.
Yeah, you are right. I always tend to ignore map's complexity, lol. You can also use unordered_map for better complexity but that isn't necessary.
A solution using set Code
A solution using map here 160632225
Then it's just kandene my dear friend.
I used divide and conquer, here is my code
I used DP
I think this is easy solution using map 160604275
**problem H **, also can be solved useing kadane's algorithm.
H can be solved in O(n) just iterating for indexes of each a that is in array. My solution is here
You're inserting into a map, so it's not $$$O(n)$$$
We can utilize the map in a way that it never holds more than two elements, and hence works in O(1), which makes the solution O(n).
see 160608733
I think for an input like [1,1,1,1,2,2,3,...] the map would have to hold 3 elements. So in the worst case the map holds log(n) elements.
You are right, so it is O(n log(log(n)))
Bro come Atleast do some research before claiming time complexity. It's not O(N) coz you are using map. But i guess the operations are quite low so we can it's O(N) but technically it's not.
I tried running this with unordered_map but its fails with timeout error. Why is this the case? Why would iterating over an unordered_map take so much longer than iterating with map?
Because unordered_map has an O(n) complexy for operations in a worst case.
Cool thanks. Where in the documentation can I find this just for future reference?
Read this
Problem H can use Kadane in a nice way.
Notice that the sum over frequencies of distinct elements is the size of our input array.
We know any subarray endings should be at two elements that have the same value, otherwise, we are pointlessly reducing our answer and we can fix our boundaries to be on the same boundaries.
say if we have XXXLXXXRXXX where [L, R] is the subarray we are considering then there is no point in having the left or right boundaries on Xs since we could improve the sum by restoring boundaries to L and R.
We can make an array of positions for each distinct element and use the observation that the Xs can be compressed together, therefore for each distinct element, such a compression yields a size of array twice the array of all positions for that element.
So our solution boils down to making a compressed array for each distinct element and then applying kadane to it, finally taking the one which gives the maximum answer.
Time complexity is still the order of n as we are effectively applying kadane on twice the input size.
Problem F : O(10^3) preprocessing + O(n) approach Submission
easier O(10³) + O(n): 160566183
https://codeforces.me/contest/1692/submission/160650500
Here , is my submission for problem G, i didn't get how I am getting wrong answer on testcase 15, can someone please explain fault in my submission?. Thank you.
probably a floating precision error cause you are using
v[i]=log2f(x)
is there anyway we can store log base 2 of any number upto say 20 order of precision?
Depends on what you mean by "20 order of precision". If you mean just 20 digits in the number then surely double-precision floating-point can hold that amount of digits. If you mean 20 digits in fractional part, then you can't have a guarantee since it depends on how big your number is
Btw, you can use
63 - __buitin__clzll(x)
instead oflog2f(x)
if you're using gcc/g++. Or you can use something like that (code below), but I'm not sure if it'll resolve your problemSolution of H without trees
Instead of doubling and halving, consider the score of a subarray to be the difference between the frequency of $$$a$$$ and the number of elements in the subarray not equal to $$$a$$$. This is done because we will double our score for $$$freq[a]$$$ times and halve it for the rest elements and hence we want this difference to be maximum. Notice that for the best subarray, $$$a = x_l = x_r$$$. The problem can now be solved with dp. Let $$$dp[i]$$$ be the best score for a subarray with $$$l = i$$$ and $$$a = x_i$$$. Then we can see that $$$dp[i] = 1 + max(0,dp[next[a[i]]] - (next[a[i]]-i-1))$$$, where $$$next[x]$$$ is used to store the next occurence of $$$x$$$ on iterating over the dp. The right end can be maintained similarly(if the dp is maximised then $$$right[i] = right[next[a[i]]]$$$.
Submission at the time of the contest — https://codeforces.me/contest/1692/submission/160583853
Can we use sliding window for E by searching total sum minus reqd target in the sliding window?
This is my code to use a sliding window Your text to link here...
O(N)
Yes you can.
That is how I did it: 267769281
Solution of H without using segment trees: https://codeforces.me/contest/1692/submission/160692781
Could anyone help me with problem E: Binary Deque? My solution is kind of greedy. I create an array with distances (in numbers of zero entries) between two conseсutive ones. For example, for the sequence: 0 0 1 0 0 0 1 1 0 1, my array is [2 3 0 1 0] (last zero means that we have tail of zeros with length 0). Next, I use two iterators for decreasing the sum of the array choosing at every step iether the head or the tail with zeros and errasing it from my array. I cannot find the mistake and 1st test is OK, but I get WA for the second. If this idea is correct then the solution is O(n). Here the link: 160692840
I have a solution of E:
You can define an array $$$k$$$, It is prefix sum of $$$a$$$, so $$$k_i$$$ is "How many ones in [1,i]". The range [l,r]'s sum is S when $$$k_r-k_{l-1}=S$$$, you can define an array $$$m$$$. $$$m_i$$$ is "The max index j that k[j]=i". Then enumerate $$$l$$$, and the max of $$$r$$$ is $$$m_{s+k[l-1]}$$$, the answer is the minimum of $$$n-(r-l+1)$$$. If every $$$r$$$ is $$$0$$$ ($$$s+k[l-1]>n$$$), Then output -1. My code: 160569001
I think this logic is incorrect as this only accounts for the head or the tail. If the sum we needed was 5 and your array was [5 0 0 0 0 4 4 4 4 4], it would incorrectly assume that it should take from the tail every time instead of realizing that the 5 is better in the long run.
Can anyone explain the Kadane algorithm approach for the H problem? I am unable to understand what one is exactly trying to do.
I've done something very similar to kadanes (with an early break when the sum reaches 0):
For each position (starting from left) iterate through the array adding +1 for matches and -1 for other values. If the sum gets to 0 break. Any start positions that have previously added a +1 are skipped (as you've already calculated the sum from that position starting from at least 1).
ohk thanks:)
Thank you for fast editorial and interesting tasks.
Pretty sure we can do a O(n) solution for E right? I did this. Doesn't use map stl. https://codeforces.me/contest/1692/submission/160607428
I did an O(n) with 2-pointers technique
https://codeforces.me/contest/1692/submission/160604366
can you explain the logic behind this? I also tried a 2-pointers technique but I don't think my solution works. Also, how is your solution O(n) if it has nested loops?
Ok I'll try.
We're moving right pointer while sum in segment [l, r] is less/equal to s. If our sum is larger than s, we're moving the left pointer to reduce it. When sum is equal to s, update the answer. Thus, we'll find all subsegments with sum equal to s.
Complexity is O(n) because we're moving the right pointer N times and left pointer no more than N times.
Actually, my code is almost a copypaste of edu`s one (first block), there's a detailed explanation as well.
anyone please tell me where am i wrong 160716728 problem D
I think line 74 should be "checkhour>=24" instead of "checkhour>24"
Also line 41~44 is not correct because the clock never shows 24:00.
I'm not too fond of the author's solution to problem H, though the problem was great. But no divisional 4 rounds should contain any Data Structure. Here's my solution —
The basic observation is that the problem simply asks us to find, for each element(x) of the given array, the maximum subarray sum on another array(b) where b[i] = 1 if a[i] == x, -1 otherwise.
We can apply Kadane's algorithm for each element lazily. In Kadane's algorithm, the important variables are current sum, current best, and where the best subarray is. So, as we iterate over the array, we evaluate elements one by one and remember these important variables for each element and their last positions, std::map works fine.
And finally, we can just iterate over the map to find the best answer and the desired segment with the same asymptotic, O(n.log(n)). See my implementation if need be.
What is the wrong on my solution Problem E ? im using two pointers to get the best distance from left and right.. 160727889
1
12 1
0 0 1 0 0 1 1 1 1 0 0 0
You answer is 8 , but the correct answer should be 7. It is easy to know that this greed will not work...
can you give a testcase at which my code fails 269659676
Take a look at Ticket 17457 from CF Stress for a counter example.
i had updated that part still it fails on same test case can you please help me with 269660652
160731775 : An Elegant solution for Problem H:no segment tree required
Where can I find a tutorial for the standard problem of finding the maximum sum of a subarray?
In D, why is the second for loop running for 2022 iterations?
Any number greater than 1440 because after that the numbers will repeat again.
An alternative solution to problem H without segment tree. Notice that if we choose $$$(a,l,r)$$$, the money we will get is $$$2^{x-(r-l+1-x)}\ =2^{2x-(r-l)+1}\ $$$ ($$$x$$$ is the number of times that $$$ a $$$ appears in round $$$l$$$ to round $$$r$$$). Thus our goal is maximizing $$$2x-(r-l)+1$$$. For a certain number $$$a'$$$, we can create an array $$$b$$$, where $$$b[i]=-i+$$$ $$$2\times$$$(the number of times that $$$ a' $$$ appears in round $$$1$$$ to round $$$i$$$). And the money we will get by choosing $$$(a',l,r)$$$ is equal to $$$2^{2x-(r-l)+1}=2^{b[r]-b[l]+1}\ $$$! On the other hand, it's obviously that if the answer is $$$(a,l,r)$$$, then the dice must show $$$a$$$ in both round $$$l$$$ and round $$$r$$$. Therefore, we only need to consider the rounds where dice show $$$a'$$$ for a certain number $$$a'$$$. Based on the above, the problem can now be solved with time complexity $$$ \mathcal{O}(nlogn)$$$ by using maps and arrays. Checks this code for better comprehension:https://codeforces.me/contest/1692/submission/160769341
when div5 begins to be held? I want a more easier division!
kidding ?
not kidding, i want a more happy contest, during which I can ak very fast
mesanu For Problem H, can you explain how you are updating and calculating the maximum sum subarray having elements -1, 1, and like how you are updating it in log(N). Like in your code what does pref, suf, Val, and sum store, and how your modify function is working as I'm having trouble with these parts. Thank you.
Here's another approach to problem H which is very surprising for me. We can just make store all positions of each distinct value. Then apply the Kadane's algorithm to find the leftmost and the rightmost of each local maximum power of 2. Lastly, just find the maximum of them. Here's the code to what I'm saying: https://codeforces.me/contest/1692/submission/161122830
[Deleted]
Greedy Approach for last question : Gambling ->
Suppose we have this example :
First make map< long long , vector> and insert key : [with vector of indexes]
then iterate over vector of indexes of each element Initialize res = 1 ( represent power of 2. Initially 1 because for one occurrence we have 1*2)
CODE
hi
Another div4 is coming soon
Will participate in next div4
In problem E editorial there is a mistake
here we have to choose largest value of r , not smallest.
What was the logic of 1st Question?
Why this approach failed for problem E:
In the solution of D, why the 2nd for loop is running 2022 iterations?