Author: SashaT9, prepared: SashaT9, Skillful_Wanderer
Tutorial
Tutorial is loading...
Code C++
#include<bits/stdc++.h>
using namespace std;
int main()
{
int t;cin>>t;
while(t--)
{
int n;cin>>n;
int cnt=0;
for(int i=0;i<n;i++)
{
int x;cin>>x;
if(x%2!=0)cnt++;
}
if(cnt%2==0)cout<<"YES\n";
else cout<<"NO\n";
}
}
Code Python
for i in range(int(input())):
n=int(input())
a=[*map(int,input().split())]
cnt=0
for i in range(n):
if a[i]%2!=0:cnt+=1
if cnt%2==0:print('YES')
else:print('NO')
1857B - Максимальное округление
Author: SashaT9, prepared: FBI, Skillful_Wanderer
Tutorial
Tutorial is loading...
Code C++
#include<bits/stdc++.h>
using namespace std;
int main()
{
int t;cin>>t;
while(t--)
{
string s;cin>>s;
s='0'+s;
int p=s.size();
for(int i=s.size()-1;i>=0;i--)
{
if(s[i]>='5')s[i-1]++,p=i;
}
for(int i=(s[0]=='0');i<s.size();i++)
{
cout<<(i>=p?'0':s[i]);
}
cout<<"\n";
}
}
Code Python
for i in range(int(input())):
s=[0]+[*map(int,list(input()))]
k=len(s)
for i in range(len(s)-1,0,-1):
if s[i]>4:s[i-1]+=1;k=i
if s[0]!=0:print(s[0],end='')
s=[*map(str,s)]
print(''.join(s[1:k]+['0']*(len(s)-k)))
1857C - Построение по минимумам
Author: SashaT9, prepared: SashaT9, Skillful_Wanderer
Tutorial
Tutorial is loading...
Code C++
#include<bits/stdc++.h>
using namespace std;
int main()
{
int t;cin>>t;
while(t--)
{
int n;cin>>n;
int m=n*(n-1)/2,b[m];
for(int i=0;i<m;i++)cin>>b[i];
sort(b,b+m);
for(int i=0;i<m;i+=--n)cout<<b[i]<<' ';
cout<<"1000000000\n";
}
}
Code Python
for _ in range(int(input())):
n=int(input())
l=sorted(map(int,input().split()))
j=0
for i in range(n-1,0,-1):
print(l[j],end=' ')
j+=i
print(l[-1])
Author: Pa_sha, prepared: SashaT9, Skillful_Wanderer
Tutorial
Tutorial is loading...
Code C++
#include<bits/stdc++.h>
using namespace std;
const int N=200005;
int a[N],b[N];
int main()
{
int t;cin>>t;
while(t--)
{
int n;cin>>n;
for(int i=1;i<=n;i++)cin>>a[i];
for(int i=1;i<=n;i++)cin>>b[i];
int mx=INT_MIN;
for(int i=1;i<=n;i++)mx=max(mx,a[i]-b[i]);
int c=0;
for(int i=1;i<=n;i++)c+=(a[i]-b[i]==mx);
cout<<c<<"\n";
for(int i=1;i<=n;i++)if(a[i]-b[i]==mx)cout<<i<<' ';
cout<<"\n";
}
}
Code Python
for _ in range(int(input())):
n=int(input())
a=[*map(int,input().split())]
b=[*map(int,input().split())]
c=[a[i]-b[i] for i in range(n)]
mx=max(c)
ans=[]
for i in range(n):
if c[i]==mx:ans.append(i+1)
print(len(ans))
print(*ans)
Author: SashaT9, prepared: SashaT9, Skillful_Wanderer
Tutorial
Tutorial is loading...
Code C++
#include<bits/stdc++.h>
using namespace std;
const int N=200005;
pair<int,int>x[N];
long long a[N];
int main()
{
int t;cin>>t;
while(t--)
{
int n;cin>>n;
long long s1=0,s2=0;
for(int i=1;i<=n;i++)
{
cin>>x[i].first;
x[i].second=i;
s2+=x[i].first;
}
sort(x+1,x+n+1);
for(int i=1;i<=n;i++)
{
s2-=x[i].first;
s1+=x[i].first;
a[x[i].second]=n+1ll*x[i].first*(2*i-n)-s1+s2;
}
for(int i=1;i<=n;i++)cout<<a[i]<<" \n"[i==n];
}
}
Code Python
for i in range(int(input())):
n=int(input())
a=sorted([(b,i)for i,b in enumerate(map(int,input().split()))])
ans=[0]*n
s1=0
s2=sum(a[i][0] for i in range(n))
for i in range(n):
ans[a[i][1]]=s2-a[i][0]*(n-i)+n-i+a[i][0]*i-s1+i
s1+=a[i][0]
s2-=a[i][0]
print(*ans)
Author: Pa_sha, prepared: Pa_sha, Skillful_Wanderer
Tutorial
Tutorial is loading...
Code C++
#include<bits/stdc++.h>
using namespace std;
map<long long,int>cnt;
long long my_sqrt(long long a)
{
long long l=0,r=5000000001;
while(r-l>1)
{
long long mid=(l+r)/2;
if(1ll*mid*mid<=a)l=mid;
else r=mid;
}
return l;
}
long long get(int b,long long c)
{
long long D=1ll*b*b-4ll*c;
if(D<0)return 0;
long long x1=(b-my_sqrt(D))/2;
long long x2=(b+my_sqrt(D))/2;
if(x1+x2!=b||x1*x2!=c)return 0;
if(x1==x2)return 1ll*cnt[x1]*(cnt[x1]-1)/2ll;
else return 1ll*cnt[x1]*cnt[x2];
}
int main()
{
int t;cin>>t;
while(t--)
{
int n;cin>>n;
cnt.clear();
for(int i=1;i<=n;i++)
{
int x;cin>>x;
cnt[x]++;
}
int q;cin>>q;
for(int i=0;i<q;i++)
{
int b;long long c;
cin>>b>>c;
cout<<get(b,c)<<" \n"[i==q-1];
}
}
}
Code Python
from collections import Counter
from math import sqrt
for _ in range(int(input())):
n=int(input())
a=[*map(int,input().split())]
d=Counter(map(str,a))
for i in range(int(input())):
x,y=map(int,input().split())
if x*x-4*y<0:print(0);continue
D=int(sqrt(x*x-4*y))
x1=(x+D)//2
x2=(x-D)//2
if x1+x2!=x or x1*x2!=y:print(0);continue
if x1!=x2:print(d[str(x1)]*d[str(x2)])
else:print(d[str(x1)]*(d[str(x1)]-1)//2)
Author: SashaT9, prepared: SashaT9, Skillful_Wanderer
Tutorial
Tutorial is loading...
Code C++
#include<bits/stdc++.h>
using namespace std;
const int N=200000,mod=998244353;
int p[N+1],sz[N+1];
struct edge
{
int u,v,w;
void read(){cin>>u>>v>>w;}
bool operator<(edge x){return w<x.w;}
}a[N+1];
int leader(int v)
{
if(p[v]==v)return v;
else return p[v]=leader(p[v]);
}
void unite(int u,int v)
{
u=leader(u);
v=leader(v);
p[u]=v;
sz[v]+=sz[u];
}
long long binpow(long long a,long long n)
{
if(n==0)return 1;
if(n%2==0)return binpow(a*a%mod,n/2);
else return a*binpow(a,n-1)%mod;
}
int main()
{
int t;cin>>t;
while(t--)
{
int n,S;cin>>n>>S;
for(int i=1;i<=n;i++)p[i]=i,sz[i]=1;
for(int i=0;i<n-1;i++)a[i].read();
sort(a,a+n-1);
long long ans=1;
for(int i=0;i<n-1;i++)
{
int sub_u=sz[leader(a[i].u)];
int sub_v=sz[leader(a[i].v)];
ans=ans*binpow(S-a[i].w+1,1ll*sub_u*sub_v-1)%mod;
unite(a[i].u,a[i].v);
}
cout<<ans<<"\n";
}
}
Code Python
mod=998244353
def find_(v):
stack=[v]
while dsu[v]!=v:
stack.append(dsu[v])
v=stack[-1]
while stack:
dsu[stack[-1]]=dsu[v]
v=stack.pop()
return dsu[v]
for i in range(int(input())):
n,S=map(int,input().split())
l=[tuple(map(int,input().split()))for i in range(n-1)]
l.sort(key=lambda x:x[2])
ans=1
dsu=[i for i in range(n)]
coun=[1]*n
for a,b,c in l:
a-=1;b-=1
if find_(a)!=find_(b):
ans=ans*pow(S-c+1,coun[dsu[a]]*coun[dsu[b]]-1,mod)
ans%=mod
coun[dsu[a]]+=coun[dsu[b]]
coun[dsu[b]]=0
dsu[b]=dsu[a]
print(ans)
Thanks for the editorial!
In problem F (also in general), you can use sqrtl(x) for a precise square root function.
I failed test 10 with sqrtl though 217692816
Do you know why?
You are not printing anything when y%sol1 != 0 or when y%sol2 != 0.
In problem B ,how the iterations are done.
From the right to the left
You can also do the iterations from left to right. Refer to this solution 217641399
Can you attach this editorial to the contest's materials? UPD: I can see it now. Nice contest:D
This round was one of the most interesting divs for me. I spent most of the round trying to solve A. I never got it, but I really liked it (usually I think the opposite about unsolved problems :))
In general, thanks for the round, it was really cool
There is an even simpler solution to A. If the sum is even then, on any colouring, the parity of the two colour sets must be the same; if it is odd then they must be different. Hence one can simply sum the array and check the parity of the sum.
This is exactly what I did.
E can also be solved with DP: 217832098 so sad during contest i didn't have enough time to remember about case with one point
It was a great contest with thought-provoking problems. I am hoping to get pupil through the results of this one, and I'm so glad to finally make it to 1200 after 3 months of trying ^^
Mathforces!
As for me, mathematics was only in two problems
Alternate and hopefully more intuitive solution for E:
We shall work based on adding and subtracting segment lengths.
Submission: https://mirror.codeforces.com/contest/1857/submission/217837318
I found this easier than working with prefixes and suffixes, and also than the formula given in the editorial. It felt more intuitive to just slide over next segments to compute them, adding and subtracting segment lengths accordingly
Thanks for the round, it was great. The only problem I didn't like was B, since it was heavy implementation, and probably a little too hard for div3B. And I think F is just too easy if you know quadratic equations, and very hard if you don't (except if there is a solution not depending on that that I'm unaware of). Overall the round was great :)
I do not remember asking for ur opinion of the problems.
You know, I don't remember my E failing during the round, especially since it cost you the promotion to expert ;)
Tell me that u are strange person without actually telling me
Tell me that you don't understand the idea of memes without actually telling me.
Tell me that u dont have life without actually telling me(your stats on cf last year :)))))))
Uh oh ad personam, you love to see it. Just wanted to inform you that being invested in your hobby doesn't necessarily mean that you don't life.
I tried the problem A in C++ yesterday (the first time I used it in a competitive programming contest) and for some reason the code was returning completely random results with different builds despite the same exact code, which is why I can't solve it even though I can :(
For problem A, my approach was to use prefix sum array, then for a
forloop from1tonwithias the variable, we consider the sum of elements from[1..i]and the sum of elements from[i+1..n]. If both sums are odd or even then we find the answer.For problem B, I basically implemented the problem's requirements. Didn't get it right on time because of burn out from problem A, so I don't solve it either.
did your solution to A got AC?
No, unfortunately.
yea thought that it wouldn't because your are only dividing the array into 2 subarrays while its possible to taking 2 different subsequences of the array that can would satisfy the parity requirement.
i think B,C need to be easier with clear statement as this div is for low rated contestants
G was cute :)
I have one doubt in F a[i] + a[j] = x => (a[i] + a[j])^2 = x^2 => a[i]^2 + a[j]^2 + 2a[i].a[j] = x^2
=> a[i]^2 + a[j]^2 = x^2-2y (as a[i].a[j] = y)
so this way we get a[i]^2 + a[j]^2 = x^2-2y this equation so is there a way to prove that for this equation there are only two values of a[i] and a[j] that satisfy this equation? as mentioned in the tutorial
The fundamental theorem of algebra says a polynomial of degree $$$n$$$ has $$$n$$$ roots (they can be not distinct).
You know, Vieta theorem was proven eons ago), it has either 2 distinct roots, 2 equal roots, or no roots
Why can't I submit code..still showing system testing 100 %
Substitute $$$a_i = x - a_j$$$ or the other way around and you get a quadratic equation with one variable since $$$x$$$ and $$$y$$$ are constant. Of course, it has at most two distinct solutions.
oh yeah Thank you
for the above replies earlier I was actually not looking for the proof, that a polynomial of degree 2 has 2 roots, I was just asking for that using my approach is it possible to prove that it has just two values of a[i] and a[j], as I wasn't able to get the hint that during the actual content that we can make a polynomial equation using that, but this idea clicked me.
but thanks to all of u
Math Problems,and in my opinion,F is a little easy.
What a good contest! the problems were really easy to understand! thank you for this contest!!!
why am i getting TLE on Problem F at test case 41 ?217727479
Use map instead of unordered_map and you will get AC.
I got this problem either. But I don't understand why map is faster than unordered_map...
Time complexity of unordered map is O(1) but in worst case it is O(n). You can check this blog : https://mirror.codeforces.com/blog/entry/62393
Thanks a lot! You save my life.
Don't try to use
unordered_mapin CF,usemapinstead.I used
unordered_mapin a contest,and my code was hacked.why is this ?
Check this : https://mirror.codeforces.com/blog/entry/62393
for(int i=0;i<m;i+=--n)cout<<b[i]<<' '; cout<<"1000000000\n"; can anyone please tell me what actually done here, In problem B Code
If you don't understand the part with
i+=--n, than it is the same asmeaning that we output $$$b[0],b[n-1],b[n+n-2],b[n+n+n-3],\dots$$$
At last we output $$$10^9$$$ because we can't determine the max element from $$$a$$$, and $$$10^9$$$ is the "neutral" one. All the elements in the array $$$b$$$ are not greater than $$$10^9$$$.
Thank you so much
My solution for problem F : https://mirror.codeforces.com/contest/1857/submission/217713950 got hacked during the contest. I used a map instead of a umap and it passed testing. Why did that happen?
Reading the editorial of E, I can't understand how to pass from the first line of the formulae to the second one. I'm sorry, but my last courses of maths are 30 years ago! Thanks in advance
the $$$n$$$ in the second line is the sum of all the $$$'1's$$$ in the first line. Since the $$$s$$$ is a fixed value,so we can extract $$$s$$$ from the two $$$\sum \quad$$$,which are $$$s \cdot i$$$ and $$$-s \cdot (n-i)$$$
In problem F i run a loop for checking it is perfect square root or not. https://mirror.codeforces.com/contest/1857/submission/217941678 Loop is from (s-1) to (s+1) so at max 3 times it will run , but is giving TLE on Test case 65, same code i just checked by if else condition for these 3 values i got AC. https://mirror.codeforces.com/contest/1857/submission/217941713
What can be possible resons as Time complexity will increase 3 times so from 500ms --> 1500ms but is over more then 4s
ll int s=sqrtl(d)The variable
sislong longhere.for(int i=max(0LL,s-1);i<=(s+1);i++)Meanwhile the variable
iisinthere, althoughmax(0LL,s-1)will return the number greater than or equal to0but the convert fromlong longtointmay give negative number because of the overflow, theforhere may loop in a huge range (for example-1e9to1e9) that can cause the TLE.You can declare
iaslong longand submit again.yaa i got AC thanks
Thanks for this round! All the questions are good.And the ways to solve the problems are interesting!!
Why hash collisions can't be done for officials Python solution for problem F
In Python 3.x, the result of hashing the string will be different across code invocations, but integer hashing is always the same. So, it is impossible to come up with a test against random hashing.
I understand that in tutorial problem G, you can put (s — w + 1) weights into the edge, but the required is only one MST, so you cannot put the weight w, but the formula (s — w + 1) remains because of the possibility of not choosing that edge. I don't know am I wrong?
You are right:)
u r right
The official Python solution to problem F writes the answers to the queries one per line, rather than all on the same line (as specified in the problem) yet passes the tests. Does the checker not check the layout of the results?
Yes, the checker doesn't care.
The provided Python solution to problem F converts the values in the array to strings before counting them, rather than simply counting the number of instances of each value as an integer. I did some experiments and this seems to be necessary to get the required performance (in particular to pass test 30), but I have no idea why this should be faster. Can anybody suggest why this should improve things?
Note that the official C++ solution doesn't do this.
In Python, structures such as set, dict, defaultdict and Counter are implemented as hash tables. The analogue of Python dict in c++ is unordered_map, and as you know, this structure is very popular for hacking using anti-hash-table tests. Test 30 is exactly the anti-hash-table test for Python, which increases the time complexity of finding an element by key from O(1) to O(n). To prevent the Python code from being hacked, commonly people use a custom randomized hash function (the code can be found here). Now about provided solution, in Python hashing of int type always happens in the same way, but str is hashed differently each time the code is run, so it's convenient to just convert int to str. Since the hashing will be different every time, it will be impossible to come up with a test against it. This method turned out to be even faster than using your own randomised hash function.
I am wondering why in Question F (Sum and Product), when I used unordered_map, I gdt TLE for test 29? Once I changed it to map, my answer got accepted? but generally speaking, unordered_map is faster. I know that in the worst case, it takes O(n) time for unordered_map, but I want to know which one I should use when I am faced with another contest.
By the way, here is my code 218194298
It sounds as if you hit the same problem as me (although in a different language). See https://mirror.codeforces.com/blog/entry/119134?#comment-1057222 and the reply by Skillful_Wanderer. A C++ unordered_map, like a Python Counter, is implemented as a hash table.
Really good round. Very interesting problems. Not too hard, not too easy. It's ideally balanced, as I think.
Why does below code give TLE @test30? ~~~~~
import math from collections import Counter for _ in range(int(input())): n=int(input()) arr=list(map(int,input().split())) g=Counter(arr) q=int(input()) final=[] for _ in range(q): s,p=map(int,input().split()) try: t1=(s+math.sqrt(s*s-4*p))/2 t2=(s-math.sqrt(s*s-4*p))/2 if t1!=t2: print(g[t1]*g[t2]) else: print((g[t1]*(g[t1]-1))//2) except: print(0)~~~~~
The answer is here
G is a good problem.
problem F is one of the best problems I have ever done on codeforces.
Guys I want some friends with whom I can do cp, So, if any one who loves problem solving we could somehow connect.
Problem D requires the output to be sorted, but that is never mentioned in the problem! that caused me several WAs on the 3rd test.
G can be solved (dumber way) by $$$O(n log^2n)$$$ centroid decomposition, although it barely fits in time limit
235049670
import java.io.*; import java.util.*; public class x { public static void main(String aa[]) { Scanner z=new Scanner(System.in); int t=z.nextInt(); while((t--)>0) { String s=z.next(); s='0'+s; int n=s.length(); char c[]=s.toCharArray(); //int t=-1; int y,k=-1; for(y=n-1;y>=0;y=y-1) { if(c[y]>='5') { c[y-1]=(char)(c[y-1]+1); c[y]='0'; k=y-1; } } s=""; if(k!=-1) { for(y=k+1;y<n;y++) c[y]='0'; } for(y=0;y<n;y++) s=s+c[y]; //System.out.println(s); if(s.charAt(0)=='0') s=s.substring(1); //System.out.println(s); //n=s.length(); System.out.println(s); } } }
I have written this code for 1857B — Maximum Rounding problem and this gives TLE can anyone tell me why is it giving TLE. When I convert the given code to C++ with ChatGpt and submit then no issue it gets submitted.
In problem G, can't we just fix our MST and explore all possible combination of the remaining edges, for every edge weights in the range:
[max(MST weights), S]?? So if the remaining edges arek, that means we have2^kmany combinations of the possible graphs. And now for every value in the range:[max(MST weights), S], there would be exactly2^kavailable options of edges to assign this weight to. i.e., total of(2^k)^(S-max(MST_weight)).