Hi, all!↵
↵
This is not [user:Tommyr7,2017-10-06], but the **impostor** behind the round :P. The statements are written by me. The characters in the round feature, again, the _Monogatari_ anime series, and to be more specific, _Nisemonogatari: Fake Tale_. The statements involve stories with fake things and oddities, but as per tradition, contain no spoilers. Thank you, everyone, and hope you've all enjoyed the round!↵
↵
On a side note, special kudos to [the best impostors of the round](http://codeforces.net/blog/entry/54971?#comment-389321) (except me, lol)!↵
↵
Any feedback on problems and tutorials are welcome -- we look forward to doing even better in the future!↵
↵
Here are hints for all problems and detailed tutorials for the first two. Stay tuned, more are coming!↵
↵
<hr>↵
↵
### Hints↵
↵
<spoiler summary="Problem A">↵
First approach: Optimize the straightforward solution.↵
↵
<spoiler summary="... or even...">↵
Second approach: Believe in magic.↵
</spoiler>↵
↵
</spoiler>↵
↵
<spoiler summary="Problem B">↵
Multiply instead of divide. What happens to the last digit when multiplying?↵
</spoiler>↵
↵
<spoiler summary="Problem C">↵
Consider islands of **two** colours and the bridges between them.↵
</spoiler>↵
↵
<spoiler summary="Problem D">↵
Iterate over all possible combination, order and direction of extra edges.↵
</spoiler>↵
↵
<spoiler summary="Problem E">↵
First approach: 2D segment tree (or quadtree) with a `set` or `vector` on each node, representing the set of barriers that cover this node.↵
↵
<spoiler summary="... or may as well...">↵
Second approach: Assign a random value to each barrier. Then utilise 2D Fenwick trees.↵
</spoiler>↵
↵
</spoiler>↵
↵
<hr>↵
↵
### Tutorials↵
↵
### [problem:869A]↵
**Author** [user:Tommyr7,2017-10-06], [user:cyand1317,2017-10-06] / **Preparation** [user:Tommyr7,2017-10-06], [user:cyand1317,2017-10-06] / **Tutorial** [user:cyand1317,2017-10-06]↵
↵
<spoiler summary="Tutorial">↵
[tutorial:869A]↵
</spoiler>↵
↵
<spoiler summary="Solution 1 (Tommyr7)">↵
~~~~~↵
#include <bits/stdc++.h>↵
using namespace std;↵
#define Maxn 4000007↵
bool vis[Maxn];↵
int a[4007],b[4007],n;↵
int main()↵
{↵
scanf("%d",&n);↵
memset(vis,false,sizeof(vis));↵
for (int i=1;i<=n;i++)↵
{↵
scanf("%d",&a[i]);↵
vis[a[i]]=true;↵
}↵
for (int i=1;i<=n;i++)↵
{↵
scanf("%d",&b[i]);↵
vis[b[i]]=true;↵
}↵
int ans=0;↵
for (int i=1;i<=n;i++)↵
for (int j=1;j<=n;j++)↵
if (vis[a[i]^b[j]]) ++ans;↵
if (ans%2==0) printf("Karen\n"); else printf("Koyomi\n");↵
return 0;↵
}↵
~~~~~↵
</spoiler>↵
↵
<spoiler summary="Solution 2 (cyand1317)">↵
~~~~~↵
#include <stdio.h>↵
↵
int main()↵
{↵
puts("Karen");↵
return 0;↵
}↵
~~~~~↵
</spoiler>↵
↵
↵
### [problem:869B]↵
**Author** [user:Tommyr7,2017-10-06] / **Preparation** [user:Tommyr7,2017-10-06] / **Tutorial** [user:cyand1317,2017-10-06]↵
↵
<spoiler summary="Tutorial">↵
[tutorial:869B]↵
</spoiler>↵
↵
<spoiler summary="Model solution (Tommyr7)">↵
~~~~~↵
#include <bits/stdc++.h>↵
using namespace std;↵
long long L,R;↵
int ans;↵
int main()↵
{↵
scanf("%lld%lld",&L,&R);↵
if (R-L>=10) printf("%d\n",0);↵
else↵
{↵
ans=1;↵
for (long long i=L+1;i<=R;i++)↵
ans=(1LL*ans*(i%10))%10;↵
printf("%d\n",ans);↵
}↵
return 0;↵
}↵
~~~~~↵
</spoiler>↵
↵
↵
### [problem:869C]↵
**Author** [user:Tommyr7,2017-10-06] / **Preparation** [user:Tommyr7,2017-10-06] / **Tutorial** [user:Tommyr7,2017-10-06]↵
↵
<spoiler summary="Tutorial">↵
[tutorial:869C]↵
</spoiler>↵
↵
<spoiler summary="Model solution (Tommyr7)">↵
~~~~~↵
#include <bits/stdc++.h>↵
#define Maxn 5007↵
#define modp 998244353↵
int p[Maxn][Maxn];↵
int pre[Maxn];↵
int a,b,c;↵
int solve(int x,int y)↵
{↵
int res=0;↵
for (int k=0;k<=x&&k<=y;k++)↵
{↵
int del=pre[k];↵
del=(1LL*del*p[x][k])%modp;↵
del=(1LL*del*p[y][k])%modp;↵
res=(res+del)%modp;↵
}↵
return res;↵
}↵
int main()↵
{↵
scanf("%d%d%d",&a,&b,&c);↵
memset(p,0,sizeof(p));↵
p[0][0]=1;↵
for (int i=1;i<=5000;i++)↵
{↵
p[i][0]=1;↵
for (int j=1;j<=i;j++)↵
p[i][j]=(p[i-1][j-1]+p[i-1][j])%modp;↵
}↵
memset(pre,0,sizeof(pre));↵
pre[0]=1;↵
for (int i=1;i<=5000;i++)↵
pre[i]=(1LL*pre[i-1]*i)%modp;↵
int ans=1;↵
ans=(1LL*ans*solve(a,b))%modp;↵
ans=(1LL*ans*solve(b,c))%modp;↵
ans=(1LL*ans*solve(a,c))%modp;↵
printf("%d\n",ans);↵
return 0;↵
}↵
↵
~~~~~↵
</spoiler>↵
↵
↵
This is not [user:Tommyr7,2017-10-06], but the **impostor** behind the round :P. The statements are written by me. The characters in the round feature, again, the _Monogatari_ anime series, and to be more specific, _Nisemonogatari: Fake Tale_. The statements involve stories with fake things and oddities, but as per tradition, contain no spoilers. Thank you, everyone, and hope you've all enjoyed the round!↵
↵
On a side note, special kudos to [the best impostors of the round](http://codeforces.net/blog/entry/54971?#comment-389321) (except me, lol)!↵
↵
Any feedback on problems and tutorials are welcome -- we look forward to doing even better in the future!↵
↵
Here are hints for all problems and detailed tutorials for the first two. Stay tuned, more are coming!↵
↵
<hr>↵
↵
### Hints↵
↵
<spoiler summary="Problem A">↵
First approach: Optimize the straightforward solution.↵
↵
<spoiler summary="... or even...">↵
Second approach: Believe in magic.↵
</spoiler>↵
↵
</spoiler>↵
↵
<spoiler summary="Problem B">↵
Multiply instead of divide. What happens to the last digit when multiplying?↵
</spoiler>↵
↵
<spoiler summary="Problem C">↵
Consider islands of **two** colours and the bridges between them.↵
</spoiler>↵
↵
<spoiler summary="Problem D">↵
Iterate over all possible combination, order and direction of extra edges.↵
</spoiler>↵
↵
<spoiler summary="Problem E">↵
First approach: 2D segment tree (or quadtree) with a `set` or `vector` on each node, representing the set of barriers that cover this node.↵
↵
<spoiler summary="... or may as well...">↵
Second approach: Assign a random value to each barrier. Then utilise 2D Fenwick trees.↵
</spoiler>↵
↵
</spoiler>↵
↵
<hr>↵
↵
### Tutorials↵
↵
### [problem:869A]↵
**Author** [user:Tommyr7,2017-10-06], [user:cyand1317,2017-10-06] / **Preparation** [user:Tommyr7,2017-10-06], [user:cyand1317,2017-10-06] / **Tutorial** [user:cyand1317,2017-10-06]↵
↵
<spoiler summary="Tutorial">↵
[tutorial:869A]↵
</spoiler>↵
↵
<spoiler summary="Solution 1 (Tommyr7)">↵
~~~~~↵
#include <bits/stdc++.h>↵
using namespace std;↵
#define Maxn 4000007↵
bool vis[Maxn];↵
int a[4007],b[4007],n;↵
int main()↵
{↵
scanf("%d",&n);↵
memset(vis,false,sizeof(vis));↵
for (int i=1;i<=n;i++)↵
{↵
scanf("%d",&a[i]);↵
vis[a[i]]=true;↵
}↵
for (int i=1;i<=n;i++)↵
{↵
scanf("%d",&b[i]);↵
vis[b[i]]=true;↵
}↵
int ans=0;↵
for (int i=1;i<=n;i++)↵
for (int j=1;j<=n;j++)↵
if (vis[a[i]^b[j]]) ++ans;↵
if (ans%2==0) printf("Karen\n"); else printf("Koyomi\n");↵
return 0;↵
}↵
~~~~~↵
</spoiler>↵
↵
<spoiler summary="Solution 2 (cyand1317)">↵
~~~~~↵
#include <stdio.h>↵
↵
int main()↵
{↵
puts("Karen");↵
return 0;↵
}↵
~~~~~↵
</spoiler>↵
↵
↵
### [problem:869B]↵
**Author** [user:Tommyr7,2017-10-06] / **Preparation** [user:Tommyr7,2017-10-06] / **Tutorial** [user:cyand1317,2017-10-06]↵
↵
<spoiler summary="Tutorial">↵
[tutorial:869B]↵
</spoiler>↵
↵
<spoiler summary="Model solution (Tommyr7)">↵
~~~~~↵
#include <bits/stdc++.h>↵
using namespace std;↵
long long L,R;↵
int ans;↵
int main()↵
{↵
scanf("%lld%lld",&L,&R);↵
if (R-L>=10) printf("%d\n",0);↵
else↵
{↵
ans=1;↵
for (long long i=L+1;i<=R;i++)↵
ans=(1LL*ans*(i%10))%10;↵
printf("%d\n",ans);↵
}↵
return 0;↵
}↵
~~~~~↵
</spoiler>↵
↵
↵
### [problem:869C]↵
**Author** [user:Tommyr7,2017-10-06] / **Preparation** [user:Tommyr7,2017-10-06] / **Tutorial** [user:Tommyr7,2017-10-06]↵
↵
<spoiler summary="Tutorial">↵
[tutorial:869C]↵
</spoiler>↵
↵
<spoiler summary="Model solution (Tommyr7)">↵
~~~~~↵
#include <bits/stdc++.h>↵
#define Maxn 5007↵
#define modp 998244353↵
int p[Maxn][Maxn];↵
int pre[Maxn];↵
int a,b,c;↵
int solve(int x,int y)↵
{↵
int res=0;↵
for (int k=0;k<=x&&k<=y;k++)↵
{↵
int del=pre[k];↵
del=(1LL*del*p[x][k])%modp;↵
del=(1LL*del*p[y][k])%modp;↵
res=(res+del)%modp;↵
}↵
return res;↵
}↵
int main()↵
{↵
scanf("%d%d%d",&a,&b,&c);↵
memset(p,0,sizeof(p));↵
p[0][0]=1;↵
for (int i=1;i<=5000;i++)↵
{↵
p[i][0]=1;↵
for (int j=1;j<=i;j++)↵
p[i][j]=(p[i-1][j-1]+p[i-1][j])%modp;↵
}↵
memset(pre,0,sizeof(pre));↵
pre[0]=1;↵
for (int i=1;i<=5000;i++)↵
pre[i]=(1LL*pre[i-1]*i)%modp;↵
int ans=1;↵
ans=(1LL*ans*solve(a,b))%modp;↵
ans=(1LL*ans*solve(b,c))%modp;↵
ans=(1LL*ans*solve(a,c))%modp;↵
printf("%d\n",ans);↵
return 0;↵
}↵
↵
~~~~~↵
</spoiler>↵
↵
