Идея: BledDest
Разбор
Tutorial is loading...
Решение (Neon)
#include <bits/stdc++.h>
using namespace std;
int main() {
int t;
cin >> t;
while (t--) {
int n;
cin >> n;
vector<int> a(n);
for (int& x : a) cin >> x;
cout << n - count(a.begin(), a.end(), *min_element(a.begin(), a.end())) << endl;
}
}
1487B - Круговорот котов в квартире
Идея: adedalic
Разбор
Tutorial is loading...
Решение (adedalic)
fun main() {
repeat(readLine()!!.toInt()) {
var (n, k) = readLine()!!.split(' ').map { it.toInt() }
k--
val floor = n / 2
println((k + (n % 2) * k / floor) % n + 1)
}
}
1487C - Как можно меньше ничьих
Идея: BledDest
Разбор
Tutorial is loading...
Решение (BledDest)
#include<bits/stdc++.h>
using namespace std;
int main()
{
int t;
cin >> t;
for(int i = 0; i < t; i++)
{
int n;
cin >> n;
if(n % 2 == 1)
{
for(int i = 0; i < n; i++)
for(int j = i + 1; j < n; j++)
if(j - i <= n / 2)
cout << 1 << " ";
else
cout << -1 << " ";
cout << endl;
}
else
{
for(int i = 0; i < n; i++)
for(int j = i + 1; j < n; j++)
if(j - i < n / 2)
cout << 1 << " ";
else if(j - i == n / 2)
cout << 0 << " ";
else
cout << -1 << " ";
cout << endl;
}
}
}
Идея: Neon
Разбор
Tutorial is loading...
Решение (Neon)
#include <bits/stdc++.h>
using namespace std;
int main() {
int t;
cin >> t;
while (t--) {
int n;
cin >> n;
int ans = 0;
for (int i = 3; i * i <= 2 * n - 1; i += 2)
++ans;
cout << ans << '\n';
}
}
Идея: BledDest
Разбор
Tutorial is loading...
Решение (BledDest)
#include<bits/stdc++.h>
using namespace std;
int main()
{
vector<int> ns(4);
for(int i = 0; i < 4; i++)
scanf("%d", &ns[i]);
vector<vector<int>> cs(4);
for(int i = 0; i < 4; i++)
{
cs[i].resize(ns[i]);
for(int j = 0; j < ns[i]; j++)
scanf("%d", &cs[i][j]);
}
vector<vector<vector<int>>> bad(3);
for(int i = 0; i < 3; i++)
{
bad[i].resize(ns[i + 1]);
int m;
scanf("%d", &m);
for(int j = 0; j < m; j++)
{
int x, y;
scanf("%d %d", &x, &y);
x--;
y--;
bad[i][y].push_back(x);
}
}
vector<vector<int>> dp(4);
dp[0] = cs[0];
for(int i = 0; i < 3; i++)
{
dp[i + 1].resize(ns[i + 1]);
multiset<int> s;
for(int j = 0; j < ns[i]; j++)
s.insert(dp[i][j]);
for(int j = 0; j < ns[i + 1]; j++)
{
for(auto k : bad[i][j])
s.erase(s.find(dp[i][k]));
if(s.empty())
dp[i + 1][j] = int(4e8 + 43);
else
dp[i + 1][j] = *s.begin() + cs[i + 1][j];
for(auto k : bad[i][j])
s.insert(dp[i][k]);
}
}
int ans = *min_element(dp[3].begin(), dp[3].end());
if(ans > int(4e8))
ans = -1;
cout << ans << endl;
}
Идея: Neon
Разбор
Tutorial is loading...
Решение (Neon)
#include <bits/stdc++.h>
using namespace std;
#define sz(a) int((a).size())
#define forn(i, n) for (int i = 0; i < int(n); ++i)
const int N = 250;
const int M = 28;
const int INF = 1e9;
int dp[2][M * 2 + 1][N][N];
int main() {
string s;
cin >> s;
reverse(s.begin(), s.end());
s += "0";
forn(carry, M * 2 + 1) forn(cp, N) forn(cn, N) dp[0][carry][cp][cn] = INF;
dp[0][M][N - 1][N - 1] = 0;
forn(i, sz(s)) {
forn(carry, M * 2 + 1) forn(cp, N) forn(cn, N) dp[1][carry][cp][cn] = INF;
forn(carry, M * 2 + 1) for (int cp = N - 1; cp >= 0; --cp) for (int cn = N - 1; cn >= 0; --cn) if (dp[0][carry][cp][cn] != INF) {
if (cp > 0) dp[0][carry][cp - 1][cn] = min(dp[0][carry][cp - 1][cn], dp[0][carry][cp][cn]);
if (cn > 0) dp[0][carry][cp][cn - 1] = min(dp[0][carry][cp][cn - 1], dp[0][carry][cp][cn]);
int rcarry = carry - M;
int val = rcarry + cp - cn;
int digit = val % 10;
if (digit < 0) digit += 10;
int ncarry = val / 10;
if (val < 0 && digit != 0) --ncarry;
if (digit == s[i] - '0') dp[1][ncarry + M][cp][cn] = min(dp[1][ncarry + M][cp][cn], dp[0][carry][cp][cn] + cp + cn);
}
swap(dp[0], dp[1]);
}
int ans = INF;
forn(i, N) forn(j, N) ans = min(ans, dp[0][M][i][j]);
cout << ans << endl;
}
Идея: BledDest
Разбор
Tutorial is loading...
Решение (BledDest)
#include<bits/stdc++.h>
using namespace std;
const int MOD = 998244353;
const int N = 402;
int add(int x, int y)
{
x += y;
while(x >= MOD) x -= MOD;
while(x < 0) x += MOD;
return x;
}
int sub(int x, int y)
{
return add(x, -y);
}
int mul(int x, int y)
{
return (x * 1ll * y) % MOD;
}
int c[26];
int dp[2][N][N][3][3];
int sumDp[N][N];
int p1[N][N];
int p2[N][N];
int n;
int main()
{
cin >> n;
for(int i = 0; i < 26; i++)
cin >> c[i];
for(int i = 0; i < 26; i++)
for(int j = 0; j < 26; j++)
for(int k = 0; k < 26; k++)
if(i != k)
{
multiset<int> s = {i, j, k};
dp[1][s.count(0)][s.count(1)][min(2, j)][min(2, k)]++;
}
for(int i = 4; i <= n; i++)
{
for(int j = 0; j < N; j++)
for(int k = 0; k < N; k++)
for(int x = 0; x < 3; x++)
for(int y = 0; y < 3; y++)
{
dp[0][j][k][x][y] = dp[1][j][k][x][y];
dp[1][j][k][x][y] = 0;
}
for(int j = 0; j < N; j++)
for(int k = 0; k < N; k++)
for(int x = 0; x < 3; x++)
for(int y = 0; y < 3; y++)
{
int cur = dp[0][j][k][x][y];
if(cur == 0) continue;
for(int z = 0; z < 3; z++)
{
int& nw = dp[1][j + (z == 0 ? 1 : 0)][k + (z == 1 ? 1 : 0)][y][z];
nw = add(nw, mul(cur, (z == 2 ? 24 : 1) - (z == x ? 1 : 0)));
}
}
}
for(int i = 0; i < N; i++)
for(int j = 0; j < N; j++)
for(int k = 0; k < 3; k++)
for(int l = 0; l < 3; l++)
sumDp[i][j] = add(sumDp[i][j], dp[1][i][j][k][l]);
for(int i = 0; i < N; i++)
{
p1[i][N - 1] = sumDp[i][N - 1];
for(int j = N - 2; j >= 0; j--)
p1[i][j] = add(sumDp[i][j], p1[i][j + 1]);
}
for(int j = 0; j < N; j++)
{
p2[N - 1][j] = p1[N - 1][j];
for(int i = N - 2; i >= 0; i--)
p2[i][j] = add(p1[i][j], p2[i + 1][j]);
}
int ans = p2[0][0];
for(int i = 0; i < 26; i++)
{
for(int j = 0; j < N; j++)
for(int k = c[i] + 1; k < N; k++)
ans = sub(ans, sumDp[k][j]);
}
for(int i = 0; i < 26; i++)
for(int j = 0; j < i; j++)
ans = add(ans, p2[c[i] + 1][c[j] + 1]);
cout << ans << endl;
}
The time complexity of the editorial of problem E seems to be O(n*m*logm), which seems more than 1E10. How does this solution get AC?
It's just $$$O((n+m) \log n)$$$ since, for each consecutive pair of types of dishes we build a data structure for the first type (in $$$O(n \log n)$$$), and for every dish of the second type, remove the forbidden elements ($$$O(m \log n)$$$ over all dishes), query the minimum ($$$O(n \log n)$$$ for all dishes in total), and insert back the removed elements.
Thanks for explanation. i tried implementing it but got WA on test case 19. tried many things but could nt get AC.Tried even generating random inputs and comparing with accepted solution but in vain.. any clues for the test case 19??
https://mirror.codeforces.com/contest/1487/submission/108129435
thanks
Sorry, I'm not familiar with Java. Does the TreeSet structure allow duplicates?
Yes it allows if we add a custom comparator. No issues i will try to generate some more tests and see whats going wrong... thank you
I've uploaded my post-contest stream (where I explain A-E) to Youtube with timestamps: https://youtu.be/bx35l4tx_xk
In problem E, I have a bit of a different solution to the DP optimization. From the previous course, we sort all dp values from low to high. Then for a certain new dish, we want to know the first option in the sorted list that isn't forbidden. First we assume every dish will pick the first option, and we put the option they choose in an array (initially all zeroes). Then go through all bad edges of the first dp option and increment the lowest possible dp option for each bad dish, then do the same for the bad edges of the second option, etc. Then it is simple to calculate the new dp values. This algorithm takes only $$$O(n \cdot log(n) +m)$$$, because it goes through each edge once, and does a sort on the dp values.
My Submission
I have done exactly the same it doesn't seem to work and is giving wrong answer on test case 16.
I have created 3 dp vectors of pairs (strg1,strg2,strg3) which store minimum cost to have till 2nd 3rd and 4th course of meals.
If we can't have a particular meal it's cost is marked as -1.
Before starting to calculate the next dp array we sort the previous dp table and our counter starts from the 1st val which isn't -1.
Then for a particular meal we increment the counter till a compatible meal is found and again reset the value to the minimum for the next meal.
Time complexity is (n*logn +m).
Please help me find my error or a test case which my code fails
Accepted
Sorry for the trouble It is working actually i forgot to check the index of sorted ones i.e. dish[i].second i was checking ith one.
My solution for F:
Supposing $$$m_i=111...1$$$($$$i$$$ digits). And you can think of this problem as: make $$$x=x+m_i/ x-m_i$$$with price $$$i$$$ and let $$$x=0$$$ with minimal price.
Let $$$dp_{y,x}$$$ mean after you plus/minus all $$$m_i (i > y)$$$ the minimal price with value $$$x$$$ now. And we can use
map/unordered_mapand Bigint(I write it myself) for $$$dp_y$$$. Initially $$$dp_{y+1,n}=0$$$For every $$$x$$$ in $$$dp_{y,x}$$$ there are only at most two options for $$$x$$$ in $$$dp_{y-1,x}$$$. Assuming $$$x$$$ is nonpositive those two options $$$x$$$ are $$$x-km_y$$$ and $$$x-(k+1)m_y$$$ where $$$x-km_y$$$ is nonnegative and $$$x-(k+1)m_y$$$ is negative. Other $$$|x-km_y| \geq m_y$$$ mean you can always minus/plus a more $$$m_y$$$ and save much more price.
There seems to be at most $$$2^{50}$$$ different $$$x$$$ in $$$dp_y$$$, but we can see $$$m_i \mod m_{i-1} = 1$$$. It means plus/minus one more $$$m_y$$$ will at most result in $$$1$$$ difference in $$$dp_{y-1}$$$. So there are at most $$$O(|n|)$$$ different $$$x$$$ in $$$dp_y$$$.
Iterate $$$y$$$ from $$$|x|+1$$$ to $$$1$$$ $$$(O(|n|))$$$, enumere $$$x$$$ in $$$dp_y$$$ and update $$$dp_{y-1}$$$ $$$(O(|n|))$$$, with Bigint calculation complexity $$$O(|n|)$$$ and map $$$O(log|n|)$$$, the total complexity as I think is $$$O(|n|^3log|n|)$$$
my code
OMG, I actuallly thought the complexity was $$$O(2 ^ {|n|})$$$ during the contest.
I was too worried to code it. :(
After all, $$$m_i\mod m_{i-1}=1$$$ seems the key to the solution.
What a nice job you did,bro!
Seemingly you claimed that if $$$|x| \geq m_y$$$, $$$m_y$$$ should be in the optimal solution. Why?
Also, could you explain why is there $$$O(|n|)$$$ different $$$x$$$ in $$$\mathrm{dp}_y$$$? I cant see why it is true given $$$m_i \bmod m_{i + 1} = 1$$$.
Well, every $$$m_y$$$ should be used less than $$$10$$$ times (in fact maybe even less), otherwise you can always change $$$10m_y$$$($$$10y$$$digits) into $$$m_{y+1}-m_1$$$($$$y+2$$$ digits). If your $$$|x| \geq m_y$$$ and don't use $$$m_y$$$ to reduce it. Considering $$$\sum_{i=1}^{y-1} 9m_i < \sum_{i=1}^{y-1}10^{i+1} = m_y$$$, Some of $$$m_i(i<y)$$$ must be used at least $$$10$$$ times to make $$$x$$$ become $$$0$$$ and you can always make it better.
I claim that for all $$$x$$$ in $$$dp_y$$$ the value of $$$x \mod m_{y}$$$ are in exactly one intervals $$$[a,b]$$$ with length of $$$O(|n|)$$$. ($$$[a,m_{y}-1] \cup [0,b]$$$ is also seen as an interval in case of $$$\mod m_{y})$$$
Initally $$$x$$$ has only $$$1$$$ possible value. Ok of course.
Since $$$x\pm km_{y}$$$ doesn't change $$$x \mod m_{y}$$$, for all $$$x$$$ in $$$dp_{y-1}$$$ the value of $$$x \mod m_{y}$$$ are in $$$[a,b]$$$ too.
Considering all $$$x$$$ in $$$dp_{y-1}$$$ must satisfy $$$|x|<m_y$$$, the possible value of $$$x$$$ is in only two intervals:$$$[a-m_y,b-m_y] \cup [a,b]$$$.
$$$a-m_y=a-10m_{y-1}-1\equiv a-1 (\mod m_{y-1})$$$. So for all x in $$$dp_{y-1}$$$,$$$x \mod m_{y-1}$$$ is in $$$[a-1,b-1] \cup [a,b] =[a-1,b]$$$, only $$$1$$$ longer than $$$[a,b]$$$. So $$$[a,b]$$$'s length is $$$O(|n|)$$$.
Since that the possible number of different $$$x$$$:$$$[a-m_y,b-m_y] \cup [a,b]$$$ is also $$$O(|n|)$$$.
Thanks for your explanation! This looks plausible.
What does the array dp mean in the solution code? Does dp[0] stands for f and dp[1] stands for g? Obviously the meaning of dp does not directly correspond with the tutorial.
As I say in the last paragraph of the editorial, the third version of dynamic programming ($$$g$$$) can be used not only to calculate the number of strings which violate the constraint on a pair of characters, but also the number of strings which don't violate any constraints and which violate the constraints on one character; so, the only dynamic programming in this solution actually stands for $$$g$$$ (though it stores only two last layers of it to optimize memory usage).
in problem D , i searched it in Wikipedia "a = k(2xy) b = k(x^2 — y^2) c = k(x^2 + y^2)" then i calculated that: x = y + 1. So my idea is using a loop for from 1 to sqrt(n) and check. But it's wrong. Can anyone help me. This is my submission: https://mirror.codeforces.com/contest/1487/submission/107657994
you just need to add cnt by 1 during the loop, because when you can keep running the loop, it means you find one answer for the question, not n/(y*y + (y+1)*(y+1))
For Problem G, is there any explanation for why the optimizations described in the solution work? Why do $$$l$$$ and $$$m$$$ only have 3 states and why do we only need to run DP once? I'm still kind of confused over these.
My English is very poor...so if I make grammar mistakes, please forgive me. TAT
The reason that $$$l$$$ and $$$m$$$ only have 3 states is we only need to know whether the last two characters are the two we fixed. If so, we can choose the rest 25 characters as the next one then update the value of $$$j$$$ or $$$k$$$. If not, we only need to choose the rest 25 characters as the next one, without updating the value of $$$j$$$ or $$$k$$$.
The reason that why do we only need to run DP once is all the characters are essentially the same. No matter which two characters you fix, your DP processes are all the same.
Ah the first part makes sense. I'm still not sure about the second part, mainly that the DP processes are all the same. How can you find the values for each pair of characters given just one DP?
To get the answer, we calculate the number of strings of length $$$n$$$ that don't contain palindromes of odd length greater than $$$1$$$.
Then we iterator all the $$$26$$$ characters and subtract the number of strings that violate the limit of at least one character(suppose this character is $$$c$$$, then the number is $$$\sum_{j=0}^n\sum_{k=limit_c+1}^ndp_{n,j,k,*,*}$$$ ) from the answer.
Then we iterator all the $$$26$$$ characters and add the number of strings that violate the limit of at least two characters(suppose these two characters are $$$c1,c2$$$, then the number is $$$\sum_{j=limit_{c1}+1}^n\sum_{k=limit_{c2}+1}^ndp_{n,j,k,*,*}$$$ ) to the answer. You can think of the whole process as an inclusion-exclusion.
Pythagorean Triples (Problem D)
int a = sqrt(n*2);
if( a%2 == 0)a--;
int ans = a/2;
sqrt() function itself take O(log n) time so your solution is not in O(1) bro
sqrt() function is a single CPU instruction
so it's really O(1)
really ?
proof?
BledDest
Можешь, пожалуйста, объяснить следующий момент в разборе задачи G:
"Чтобы обработать ограничения на количество символов каждого типа, воспользуемся формулой включений-исключений. Так как каждое значение Сi > n / 2, максимум два символа могут нарушить ограничение ...".
Какое ограничение могут нарушить максимум 2 символа? Почему именно 2 символа?
In problem B can anyone tell what are the collision points for n = 7.It is supposed to be collide after n//2 steps but for n = 7 ,collision happened only at pt 3 and 1 and after that it is not colliding.Please explain where m i doing wrong
collision happened at 4 -> 1 -> 5 -> 2 -> ... {7,1},{6,2},{5,3},!{4,5},{3,6},{2,7},!{1,2},{7,3},{6,4},!{5,6},{4,7},{3,1},{2,3} it seems that the collision happened on pt (1+t*(n-1)/2)
In Neon's editorial of problem F, why is this condition met carry>=(carry+cp)/10? Thanks!
Pfft, that solution for B was way too complicated, I came up with much simpler solution. Obviously, the solution is
(1 - n % 2) * (((k - 1) % n) + 1) + (n % 2) * (((((k - 1) % (n * (n / 2))) / (n / 2)) / 2 + (((k - 1) % (n * (n / 2))) % (n / 2)) + ((((k - 1) % (n * (n / 2))) / (n / 2)) % 2) * (n / 2 + 1)) % n + 1)Can any one help me: Why 3n(n-1)/2 mod n = n / 2. I tried to prove it but I think 3n mod n = 0 so 3n(n-1)/2 also 0...
Of course, 3 * n mod n = 0 and that's why 3 * n * (n — 1) mod n = 0. But after dividing 3 * n * (n — 1) by 2, this condition is not necessarily satisfied (for example, with n = 2: 3 * 2 * 1 = 6, 6 mod 2 = 0. But (3 * 2 * 1) / 2 = 3, 3 mod 2 != 0). Also statement 3 * n * (n — 1) / 2 mod n = n / 2 is correct if and only if n is even (if it is odd left part is integer and right is not). proof: 3 * n * (n — 1) / 2 mod n = n / 2 <=> 3 * n * (n — 1) / 2 — n / 2 mod n = 0 <=> (3 * n * n — 4 * n) / 2 mod n = 0 <=> n * (3 * n — 4) / 2 mod n = 0 — this is correct because 3 * n — 4 is even (because n is even) and (3 * n — 4) / 2 is integer.
Yay, your reply is very helpful. I also have another question: is there any ways to find result: n / 2 without proving...
Yes. You can do it in following way: We want to find a number from 0 to n — 1 inclusive such that 3 * n * (n — 1) / 2 mod n = x. 3 * n * (n — 1) / 2 mod n = x <=> 3 * n * (n — 1) / 2 — x mod n = 0 <=> 3 * n * n — 3 * n — 2 * x mod 2 * n = 0. It means (1) that 3 * n + 2 * x mod 2 * n = 0 (because 3 * n * n mod 2 * n = 0, as n is even and 0 mod 2 * n = 0) and (2) 2 * x mod n = 0 (because 3 * n * n — 3 * n mod n = 0 and 0 mod n = 0). It follows from (2) that x = 0 or x = n / 2 (because 0 <= x < n). If x = 0, (1) sometimes is false (for example, if n = 2). If x = n / 2, 3 * n + 2 * x = 4 * n, 4 * n mod 2 * n = 0. So the only solution to this problem is x = n / 2.
If I could upvote more than 100 times, I will do it for your helpful reply :D. Thanks sir
Why solution in B do k-- ??? I cant understand