Codeforces Round 928 (Div. 4) Editorial
source link: https://codeforces.com/blog/entry/126132
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
Codeforces Round 928 (Div. 4) Editorial
5 days ago, # | For Problem-F, I have a bitmask dp solution: 247350477 |
-
I am interested to know how you formed intitution for bitmask dp when it looks like a graph based problem at first.
-
Firstly, I thought if we precalculate answers for all matrixes at the beginning, then we can solve queries in O(n2)O(n2) which equals reading matrix.
But how can we precalculate answers for all matrixes. Like in the editorial, we can separate matrix into 2 sets; which one of them has 25 elements, other's 24. How can we calculate answers for all matrix designs in one set.
And then I reduced problem to a bitmask DP problem. And I found a classicial DP solution:
Try to show possible matrixes as a masks, which black square is 1, else 0. Then f(mask)f(mask) will show answer for maskmask.
We have 2 easy cases:
It is a good matrix (every black square doesn't have 4 diagonal black square) and f(mask)=0f(mask)=0: We can check it in O(bit number of mask)O(bitnumberofmask).
It isn't a good matrix, and suppose we transform k.k. black square to white: f(mask)=min∀k∈maskf(mask⊗2k)+1f(mask)=min∀k∈maskf(mask⊗2k)+1 And our case will has a same complexity as 1. case.
Then we will have 225225 mask for first set, and 224224 for second set. And final complexity will be O((225+224)×25+(T×49))O((225+224)×25+(T×49)) or O(2N22×N/2+T)O(2N22×N/2+T). Nearly 2×1092×109 which is in TL. But it is too close to TL so it can get TLE if your constant is big.
Note: You can fast your solution with magical bitwise operations.
Also sorry for my poor English.
-
5 days ago, # | I tried hard to solve F using bipartite matching but I failed. Does F can't be solved by bipartite matching? I think it can be solved by find minimum vertex cover with good network modeling. Plz help me. |
-
I think F is very difficult to be solved by flow (network modeling).
I tried to find a modeling of minimum cut, but I found that it's difficult to produce by flow that for an illegal black cell, we need only to change one cell's color to make it legal. In other words, for a black cell that is not legal, we need to manipulate at least one other cells to make it legal. The "at least one" operation is difficult for network flows.
But perhaps there is some subtle transformation in this problem that eliminates the "at least" condition. I'm looking forward the subtle way to solve it expectantly.
5 days ago, # | problem f is so bad i cant solve it |
4 days ago, # | There's a much simpler solution for G.
|
-
Well done, I attempted the same DFS traversal, but never thought of changing C to P. What I did instead was to keep a count of P and S during traversal, and set either P or S to 0 once the wall is put. But haven't quite figured out how to make it AC. Although I have the same cntscntscntpcntp comparison :D
-
Could you explain why: when cntscnts = cntpcntp,We should change it to be the same as the parent.
I didn't do this, so I got WA2.But I don't understand why we have to do this.
thank you
I recorded myself live while solving A,B,C,D,E and thinking G. Hope it helps someone: https://www.youtube.com/watch?v=Zr2JbyTwq0A |
-
Bro why you did it in live stream?
4 days ago, # | Why this solution get TLE? https://codeforces.com/contest/1926/submission/247402006 I can't think of a single reason, every operation in loops are constant I solved it other way: https://codeforces.com/contest/1926/submission/247402620 But still curious why first one is TLE |
4 days ago, # | I wrote this solution which just check each line if it has substring of "010" since k>1 that means a square is at least 2*2 if it has a "010" then it is a triangle else is square its an easier approach Solution |
I have a bitmask dp solution for problem F. first assume that B = 1 and W = 0, and change the grid accordingly. Let's say the bit on cell (i, j) is bad iff With that, let's define A mask is valid iff for all x, if x is bad than mask CANNOT have both (x — 1) and (x + 1) BOTH on. otherwise we would have that With some clever preprocessing of the masks, this dp can be achieved with a complexity of O(N∗2N∗3N)O(N∗2N∗3N), with N = 7 and 200 testcases, this is fast enough here's my solution |
4 days ago, # | I solve problem C without precomputing in O(t*log10(n)).LOL 247319547 |
-
I was literally trying to formulate a thing like this but failed on it badly and messed up with my rating. going back to grey again :(
I have a different approach with dp for problem F. First consider the following dp: dp[i][msk1][msk2]. |
4 days ago, # | For problem D, rather than using XOR, I simply added the two numbers and checked to see if they were equal to |
4 days ago, # | The link to G in the tutorial is in russian for some reason. |
have problem with reading problem statement E. wouldn't all cards with number from 1 to n appears? for example 8, it's clearly not odd, it can't be 2 * (any odd number) number, it can't be 3 * (any odd number), it can't be 4 * (any odd number). 8 never appears, thus constraint on k, n is not valid |
4 days ago, # | So is there a polynomial solution for F? I tried modeling with network flow but failed, and I think such approach probably won't work. |
-
Okay, I've got it. Since we know from editorial that at most 4 squares are needed in each parity, we can replace knapsack with 4-sum (1-2-3-sums in fact) with total complexity O(n3)O(n3). Slightly trollish but polynomial
-
Sorry, but this solution is nothing different from the one in the editorial. Your solution requires the fact that "at most 4 squares needed in each parity", however, this won't work for n≥8n≥8. So I had to say that this is not a true polynomial solution. It's indeed O(n⌊n2⌋)O(n⌊n2⌋).
-
Indeed, should have checked it before. Thanks for pointing out.
While researching I found that low frequency set can be approximated, maybe that's the intended polynomial solution.
-
-
code |
4 days ago, # | For F,my submission 247420824, why i add the dfs branch (the //add part),the result become worse. For example,
If I remove the comment symbols in the code and dfs by five cases, I get a result of 7.While following the code inside my link to dfs with three cases gives a result of 6. Besides , What is the problem with the code inside my link and why can't AC. Sorry for my poor English, can anyone help me ? |
-
I found the problem, I forgot to add "return" in this place during dfs
if (check(x, y) == 0) "return" dfs2(u + 1, cnt);
This can lead to otherwise legal points that I still go to enumerate to modify its diagonal, resulting in a large answer. And the more cases of dfs, the more likely it is to lead to a large answer, which is what led to my question above.
How can I do hash collision on this solution?
|
4 days ago, # | Can somebody share the flow networks approach and solution for Problem G. I want to know how maxflow/mincut can find the solution. Thanks in Advance. |
4 days ago, # | I don't get why dp is needed in G. Isn't it simple dfs?
|
-
I was thinking if we can solve G using min-cut.
Basically my idea was to combine all the 'P' to a node 0 in a new_graph and all the 'S' to a node n+1, which are basically acting as the source and sink respectively, and keeping the configuration of the 'C' vertices constant, which are acting as intermediate nodes. There can be multiple edges.
Then we calculate the max-flow, where each edge has a capacity of 1 which will be our final answer. But using Ford-Fulkerson gives O(nm2)O(nm2), thus giving TLE.
Can we use the fact that the capacity of each edge is 1 thus somehow reducing it to linear time ?
-
-
Thanks. It got AC using Dinic's algorithm. After you said faster flow network I googled and found out it takes less time for unit capacity O(M√M)O(M√M).
Sorry, but since I didn't know about it before, I didn't really understand your implementation of it. Did you use the same?
-
-
4 days ago, # | I would like to mention my solution for F. Observation 1: Grid can be divided into 2 independent sets of cells based on whether (i+j) is odd or even, with 25 and 24 cells in each. Considering only black cells, we can brute force all possible flips in O(2^25 * 25). But this is slow. Observation 2: Flipping cells from the grid boundary is not necessarily needed, we will still find an optimal flipping. This reduces our cell count to 13 and 12. And the brute force is fast enough now. |
My solution in C was O(N+t)O(N+t)247266041. If n≤106n≤106 my solution will still work But it contains precomputation too |
4 days ago, # | A very simple solution for B. find the first instance of 1 in the grid. then check if the next cell is 1 and if the bottom cell is 1. if so then its square otherwise triangle. |
4 days ago, # | for problem D i got TLE. I believe its o(n) can someone correct
|
-
Counter
behaves similarly tounordered_map
in C++. It can be TLE hacked wherec[k]
orc[e]
can be O(n)O(n).What you can do is a
random.shuffle(a)
to make the hackers work harder :D-
noooo I didnt get hacked. I got TLE in contest itself.
-
They made the test case that will TLE if you use a
dict
or a similar hash based data type. They created a "hack" before the hacking phase.Try adding a
import random
andrandom.shuffle(a)
and you will see you will get AC (the test case that TLEs python will no longer work).-
ohhh thanks for the reply. Any idea why do they do this on purpose? And how do they achieve this exactly
-
They do this on purpose to make people come up with efficient algorithms that don't rely on hash tables. Of course, in C++ there's ordered
map
.For example, try solving:
Subarray Sums I: https://cses.fi/problemset/task/1660
Subarray Sums II: https://cses.fi/problemset/task/1661
You will be surprised :D
Here's a hack tutorial for Python and you can test it out yourself: https://codeforces.com/blog/entry/98994
You exploit the hash function to create collisions and make any resizing attempts still maintain collisions.
-
-
-
-
-
my c++ version also got TLE
#include <iostream> #include <unordered_map> #include <vector> using namespace std; int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); int t; cin >> t; while (t--) { int n; cin >> n; unordered_map<int, int> counter; vector<int> a(n); for (int i = 0; i < n; ++i) { cin >> a[i]; counter[a[i]]++; } int count = 0; for (int i = 0; i < n; ++i) { int k = 2147483647 - a[i]; if (counter[k] > 0 && counter[a[i]] > 0) { count++; counter[a[i]]--; counter[k]--; } } cout << n - count << "\n"; } return 0; }
-
Did you try using Fast IO? Python's Hash table uses Sip Hash. Not exactly similar to CPP's unordered_map but very strong. IMO hash table is not the cause for TLE.
-
-
Hmm, this is interesting. I didn't come across such behaviour earlier. New learning for me.
-
Try this one: https://cses.fi/problemset/task/1661
They have a test case that purposefully TLEs a Python hashmap and if you switch to a O(nlogn)O(nlogn) solution, with same IO, it passes.
-
-
-
4 days ago, # | As a nooooooooooob,even I can't solve D and E lol Next I will record the results of each of my races. I believe I can be LGM before 2026! |
4 days ago, # | For problem B, I have a solution in which I get the numbers of 1s in the first line the number 1 starts appearing. If the numbers of 1s in the next line that has 1 is different (for example, line 1 has 3 ones, line 2 has 1 one) then it is a triangle, otherwise it is a square. However this solution doesn't work on test case 2 and I've not been able to find any edgecase in my mind that defies this logic: 247338503 |
-
Your description sounds correct, your code doesn't quite do that.
-
Thank you, my code didn't check for the case in which there're lines full of 0s below the shape, and it compared 0 number of 1s to the number of expected 1s to make a square (which was already completed) and flagged it as a triangle because these numbers are different.
Thank you for finding the test case!
-
Amazing work setters!! My Java Binary Trie Solution 247338014 with complexity O(30*N) TLEd on System Test which ideally should not. In contest it showed a runtime of 1091 ms , since it had a buffer of almost 1 sec , so i thought it was feasible. And again no surprise exact same code in C++ passes. 247463968 UPD : Got my AC back :) |
4 days ago, # | Why didn't my rating change ( my rating was 381 before the contest ) even though I solved the first three problems ? |
4 days ago, # | how to solve F in polytime? |
4 days ago, # | This was my first Codeforces contest. Can anyone suggest study materials for dsa. |
4 days ago, # | Can anyone explain this line of the editorial solution of Problem G:Vlad and Trouble at MIT? dp[u][0] = min({tot, dp[u][1] + 1, dp[u][2] + 1}); I can not understand it. Please give some explanation. |
4 days ago, # | I think this Div4 is harder than previous Div4, because problem F and G was very hard for pupil |
4 days ago, # | Could you please explain the approach of D ? |
4 days ago, # | Problem C: Why does it fail on Test #8 ? : Submission include <bits/stdc++.h>using namespace std; int sumDigits(int n) { int sum = 0; while(n > 0) { sum += n%10; n /= 10; } return sum; void solve(vector v, int n, vector ©) { map <int, int> mp; int ans = 0; int p = 0; for(int i = 1; i <= n; i++) { if(i == v[p]) { ans += sumDigits(i); mp[i] = ans; p++; continue; } else ans += sumDigits(i); } for(int i = 0; i < copy.size(); i++) { cout << mp[copy[i]] << endl; } int main() { ios::sync_with_stdio(0); cin.tie(0); int t; cin >> t; int maxN = 0; vector<int> v; while(t--) { int n; cin >> n; maxN = max(maxN, n); v.push_back(n); } vector<int> copy = v; sort(v.begin(), v.end()); solve(v, maxN, copy); return 0; |
3 days ago, # | For Problem-F, we just need to check the cells marked as '@' below:
For the blue part, we need to check these cells:
So we just brute force from 0 to 4095. For the red part, we need to check these cells:
So we just brute force from 0 to 511. Here is my solution: 247559944. |
3 days ago, # | Problem-D,Why does using unordered_map table time out? |
3 days ago, # | How to deal with Problem C if n<=1e18. (Chinese student,Englishi is very poor...) |
-
That means how to deal it with a O(t) solution. I think there is a solution which used math.
-
I don't sure but i think my solution here is O(log(n)) for each query
#include <bits/stdc++.h> using namespace std; #define ll long long ll sumOfDigits(ll n) { if (n < 10) return n * (n + 1) / 2; ll d = log10(n); ll *a = new ll[d+1]; a[0] = 0, a[1] = 45; for (ll i = 2; i <= d; i++) a[i] = a[i-1] * 10 + 45 * ceil(pow(10, i-1)); ll p = ceil(pow(10, d)); ll msd = n / p; return msd * a[d] + (msd * (msd - 1) / 2) * p + msd * (1 + n % p) + sumOfDigits(n % p); } int main() { ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0); int t; cin >> t; while(t--) { ll n; cin >> n; cout << sumOfDigits(n) << "\n"; } return 0; }
-
Thanks for your healping.Last night I solve Problem C with a O(log10 n * t) solution.This is my code:
#include<bits/stdc++.h> using namespace std; #define pii pair<int,int> #define mp(x,y) make_pair(x,y) #define pqg priority_queue<int,vector<int>,greater<int>> #define pql priority_queue<int,vector<int>,less<int>> #define pqg_pii priority_queue<pii,vector<pii>,greater<pii>> #define pql_pii priority_queue<pii,vector<pii>,less<pii>> #define scnaf scanf #define rt register int #define int long long int n,T,a[6],x[6],k[6]; string s; signed main() { // freopen(".in","r",stdin); // freopen(".out","w",stdout); cin>>T; k[0]=45; for(int i=1; i<5; i++) k[i]=k[i-1]*10+45*pow(10,i); cout<<endl; while(T--) { cin>>s; int ans=0; a[0]=a[1]=a[2]=a[3]=a[4]=0; x[0]=x[1]=x[2]=x[3]=x[4]=0; n=s.size(); for(int i=0; i<n; ++i) a[i]=s[i]-'0'; for(int i=1; i<n; ++i) x[i]=x[i-1]+a[i-1]; for(int i=0; i<n/2; ++i) swap(a[i],a[n-i-1]),swap(x[i],x[n-i-1]); if(a[0]!=0) ans=(a[0]+1)*a[0]/2+a[0]*x[0]; for(int i=1; i<n; i++) ans+=a[i]*pow(10,i)*x[i]+k[i-1]*a[i]+a[i]+(a[i]-1)*a[i]*pow(10,i)/2; cout<<ans<<endl; } return 0; }
-
-
3 days ago, # | I wondered if there is a not hard brute-force approach for the problem F |
3 days ago, # | I think problem F can further be optimized by considering only the inner 5x5 square (the same idea, just considering less squares for backtrack). This approach should be more than 10x faster. |
3 days ago, # | For Problem D why my solution is giving TLE CODE-: int t; cin>>t; while(t--){ int n; cin>>n; vector<int> v(n); for(int i = 0; i < n; i++){ cin>>v[i]; } int ans = 0; unordered_map<int, int> mpp; for(int i = 0; i < n; i++){ if(mpp.count(INT_MAX - v[i])){ mpp[INT_MAX - v[i]]--; if(mpp[INT_MAX - v[i]] == 0) mpp.erase(INT_MAX - v[i]); ans++; }else{ mpp[v[i]]++; } } for(auto it : mpp){ ans += (it.second) } cout<<ans<<endl; } |
2 days ago, # | Can anyone tell me why this is giving tle for E i did the same as in the editorial but i used binary search to fing no of elements we can take at each step am i missing something code |
41 hour(s) ago, # | For problem d: for i in range(int(input())): n = int(input()) l = list(map(int,input().split())) my_dict = {} for num in l: if(num not in my_dict): my_dict[num] = 1 else: my_dict[num] += 1 count = 0 for num in l: if(my_dict[num]!=0): count+=1 xor_val = ((1<<31)-1)^num if(xor_val in my_dict and my_dict[xor_val]!=0): my_dict[xor_val]-=1 my_dict[num]-=1 print(count) i am getting tle... how can i optimise it?? |
15 hours ago, # | I found this solution helpful as a beginner programmer. However, I believe attaching a video solution would greatly benefit learners like me who might need a bit more visual guidance |
Recommend
About Joyk
Aggregate valuable and interesting links.
Joyk means Joy of geeK