Hello,
The problem set is basically divided into 2 parts, very easy problems that were created for teams completely new to ICPC contests, and harder problems for experienced teams. I believe that all the problems were suitable for a div.3 contest except for problems G and L.
Tutorial is loading...
Code
#include <bits/stdc++.h>
using namespace std;
int main(){
int a, b;
scanf("%d%d", &a, &b);
printf("%d\n", a >= b);
}
Tutorial is loading...
Code
#include <bits/stdc++.h>
using namespace std;
bool isp(int x){
if (x < 2)return false;
for (int i = 2; i * i <= x; ++i)if (x % i == 0)return false;
return true;
}
int main(){
int x;
scanf("%d", &x);
if (isp(x - 2))printf("%d %d\n", 2, x - 2);
else printf("-1\n");
}
Tutorial is loading...
Code
#include <bits/stdc++.h>
using namespace std;
int main(){
int s , x ;
scanf("%d %d" , &s , &x) ;
int ans = 0 ;
while (s > 0){
s/=x ;
ans++;
}
if (ans != 0)
printf("%d\n" , ans) ;
else
printf("%d\n" , 1) ;
}
Tutorial is loading...
Code
#include <bits/stdc++.h>
using namespace std;
void solve(){
string an;
for (int i = 0; i < 24; ++i)an += "DL";
an += "RRUU";
printf("%d\n%s\n", (int)an.size(), an.c_str());
}
int main(){
int t;
scanf("%d", &t);
while (t--)solve();
}
Tutorial is loading...
Code
#include <bits/stdc++.h>
using namespace std;
#define f(i, x, n) for(int i = x; i < (int)(n); ++i)
void solve(){
string an;
f(it, 0, 24)an += "DL";
f(it, 0, 4){
f(it, 0, 5)an += 'U';
f(it, 0, 2)an += 'L';
f(it, 0, 5)an += 'D';
an += 'L';
f(it, 0, 5)an += 'D';
}
an += "RRRRRRRRDDUUURDDDDUUUUULLDDDDRRUUUU";
printf("%d\n%s\n", (int)an.size(), an.c_str());
}
int main(){
int t;
scanf("%d", &t);
while (t--)solve();
}
Tutorial is loading...
Code
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 3000 + 10;
const int M = 1000000007;
const double eps = 1e-9;
const double PI = acos(-1);
const int oo = 1000000;
#define pb push_back
int n,x[N],y[N],l[N],r[N],indeg[N];
bool g[N][N];
void get(int &n, int l, int r){
assert(scanf("%d",&n)+1);
assert(n>=l && n<=r);
}
set<pair<int, int>> st;
int main(){
get(n,1,3000);
for(int a,rn,i=0; i<n; ++i){
get(x[i], -oo, oo);
get(y[i], -oo, oo);
get(a, 0, 359);
get(rn, 0, 89);
l[i]=(a-rn+360)%360;
r[i]=(a+rn)%360;
assert(st.insert({x[i],y[i]}).second);
}
for(int i=0; i<n; ++i){
for(int j=0; j<n; ++j){
if(i==j)continue;
int dx=x[j]-x[i], dy=y[j]-y[i];
double ang=atan2(dy,dx);
if(ang<0)
ang+=2*PI;
ang*=180/PI;
bool in=0;
if(l[i]>r[i]){
if(ang+eps>=l[i] || ang-eps<=r[i])
in=1;
}else if(ang+eps>=l[i] && ang-eps<=r[i])
in=1;
g[i][j]=in;
indeg[j]+=in;
}
}
queue<int> q;
for(int i=0; i<n; ++i)
if(!indeg[i])
q.push(i);
vector<int> ans;
while(!q.empty()){
int u=q.front();
q.pop();
ans.push_back(u+1);
for(int i=0; i<n; ++i)
if(g[u][i] && !--indeg[i])
q.push(i);
}
if(ans.size()<n)
return cout<<-1<<endl,0;
for(int i=0; i<n; ++i)
printf("%d%c", ans[i], i<n-1?' ':'\n');
return 0;
}
Tutorial is loading...
Code
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define f(i, x, n) for(int i = x; i < (int)(n); ++i)
int const N = 100000;
ll const inf = 2e18;
int n;
struct S{
int fr;
ll a, b, mn;
S(){}
S(int _a, ll _b):fr(1), a(_a), b(_b), mn(_a + _b) {}
S operator +(S const &o){
S an;
an.fr = fr + o.fr;
an.a = a + o.a;
an.mn = min(mn, o.mn + a);
return an;
}
}s[N << 2];
void st(int i, int a1, ll b1, int l = 1, int r = n, int id = 1){
if (l == r)return void(s[id] = S(a1, b1));
int m = l + r >> 1, a = id << 1, b = a | 1;
if (i <= m)st(i, a1, b1, l, m, a);
else st(i, a1, b1, m + 1, r, b);
s[id] = s[a] + s[b];
}
void kl(ll x, ll sm = 0, int l = 1, int r = n, int id = 1){
if (l == r){
if(sm + s[id].mn >= x)return;
s[id].fr = 0;
s[id].a = 0;
s[id].b = inf;
s[id].mn = inf;
return;
}
int m = l + r >> 1, a = id << 1, b = a | 1;
if (s[b].mn + sm + s[a].a < x)kl(x, sm + s[a].a, m + 1, r, b);
if (s[a].mn + sm < x)kl(x, sm, l, m, a);
s[id] = s[a] + s[b];
}
int bs(ll x, ll sm = 0, int l = 1, int r = n, int id = 1){
if (l == r)return x >= sm + s[id].a ? s[id].fr : 0;
int m = l + r >> 1, a = id << 1, b = a | 1;
if (s[a].a + sm > x)return bs(x, sm, l, m, a);
else return s[a].fr + bs(x, sm + s[a].a, m + 1, r, b);
}
int dead(ll x){
int fr = s[1].fr;
kl(x);
return fr - s[1].fr;
}
int hungry(ll x) { return s[1].fr - bs(x); }
int main(){
scanf("%d", &n);
f(i, 1, n + 1){
int a;
ll b;
scanf("%d%lld", &a, &b);
st(i, a, b);
}
int q;
scanf("%d", &q);
while (q--){
int o;
scanf("%d", &o);
if (o == 1){
ll x;
scanf("%lld", &x);
int b = hungry(x), a = dead(x);
printf("%d %d\n", a, b);
}else {
int a, c;
ll b;
scanf("%d%lld%d", &a, &b, &c);
st(c, a, b);
}
}
}
Tutorial is loading...
Code
#include <bits/stdc++.h>
using namespace std;
const double pi = acos(-1) ;
int main() {
double v , s ;
scanf("%lf %lf" ,&v , &s) ;
double ans ;
ans = s/(2.0 * sin(pi/v)) ;
printf("%.9lf" , ans * ans * pi) ;
return 0;
}
Tutorial is loading...
Code
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define f(i, x, n) for(int i = x; i < (int)(n); ++i)
int const N = 1000000;
char s[N + 1];
int an[N], n;
inline bool isNumberDigit(char c) { return c >= '0' && c <= '9'; }
int I;
inline int readInteger(){
int an = 0;
while (isNumberDigit(s[I])){
an = an * 10 + s[I] - '0';
++I;
}
return an;
}
void readSoldier(int supervisor){
int id = readInteger();
while (s[I] == '('){
++I;
readSoldier(id);
++I;
}
an[id] = supervisor;
}
int main(){
scanf("%d%s", &n, s);
readSoldier(0);
printf("%d", an[1]);
f(i, 2, n + 1)printf(" %d", an[i]);
printf("\n");
}
Tutorial is loading...
Code
#include <bits/stdc++.h>
using namespace std;
const int N = 2001,M = 1e9 + 7;
int n,m,k,dp[N][N],ans;
void add(int &a,int b){
a+=b;
if(a >= M)a-=M;
}
int main(){
scanf("%d%d%d",&n,&k,&m);
k = min(m,k);
dp[0][0] = 1;
for(int i = 0;i < m;i++)
for(int j = 0;j <= k;j++){
if(j + 1 <= k)add(dp[i + 1][j + 1],dp[i][j]);
if(j - 1 >= 0)add(dp[i + 1][j - 1],dp[i][j]);
}
for(int i = 2;i <= m;i+=2)add(ans,dp[i][0]);
printf("%d\n",2LL*n*ans%M);
}
Tutorial is loading...
Code
#include <bits/stdc++.h>
using namespace std;
typedef long long ll ;
int n , a[25];
vector<int>v ;
ll ans = 0 ;
void calc(int idx) {
if (idx == n)
{
int x = 0 ;
for(int i =0 ; i<v.size() ; ++i) {
x |=v[i] ;
}
ans+= 1ll *x ;
return ;
}
v.push_back(a[idx]) ;
calc(idx+1) ;
v.pop_back() ;
calc(idx+1) ;
}
int main() {
scanf("%d" , &n) ;
for (int i =0 ; i<n ; ++i) {
scanf("%d" , &a[i]) ;
}
calc(0) ;
printf("%lld\n" , ans) ;
return 0;
}
Spoiler!
Instead of going through all the subsets, we will try to find a simpler way by going through the bits of the given numbers. we know that the number of subsets is $$$2^n - 1$$$, for the $$$i^{th}$$$ bit of each number we know it's either $$$1$$$ or $$$0$$$, you can notice that for a resulting subset of ORing some numbers, its $$$i^{th}$$$ bit is $$$0$$$ $$$iff$$$ all the $$$i^{th}$$$ bit of elements in the subset is $$$0$$$. With this observation we can eliminate all the $$$i^{th}$$$ bits of $$$0's$$$ in all subsets and add keep the $$$1's$$$ and then add the summation of the $$$1's$$$ of $$$i^{th}$$$ bit to the final answer. In short, what you have to do is to find the summation for each $$$i^{th}$$$ bit in all subsets, but don't forget to multiply by its digit place, and you get the resulting formula for the $$$i^{th}$$$ bit (assuming $$$x = 0's$$$ $$$count$$$ $$$for$$$ $$$i^{th}$$$ $$$bit$$$) the answer is : $$$((2^n -1) - (2^x-1)) * 2^i.$$$
Complexity: $$$O(n)$$$
Solution code
#include <bits/stdc++.h>
using namespace std;
typedef long long ll ;
const int N = 1e5+5 ;
int n , a[N] , zero[31];
int main() {
scanf("%d" , &n) ;
for (int i =0 ; i<n; ++i) {
scanf("%d" , &a[i]) ;
}
for (int i = 0; i <31 ; i++){
for (int j = 0; j < n; j++) {
if (!(a[j] & 1 << i)) {
zero[i]++;
}
}
}
ll ans = 0;
for (int i = 0; i < 31 ; i++)
{
ans += (1ll * ( (1<<n) - 1) - (1ll*(1<<zero[i]) - 1)) * 1ll*(1<<i);
}
printf("%lld\n" , ans) ;
return 0;
}
Tutorial is loading...
Code
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define f(i, x, n) for(int i = x; i < (int)(n); ++i)
int const N = 200000;
char s[N + 1];
vector<pair<int, int> > an;
void no() { printf("-1\n"); exit(0); }
inline void ad(int tp, int i) { an.push_back(make_pair(tp, i)); }
int main(){
scanf("%s", s);
int n = strlen(s);
string v;
f(i, 0, n)if (s[i] == 'c'){ // first remove all 'c' characters
if (v.empty())no(); // 'c' is first character in string
if (v.back() == 'a'){ // "ac"
ad(3, v.size() + 1);
v += 'b';
v += 'a';
}else {
if (v.size() == 1)no(); // "bc"
if (v[v.size() - 2] == 'a'){ // "abc"
ad(4, v.size() - 1);
v.pop_back();
v.pop_back();
}else { // "bbc"
ad(2, v.size() - 1);
ad(3, v.size());
ad(4, v.size() + 1);
}
}
}else v += s[i];
string g;
f(i, 0, v.size())if (v[i] == 'b'){ // string contains only 'a' and 'b'
if (g.empty())no();
ad(2, g.size() + 1);
ad(4, g.size());
g.pop_back();
}else g += v[i];
f(i, 0, g.size()){ // remove any left 'a' characters
ad(1, 1);
ad(2, 2);
ad(4, 1);
}
printf("%d\n", (int)an.size());
f(i, 0, an.size())printf("%d %d\n", an[i].first, an[i].second);
}
omg I didn't notice that the input in problem B (primes) is always a prime number , I solved it by building sieve array :D :D .
still waiting for F editorial .
very nice problems , thank you so much .
I also did the same:)
Need help in I Can we do this by using stack? 56522390
yes, you can. I did the same but using vector instead of stack. but you have the same mistake I had done. when you see like this bracket "(" you push the next element, this is wrong. imagine 3(10(15)) so you push 1 instead of 10 and again 1 instead of 15. so you need to get the whole number. my solution if you want to check how I solve this problem 56524350
Ohk, I got it now
Thanks for the help
Can anyone help me in understanding the concept behind the O(N) solution of problem K. I know it is a fairly common problem but I cannot seem to grasp the idea behind it. Can anyone please help me? It will really help me out in solving other problems like this.
Can we do J using matrix exponential? There is a trick which calculates number of walks of length k in a graph by raising the power of adjacency matrix to k.
Yes we can by taking the sub-graph that we're only allowed to walk on from the original graph, but it has worse complexity, $$$O(m^3 \log{k}$$$).
Actually, this solution, even if the limits are made smaller, will be wrong because we want the sum of matrix[0][0] for all powers from 2 to min(m,k). so using matrix exponentiation has a complexity of $$$O(m^3min(m,k))$$$
we can add another row and column to the adjacency matrix and let one of the new cells be responsible for the sum of cell (0,0).
yea sure that works.
For Question F, we can also find the answer by applying dfs and taking the post order traversal of graph, right?
I'm new here but wouldn't ...
... be an easier way to solve C (Dolls)?
That's another way to solve it, the intended solution is for people that don't know much about the log function.
In problem F, we wrote this code
We are getting WA on test case 128, and we are unable to see if we have done a error in logic or if there is an error in handling precision.
We have written a very neat code so that you won't have trouble in understanding and debugging it.
Someone please have a look at the code and help us out.
Are you sure this is correct:
won't that give you the opposite of what you want?
Yes we have realised that we were doing just the opposite. Now we have corrected our code but still we are getting WA on test case 133. What else do you think could be wrong?
try this:
Okay Thanks we understood where we are going wrong.
Thank you very much for helping us out.