We hope you enjoyed the contest!
1950A - Stair, Peak, or Neither?
Idea: SlavicG
Tutorial
Tutorial is loading...
Solution
#include <iostream>
void solve() {
int a, b, c;
std::cin >> a >> b >> c;
if(a < b && b < c) std::cout << "STAIR"<< "\n";
else if(a < b && b > c) std::cout << "PEAK"<< "\n";
else std::cout << "NONE" << "\n";
}
int main() {
int tt; std::cin >> tt;
while(tt--)
solve();
}
Idea: flamestorm
Tutorial
Tutorial is loading...
Solution
#include <bits/stdc++.h>
using namespace std;
void solve() {
int n;
cin >> n;
for (int i = 0; i < 2 * n; i++) {
for (int j = 0; j < 2 * n; j++) {
cout << (i / 2 + j / 2 & 1 ? '.' : '#');
}
cout << '\n';
}
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int tt; cin >> tt; for (int i = 1; i <= tt; i++) {solve();}
// solve();
}
Idea: mesanu
Tutorial
Tutorial is loading...
Solution
#include <bits/stdc++.h>
using namespace std;
void solve() {
int h, m; char c;
cin >> h >> c >> m;
string am = (h < 12 ? " AM" : " PM");
h = (h % 12 ? h % 12 : 12);
cout << (h < 10 ? "0" : "") << h << c << (m < 10 ? "0" : "") << m << am << '\n';
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int tt; cin >> tt; for (int i = 1; i <= tt; i++) {solve();}
// solve();
}
1950D - Product of Binary Decimals
Idea: flamestorm
Tutorial
Tutorial is loading...
Solution
#include <bits/stdc++.h>
using namespace std;
const int MAX = 100'007;
const int MOD = 1'000'000'007;
vector<int> binary_decimals;
bool ok(int n) {
if (n == 1) {return true;}
bool ans = false;
for (int i : binary_decimals) {
if (n % i == 0) {
ans |= ok(n / i);
}
}
return ans;
}
void solve() {
int n;
cin >> n;
cout << (ok(n) ? "YES\n" : "NO\n");
}
int main() {
for (int i = 2; i < MAX; i++) {
int curr = i;
bool bad = false;
while (curr) {
if (curr % 10 > 1) {bad = true; break;}
curr /= 10;
}
if (!bad) {binary_decimals.push_back(i);}
}
int tt; cin >> tt; for (int i = 1; i <= tt; i++) {solve();}
// solve();
}
1950E - Nearly Shortest Repeating Substring
Idea: mesanu
Tutorial
Tutorial is loading...
Solution
#include <bits/stdc++.h>
using namespace std;
void solve() {
int n;
cin >> n;
string s;
cin >> s;
for(int i = 1; i <= n; i++)
{
if(n%i == 0)
{
int satisfy = 2;
for(int j = 0; j < i; j++)
{
for(int k = j+i; k < n; k+=i)
{
if(s[k] != s[j])
{
satisfy--;
}
}
}
if(satisfy > 0)
{
cout << i << endl;
return;
}
satisfy = 2;
for(int j = n-i; j < n; j++)
{
for(int k = j-i; k >= 0; k-=i)
{
if(s[k] != s[j])
{
satisfy--;
}
}
}
if(satisfy > 0)
{
cout << i << endl;
return;
}
}
}
}
int32_t main(){
int t = 1;
cin >> t;
while (t--) {
solve();
}
}
Idea: flamestorm
Tutorial
Tutorial is loading...
Solution
#include <bits/stdc++.h>
using namespace std;
void solve() {
int a, b, c;
cin >> a >> b >> c;
if (a + 1 != c) {cout << -1 << '\n'; return;}
if (a + b + c == 1) {cout << 0 << '\n'; return;}
int curr = 1, next = 0, res = 1;
for (int i = 0; i < a + b; i++) {
if (!curr) {
swap(next, curr);
res++;
}
curr--;
next++;
if (i < a) {next++;}
}
cout << res << '\n';
}
int main() {
int tt; cin >> tt; for (int i = 1; i <= tt; i++) {solve();}
// solve();
}
Idea: SlavicG
Tutorial
Tutorial is loading...
Solution
#include "bits/stdc++.h"
using namespace std;
#define all(x) x.begin(),x.end()
void solve() {
int n; cin >> n;
vector<int> s(n), g(n);
vector<string> aa(n), bb(n);
vector<string> vals;
for(int i = 0; i < n; ++i) {
string a, b; cin >> a >> b;
vals.push_back(a);
vals.push_back(b);
aa[i] = a, bb[i] = b;
}
sort(all(vals));
vals.erase(unique(all(vals)), vals.end());
for(int i = 0; i < n; ++i) {
s[i] = lower_bound(all(vals), aa[i]) - vals.begin();
g[i] = lower_bound(all(vals), bb[i]) - vals.begin();
}
vector<vector<int>> dp(1 << n, vector<int>(n, 0));
for(int i = 0; i < n; ++i) dp[1 << i][i] = 1;
for(int mask = 0; mask < (1 << n); ++mask) {
for(int lst = 0; lst < n; ++lst) {
if(!dp[mask][lst]) continue;
for(int i = 0; i < n; ++i) {
if(mask >> i & 1) continue;
if(s[lst] == s[i] || g[lst] == g[i]) {
dp[mask | (1 << i)][i] |= dp[mask][lst];
}
}
}
}
int ans = 0;
for(int mask = 0; mask < (1 << n); ++mask) {
for(int i = 0; i < n; ++i) {
if(dp[mask][i]) {
ans = max(ans, __builtin_popcount(mask));
}
}
}
cout << n - ans << "\n";
}
main() {
int t = 1; cin >> t;
while(t--) {
solve();
}
}
thanks for the fast editorial
although they are all empty :(
They are updated now with solutions
still waiting for G.
search hamiltonian paths
would recommend this blog for problem G: https://codeforces.me/blog/entry/337
in problem E why we are checking strings of length l from either prefix or suffix why it cannot be any substring with length l from middle or anywhere else in the string ?? can someone please answer this
notice this, there can be atmost 1 difference since we can just check both prefix and suffix, we already have two choices, if first doesnt work then check second, if both doesnt work then a high lenght of the string is required
A fun little exercise for G: Shuffling Songs. Consider this code that finds the longest hamiltonian path of a subset of vertices. What is the time complexity of this code? Is it $$$O(N^3 \cdot 2^N)$$$ or $$$O(N^2 \cdot 2^N)$$$ or $$$O(N \cdot 2^N)$$$? (With proper proof/arguments).
It's O(2^n*n^2) because for each bit mask you iterate every possibile pair of songs.
thank u
Problems were very challenging .. liked them even though not solved them but they were good .. + lightning fast editorial
F can be solved in O(1), so why a + b + c <= 3*10^5??
Do you mean O(log(a)) cause I can't figure out an O(1)
Depends on what you count as a primitive operation, but here's an example of a solution that can be interpreted as O(1): 253827308
can you correct the logic in this one , for 14641 i couldn't get the code right for 14641 so i edited it , though it still failed 253823896
__builtin_popcount(n) has a complexity of log(n). As you are calculating __builtin_popcount(a), your code should be considered as O(log(a))
First of all, my code calls
clz
, notpopcount
. Secondly, it can be misleading to think of it as $$$O(\log)$$$. Explicitly looping over the bits is substantially slower because modern processors have special instructions for bothclz
andpopcount
.sorry for the confusion with clz. Interesting, learnt something new, ty
can you please explain what's the logic behind Padding variable ?
I first build a complete binary tree out of nodes of degrees 0 and 2. The last level may be partially filled, and
padding
denotes how many nodes of degree 1 can be inserted immediately above leaves without increasinglevels
. After that, the second phase begins where everyc
insertions of nodes of degree 1 immediately above leaves increase the number of levels by 1.UPD: I thought of this variable name because padding usually comes between content (nodes of degree 2) and border (nodes of degree 0).
but after subtracting padding, what does increase of (c-1)/c mean b/c i understand that it is 1 degree nodes ,can u please explain ??
It's a common way to round the division result up.
ok, thank u
I know it existed, but I didn't find the optimization from $$$\mathcal{O}(a+b+c)$$$ to $$$\mathcal{O}(\log(a))$$$ (or $$$\mathcal{O}(1)$$$) very interesting, and the core idea is the same.
solution you can check this solution for O(1)
bro u used power function is not o(1)
int ha=log2(a);
is logarithmiccan someone please explain why my code fails in task F https://codeforces.me/contest/1950/submission/262901913
'cause it is div4 :)
For this constraint, queue solution is also accepted. Queue Solution (AC)
thanks you for the quick editorial and good round!
Hello I am gokula kannan siva ji
why am i geting downvoted i am gokula kannan siva ji < : (
don't be sad bro, I upvoted
thank you bro i appreciate it :( they are just mad for no reason
Hey! I am solving G using DFS to find the component of largest size. Why is it giving WA on test 5. Please look at my Submission
Detailed approach:
create a graph with vertices as songs from 1 to n. Two vertices are connected if they have a common artist or genre. Using dfs, find the largest component. Is my approach Wrong??
Consider
Is this graph connected? Can you find a way to arrange all vertices in order?
so how to approach this? i read about hamiltonian path! but i didnt get it! please explain
[EDIT: This solution is incorrect, check end of this comment]
I also did with DFS and DSUs. The trick is do DFS from a node and find the length of the longest "path" from each of them. You can do this by returning (max path length + 1) at each node.
You will notice that I'm setting
dfsvis[node] = false;
while exiting the node. This ensures that every path is tried and non-optimal results aren't returned. (Think what if a node that is part of the longest path is visited before we can check for it, that's why we unvisit it)However only this solution will give a TLE when all 16 songs have same genre and writer coz you check every possible path. To counter this, I checked if the max length that I'm getting is the max possible. If it is no point in keeping checking.
Now what is the max possible length? The size of the connected component! I found it using DSU, you can use other methods. To check, at each branch, I add the max length of that branch and the number of visited node and see its it's equal to the size of the connected component.
Submission: 253849577
[HACKED]
EDIT: This submission has been hacked and I discovered that my code has n! worst case time complexity.
Let's suppose vertex a and b both have first string(genre) same as first string of c then we can arrange like a-b-c-d-e-f-g.
consider other case like a,d both have second string(writer) same as second string of c then we can arrange like b-c-a-d-e-f-g.
so trying all possible case i guess we always find some arrangement
You don't need to suppose anything. The graph I shared explicitly means that there is nothing common between vertex $$$a$$$ and any other vertex except vertex $$$d$$$. How would you find an arrangement then? Hint : It's not possible.
But if you stick to your strategy of finding maximal connected component size, you'd get an incorrect answer.
This isn't a good counter-example since this graph cannot exist (
a
must have an edge with at least one ofc
/e
, orc
must have an edge toe
). Add an edge betweenc
ande
, and that suffices for a graph with no Hamiltonian path under the constraints of this problem.Fair enough. The OP had an impression that their algorithm must be true for general graphs as well, hence I randomly constructed a counter example.
But you're correct, given the context of this problem, there should be an edge between
c
ande
. Fixed.what would be the rating for problem E? just wondering
around 1300
realistically 1200-1300, Clist says its 1500:
https://clist.by/problems/
Maybe 1200-1300
maybe around 1200-1300, maximum ~1500
thanks for the solutions!
I loved the problem G. The constraints were a subtle hint already but I tried to build a graph between connected components (an edge between song $$$i$$$ and $$$j$$$ iff genre or artist is same). After looking at the graph, it was pretty evident it is a Hamiltonian Path bitmask DP. Figuring it out was very fun! Great problemset overall for Div4 users.
why is my submission for E wrong tho i tested them all? ;-; here's my submission: 253815920
try case 1 2 aa
Can anyone explain the reasoning behind the Time complexity Anaylsis given for D? I didnt get the idea or how those cubic/quantic equations got formed.
can someone explain solution to problem E
brute force check for every factor of n
Notice that the answer can only be a divisor of n, so we have to calculate all the divisors.
Now Try to form a new string (formed by concatenation of a prefix of s), Example
s= "abba"
and divisord= 2
;prefix = "ab"
. The new formed string will be"abab"
. (do the same thing with suffix ="ba"
) Now compare the 2 formed strings with s, if we find more than 1 difference we move on to the next divisor, else, d is our answer.Hope this helps.
thanks got it now
why do we only need to consider concatenation of a prefix or suffix?
why do we ignore a potential substring in the center?
sorry! i just started CF
u can take whatever 2 substrings you want but they should not be overlapping
No. (let d be a divisor of n) The strings must start from an index divisible by d and with length d .
this comment explains in more detail
i supposed that the lenght of substring is a divisor of n
One straightforward optimization can be that once
i
crossesn/2
, you can be sure that the answer isn
.I was a little disappointed with the pretest in task G. It was clearly my fault for underestimating the problem. But I was disappointed that out of 38 pretests, not a single one made simple DFS got Time Limit Exceeded in a task where you intended dp using bitfield as the correct answer.
253766687 << Yes, here are my code with dumb approach, and it passed during competition, and hacked immediately I showed this code to other ones.
Explain why it is impossible to find a component in G with the maximum number of vertices. Essentially, vertices have two types of edges, those connected by author and those connected by genre. If there are > 2 edges at a vertex, then some vertices will form a cycle, where the order is no longer important.
Counter Example
For problem D why cant we just factorize the given number and if the prime factorization contains any digit which are not binary decimal then we will multiply them together lets call it as Product and the numbers which are binary decimal we will leave them as it is. Now if the Product is binary decimal then answer is yes else no ?
if the number is already a binary decimal we will simply return yes
Consider $$$12321 = 3^2\cdot 37^2$$$.
Yeah, it quickly becomes slow if n is bigger than 10^5
I've also done it like that. First prime factorization, and if some primes are not "binary" ones then just brute force it to check if there is a way to multiply them to obtain the binary number. Prime factorization is O(sqrt(n)) and there are at most 6 primes to brute force under 100000.
but this method is giving error on test 2 https://codeforces.me/contest/1950/submission/253788629 here is my solution
Instead of this, erase all binary prime factors and pass the remaining primes to the recursive function with two nested for loops, erase both elements if they multiply to a binary number and do a recursive call on remaining primes. If no elements are left in the primes vector then binary multiplies were found. here's my solution https://codeforces.me/contest/1950/submission/253817219
Got it. Thank You
Can someone please try and hack my E solution. Submission Link
My solutions to problems A
O(1)
My solutions to problems B
O((n * 2) ^ 2) In this problem it was possible to notice that when numbers (i/2) and (j/2) that they had to be of the same parity
My solutions to problems C
This code can be considered in O(1) complexity. I break this line that is given for hours and minutes if the time is on the clock less than 12 or equal to 24, then it will always be AM in other cases PM. And then look at the clock
My solutions to problems D
My logic consisted of creating an array that would store all binary decimal numbers. 1. I considered if the number consists only of the digits 1 and 0 then if it consisted it displayed "YES" If not then I took the number n and divided it by all binary numbers, if the cycle cannot divide anymore then the answer is NO, otherwise if it came to the cycle n == 1 then the answer is YES
My solutions to problems E
Let's note that the length of the string k — can only be a divisor of n — the size of the string. In my logic I went by the size that it might be. Then I took cycle 2 which one might say created substrings from i to i + d i — where we are d is the divisor, which we consider to be the length . 3 in a loop I simply checked whether the string matches the condition. I remind you of the condition “Find the length of the shortest string k, such that several (possibly one) copies of k can be concatenated together to form a string the same length as s, and there is at most one different character". Complexity of the algorithm that is implemented sqrt(n) * log(n) * n
F sadly I didn’t solve it, but I had the logic for creating a binary tree, I just didn’t have time to implement it))
My solutions to problems G
In this problem it is more difficult to implement dp than to come up with logic. In this problem you just need to go through all the permutations.
Even the authors gave hints that this is due to permutations. Problem limits
1 <= n <= 16
2^n < 2^16
^ — degree
Help Anyone
How can this solution for D have tle,its constant time
💀
And she's buying a stairway to Heaven ....
253803810 Can someone help me why this code for F doesn't work.. My logic was that if c=a+1, then answer is possible... So first try to find the minimum height of the binary tree that could be made with a : it will turn out to be ceil(log2(a))+(ceil(log2(a))==floor(log2(a))). Now to maintain the same no of leaf nodes c, for each of the leaf node in the above binary tree formed with a add a single child to each of the leaf...so basically for every leaf node filled at the ith level of height, the next addition will increase the height by one after all leaf in that level is given a child...
this seems to be right but why doesnt my solution work? please help me
edit i solved it...it was just a small issue...instead of dividing it by no of leaf node for this tree, i divided it by no of leaf node of a complete graph... answer (O(1) solution): 253841056
can someone explain me this approach for problem d ? 253830700
bitset<5>(i).to_string()
is equivilant tobin(i)[2:]
in pythonit returns the binary of i as a string then we use stoi (string to integer) to turn it back to an integer so we can divide with it. i used something like that in my code 253793921
In solution of E why are we only checking for prefix or sufix of length l and not and string of length from the middlee?
because atmost 1 char can be different, so if the string is valid we can clearly see that the repeating substring completely matches with the characters of S in either a prefix or suffix or both
Thankss!
F can be solved in O(1) if you know the property of complete binary trees (number of nodes at each level increases by a factor of 2) and a little bit of maths.
Indeed, here is a solution. https://codeforces.me/contest/1950/submission/253859143
253824980
WHY IS THIS WRONG QUES 4
https://codeforces.me/contest/1950/submission/253824980
You only considered good numbers divisible by 11 and 10, while not all of them have that attribute.
An example of such good numbers, and very possibly the one caused you a WA, is $$$10201$$$ ($$$101^2$$$).
ok thanku so much,will u share your soln plz
https://codeforces.me/contest/1950/submission/253868766
thanks for very fast editorial.
Why didnt Dp worked for the solution D. Its shows TLE. Here is my solution : https://codeforces.me/contest/1950/submission/253751070. PLEASE HELP
there are no constraints on n over all test cases.
after knowing that c == a+1 in F the problem became very easy and solved it in 3 lines submission. the leaves are what bothered me when solving it in the first place
253841056
My solution in O(1) using maths...
I believe on question E, instead of trying for all n, we can first compute the divisors in O(sqrt(n)) with the following: go until i * i <= n and, if n % i == 0, add to the divisors array not only i, but also n / i.
2nd question was very bad question.I hate such type of questions
boo hoo. grow up.
"Grow up"? You unironically have Andrew Tate as your profile picture.
so?
How can we solve G using DSU, basically find size of largest component ?
finding biggest component wont work!
look at this
Can anyone share the solution for D by DP?
253844267
Thank you so much for answering my question fast during the contest (I indeed am very bad at reading) and for providing very high quality problems (I only did C D F but they were insanely interesting).
Another weak pretests day? What is it with codeforces and weak pretests.... (problem E)
Prb-E, Can someone tell time complexity of my solution, my understanding says it's same as author(All numbers at most 10^5 have at most 128 divisors, so this will take ∼128⋅10^5operations, which is fast enough), but I am missing something, https://codeforces.me/contest/1950/submission/253828002
nvm, my assumption was wrong
.
Adding my live coding + commentary here: https://www.youtube.com/watch?v=kQOWiTvgah0&ab_channel=DecipherAlgorithmswithSaptarshi
I'd be glad if somebody finds it beneficial!
Hi, all why my solution G will WA 5? https://codeforces.me/contest/1950/submission/253786544 it also uses bitmask, and I think the order doesn't matter. Thanks for your help!
Oh, I find a example for WA 5: 7 a b c b c d c e f e f g z d
answer should be 1 not 0
Is it possible to solve the problem D using sieve? I'm trying to factorize the primes and then check if I can make some pairs decimal digits
Here is a simpler solution for D : https://codeforces.me/contest/1950/submission/253868766 I thought all possible combinations of 0 & 1 less than 1e5 from which dividing the number and checking if it is divisible by these numbers the answer is okay or not. Also I divided in descending order other wise number like 1001 will cause problem as it will be divided by 11 and leave some number which is not 1. I hope it helps.
i just want to know that for e question,i submitted my code in c++17 and it got wrong answer on test2,then after contest i checked that test and it was giving right answer on my visualstudiocode compiler and then i submitted that same code in c++20 and it got accepted,now i want to know why is it so and am i responsible for this mistake of choosing compiler or is it a error from codeforces;s side
Here is a simpler solution for D : https://codeforces.me/contest/1950/submission/253868766 I thought all possible combinations of 0 & 1 less than 1e5 from which dividing the number and checking if it is divisible by these numbers the answer is okay or not. Also I divided in descending order other wise number like 1001 will cause problem as it will be divided by 11 and leave some number which is not 1. I hope it helps.
Problem G was great
tourist getting WA1 on A is really funny to me for some reason
Wrote G for 80 minutes, 3KB of non-template code, only to find I went in the wrong direction. I tried to build a bipartite,one side is Genre and the other is Writer, and check for a Euler path, but it doesn't work on example 4 When can I AK Div4......
I am newbie to competitive programming. I appeared for this contest and solved 3 problems (yay, albeit with a lot of trial error). In the contest announcement page, it showed that it was rated for participants with ratings <= 1400, so it should have been rated for me. But I don't see that being reflected on my profile page under contests. I don't know what happened. I would be glad if anyone could clear up my confusion.
It would be updated once the open hacking phase ends.
Thank you for the clarification!
After every contest there is an open hacking phase where participants try and hack each other. Only after that the system will start updating ratings . In general it takes 24 hours to update ratings .
But for div 4 rounds it might take more than that
(found)
Is my intuition for G correct, because i am getting wrong answer in test 5, testcase 168. approach is to create a graph, and each category of artists and genre represent an edge between two adjacent nodes, ie.if two nodes have same genre or same artist then there will be edge between them. so after we create a graph we can just find the size of largest connected component and print n-c.(n is total number of nodes)
No, being connected doesn't mean that you can make a simple path that visits all nodes.
can you explain why that might be the case?.Because what i am thinking is, there will always exist a valid simple path in which we can arrange the elements of that particular cc.
This is the simplest counterexample I can think of:
which can be created with this input: https://ideone.com/Lvl1xi
thank you very much.:)
how did you solve this question?
Bitmask DP is probably the simplest, for example if you do top-down DP then you can set $$$dp[i][bitmask]$$$ = maximum length of the path you can further advance when you visited vertices in $$$bitmask$$$ and you're currently at vertex $$$i$$$, then it is $$$max(dp[j][bitmask | (1 \lt \lt j)])+1$$$ where $$$i$$$ and $$$j$$$ are connected by an edge.
really nice explination. I worked this problem for a long time, but got wrong for the same reason
It is not necessary that if a component is connected , then you can get an ordering for each vertex in that component following the rule for adjacent songs.
So, instead of size of component , we need to find the longest path in each component.
That gives TLE
ohk got it. thanks.
Can anybody help me in figuring out where my solution is wrong for "1950D — Product of Binary Decimals"
https://codeforces.me/contest/1950/submission/253812424
it would be great help!! thanks
I just read through your code, consider trying to get the case 1210 = 11*11*10 to return print YES correctly.
name of problem D was a hint about its tag.
?
it was a troll. (DP : dynamic programming) tag of problem D.
Just 1 char from AC :sob:
Wa test 2: https://codeforces.me/contest/1950/submission/253816793
Accepted: https://codeforces.me/contest/1950/submission/253892875
Ive seen many solutions for G problem using dp + bitmask. Could someone explain why only using bitmask and trying to take all the vertices you can doesnt work? Here my solution . I just used bitmask + bfs but got wa on test 5
How do you find the optimal way to reorder the elements?
when i don't add the condition (c ==a+1), can anyone tell me the testcase where this code fails?
Can anybody explain how this code gets AC? https://codeforces.me/contest/1950/submission/253676853
He did a brute force and store all the binary decimals till 10^5 size, its genius, I would have never thought of it...
I mean, why is it correct? Is it possible to prove that this solution is correct?
find all the binary decimals till 10^5 is easy, you jut have to do the combination of 0 and 1 , and then just check with the number to see if it is divisible by our stored numbers ,
I've done something similar 253775386.
Binary Decimal is a number with only $$$1$$$ or $$$0$$$ in its decimal notation.
So, it is quite intuitive think about all possible binary decimals.
For length $$$1$$$ -> $$$1$$$ $$$\newline$$$ For length $$$2$$$ -> $$$10, 01$$$ $$$\newline$$$ For length $$$3$$$ -> $$$100, 101, 110, 111$$$ $$$\newline$$$ For length $$$4$$$ -> $$$1000, 1001, 1010, 1011, 1100, 1101, 1110, 1111$$$ $$$\newline$$$ For length $$$5$$$ -> $$$10000, 10001, 10010, 10011, 10100, 10101, 10110, 10111,$$$ $$$\newline$$$ $$$11000, 11001, 11010, 11011, 11100, 11101, 11110, 11111$$$ $$$\newline$$$ For length $$$6$$$ -> $$$100000$$$ since $$$n \leq 10^5$$$ $$$\newline$$$
Now, for a given $$$n$$$ to be product of binary decimals, either it is one of the above mentioned numbers or it is a product of $$$2$$$ or more above mentioned binary decimal numbers.
So, we can just recursively check whether it is divisible by any of these above mentioned numbers very easily.
Guys, they wanted a proof, not a step-by-step implementation guidance meant for a toddler...
For the OP: At least until $$$10^5$$$ size, I am observing that for every two distinct coprime binary decimals, their sets of prime divisors also don't intersect. I believe that to cause an unexpected division to fail this kind of solutions, the former condition must not hold.
(This is by far just my observation and intuition, so take it with a grain of salt)
you only need 10, 11, 100, 101, 110, 111 — all the factors below the sqrt(10^5)
Suppose you can write $$$n$$$ as a product of binary decimals, say $$$a_1, a_2 \cdots a_n$$$ (in increasing order). Now when you delete $$$a_n$$$, the rest are still guaranteed to be binary decimals. However, if you follow another strategy, say like dividing by a smaller number first, some $$$a_i$$$ may no longer be a binary decimal
Edit: nvm, this isn't good enough
Okay, I believe I found a counterexample, suppose we have
$$$1001 \times 1001$$$, now the submission would first delete $$$11 * 1001$$$ = $$$11011$$$, and the remaining factor would be $$$91$$$, so it would be $$$NO$$$ instead of $$$YES$$$, the counterexample is $$$1002001$$$, and I can't really find a smaller one
WOW thanks! I suppose there was a reason I couldn't prove that solution for 2 hours.
Waiting for the tutorial of G...
I want to use DSU to solve G but failed ,who could tell me why,I want to find the biggest set f[k] and return n-size[k] thank you
A test like this would fail you:
It's clear that this graph is connected, but the answer would be
1
rather than0
.I also got help from the graph, but I was looking for the length of the longest path in it Can you tell me the reason for WA 3 of this code: https://codeforces.me/contest/1950/submission/253975967
You are doing the DFS wrong if you want to find the longest path:
vis[a]
must be unset at the end ofdfs()
function, otherwise it would skip a lot of paths, possibly the longest included.Despite the approach of finding longest path was correct, however, a naive/exhaustive DFS will be inefficient with $$$n \le 16$$$ — as the complexity for the number of any paths in a graph would be $$$\mathcal{O}(n!)$$$, so even at the most optimistic scenario, you would encounter failure at test #44 anyway.
thanks a lot
thanku bro
Can anybody tell what's wrong with (G)this submission, I am getting WA on test case 3 , can't find the mistake
I am getting same error on test case 3 for 150th case my solution
but when I use max function it works?
A better solution: Was 2 min late for the submission in the contest...
O(logn) solution for problem f
Can anyone help me with this solution, how is this different from the one in tutorial?
https://codeforces.me/contest/1950/submission/253833340
why did you assume it's a monotonic function you have too check for all factors and choose the min one
Thanks for the catch :)
can't g be solved by optimizing the code for finding the longest path in a graph problem
The length that can be filled does not satisfy monotonic conditions, so binary search cannot be used
yeah but i meant can we add some conditions in the dfs code only so that we don't get tle in tc 33
oh sorry, i reply wrong place, by the way i encountered the same problem as you in the competition, and the maximum complexity of dfs is n! And 16!>= 2e11
thanks for super duper fast editorial MikeMirzayanov !
thanks for the greatest platform ever Codeforces and also Polygon <33
thanks for super duper fast editorial MikeMirzayanov !
thanks for the greatest platform ever Codeforces and also Polygon <33
thanks for super duper fast editorial MikeMirzayanov !
thanks for the greatest platform ever Codeforces and also Polygon <33
thanks for super duper fast editorial MikeMirzayanov !
thanks for the greatest platform ever Codeforces and also Polygon <33
thanks for super duper fast editorial MikeMirzayanov !
thanks for the greatest platform ever Codeforces and also Polygon <33
thanks for super duper fast editorial MikeMirzayanov !
thanks for the greatest platform ever Codeforces and also Polygon <33
thanks for super duper fast editorial MikeMirzayanov !
thanks for the greatest platform ever Codeforces and also Polygon <33
thanks for super duper fast editorial MikeMirzayanov !
thanks for the greatest platform ever Codeforces and also Polygon <33
thanks for super duper fast editorial MikeMirzayanov !
thanks for the greatest platform ever Codeforces and also Polygon <33
thanks for super duper fast editorial MikeMirzayanov !
thanks for the greatest platform ever Codeforces and also Polygon <33
thanks for super duper fast editorial MikeMirzayanov !
thanks for the greatest platform ever Codeforces and also Polygon <33
thanks for super duper fast editorial MikeMirzayanov !
thanks for the greatest platform ever Codeforces and also Polygon <33
thanks for super duper fast editorial MikeMirzayanov !
thanks for the greatest platform ever Codeforces and also Polygon <33
thanks for super duper fast editorial MikeMirzayanov !
thanks for the greatest platform ever Codeforces and also Polygon <33
thanks for super duper fast editorial MikeMirzayanov !
thanks for the greatest platform ever Codeforces and also Polygon <33
thanks for super duper fast editorial MikeMirzayanov !
thanks for the greatest platform ever Codeforces and also Polygon <33
thanks for super duper fast editorial MikeMirzayanov !
thanks for the greatest platform ever Codeforces and also Polygon <33
thanks for super duper fast editorial MikeMirzayanov !
thanks for the greatest platform ever Codeforces and also Polygon <33
thanks for super duper fast editorial MikeMirzayanov !
thanks for the greatest platform ever Codeforces and also Polygon <33
thanks for super duper fast editorial MikeMirzayanov !
thanks for the greatest platform ever Codeforces and also Polygon <33
thanks for super duper fast editorial MikeMirzayanov !
thanks for the greatest platform ever Codeforces and also Polygon <33
thanks for super duper fast editorial MikeMirzayanov !
thanks for the greatest platform ever Codeforces and also Polygon <33
thanks for super duper fast editorial MikeMirzayanov !
thanks for the greatest platform ever Codeforces and also Polygon <33
thanks for super duper fast editorial MikeMirzayanov !
thanks for the greatest platform ever Codeforces and also Polygon <33
thanks for super duper fast editorial MikeMirzayanov !
thanks for the greatest platform ever Codeforces and also Polygon <33
thanks for super duper fast editorial MikeMirzayanov !
thanks for the greatest platform ever Codeforces and also Polygon <33
thanks for super duper fast editorial MikeMirzayanov !
thanks for the greatest platform ever Codeforces and also Polygon <33
thanks for super duper fast editorial MikeMirzayanov !
thanks for the greatest platform ever Codeforces and also Polygon <33
thanks for super duper fast editorial MikeMirzayanov !
thanks for the greatest platform ever Codeforces and also Polygon <33
thanks for super duper fast editorial MikeMirzayanov !
thanks for the greatest platform ever Codeforces and also Polygon <33
thanks for super duper fast editorial MikeMirzayanov !
thanks for the greatest platform ever Codeforces and also Polygon <33
thanks for super duper fast editorial MikeMirzayanov !
thanks for the greatest platform ever Codeforces and also Polygon <33
thanks for super duper fast editorial MikeMirzayanov !
thanks for the greatest platform ever Codeforces and also Polygon <33
thanks for super duper fast editorial MikeMirzayanov !
thanks for the greatest platform ever Codeforces and also Polygon <33
thanks for super duper fast editorial MikeMirzayanov !
thanks for the greatest platform ever Codeforces and also Polygon <33
thanks for super duper fast editorial MikeMirzayanov !
thanks for the greatest platform ever Codeforces and also Polygon <33
thanks for super duper fast editorial MikeMirzayanov !
thanks for the greatest platform ever Codeforces and also Polygon <33
thanks for super duper fast editorial MikeMirzayanov !
thanks for the greatest platform ever Codeforces and also Polygon <33
thanks for super duper fast editorial MikeMirzayanov !
thanks for the greatest platform ever Codeforces and also Polygon <33
thanks for super duper fast editorial MikeMirzayanov !
thanks for the greatest platform ever Codeforces and also Polygon <33
thanks for super duper fast editorial MikeMirzayanov !
thanks for the greatest platform ever Codeforces and also Polygon <33
thanks for super duper fast editorial MikeMirzayanov !
thanks for the greatest platform ever Codeforces and also Polygon <33
thanks for super duper fast editorial MikeMirzayanov !
thanks for the greatest platform ever Codeforces and also Polygon <33
thanks for super duper fast editorial MikeMirzayanov !
thanks for the greatest platform ever Codeforces and also Polygon <33
thanks for super duper fast editorial MikeMirzayanov !
thanks for the greatest platform ever Codeforces and also Polygon <33
thanks for super duper fast editorial MikeMirzayanov !
thanks for the greatest platform ever Codeforces and also Polygon <33
thanks for super duper fast editorial MikeMirzayanov !
thanks for the greatest platform ever Codeforces and also Polygon <33
thanks for super duper fast editorial MikeMirzayanov !
thanks for the greatest platform ever Codeforces and also Polygon <33
thanks for super duper fast editorial MikeMirzayanov !
thanks for the greatest platform ever Codeforces and also Polygon <33
thanks for super duper fast editorial MikeMirzayanov !
thanks for the greatest platform ever Codeforces and also Polygon <33
thanks for super duper fast editorial MikeMirzayanov !
thanks for the greatest platform ever Codeforces and also Polygon <33
thanks for super duper fast editorial MikeMirzayanov !
thanks for the greatest platform ever Codeforces and also Polygon <33
thanks for super duper fast editorial MikeMirzayanov !
thanks for the greatest platform ever Codeforces and also Polygon <33
thanks for super duper fast editorial MikeMirzayanov !
thanks for the greatest platform ever Codeforces and also Polygon <33
thanks for super duper fast editorial MikeMirzayanov !
thanks for the greatest platform ever Codeforces and also Polygon <33
thanks for super duper fast editorial MikeMirzayanov !
thanks for the greatest platform ever Codeforces and also Polygon <33
thanks for super duper fast editorial MikeMirzayanov !
thanks for the greatest platform ever Codeforces and also Polygon <33
thanks for super duper fast editorial MikeMirzayanov !
thanks for the greatest platform ever Codeforces and also Polygon <33
thanks for super duper fast editorial MikeMirzayanov !
thanks for the greatest platform ever Codeforces and also Polygon <33
thanks for super duper fast editorial MikeMirzayanov !
thanks for the greatest platform ever Codeforces and also Polygon <33
thanks for super duper fast editorial MikeMirzayanov !
thanks for the greatest platform ever Codeforces and also Polygon <33
thanks for super duper fast editorial MikeMirzayanov !
thanks for the greatest platform ever Codeforces and also Polygon <33
thanks for super duper fast editorial MikeMirzayanov !
thanks for the greatest platform ever Codeforces and also Polygon <33
thanks for super duper fast editorial MikeMirzayanov !
thanks for the greatest platform ever Codeforces and also Polygon <33
thanks for super duper fast editorial MikeMirzayanov !
thanks for the greatest platform ever Codeforces and also Polygon <33
thanks for super duper fast editorial MikeMirzayanov !
thanks for the greatest platform ever Codeforces and also Polygon <33
thanks for super duper fast editorial MikeMirzayanov !
thanks for the greatest platform ever Codeforces and also Polygon <33
thanks for super duper fast editorial MikeMirzayanov !
thanks for the greatest platform ever Codeforces and also Polygon <33
thanks for super duper fast editorial MikeMirzayanov !
thanks for the greatest platform ever Codeforces and also Polygon <33
thanks for super duper fast editorial MikeMirzayanov !
thanks for the greatest platform ever Codeforces and also Polygon <33
thanks for super duper fast editorial MikeMirzayanov !
thanks for the greatest platform ever Codeforces and also Polygon <33
thanks for super duper fast editorial MikeMirzayanov !
thanks for the greatest platform ever Codeforces and also Polygon <33
thanks for super duper fast editorial MikeMirzayanov !
thanks for the greatest platform ever Codeforces and also Polygon <33
thanks for super duper fast editorial MikeMirzayanov !
thanks for the greatest platform ever Codeforces and also Polygon <33
thanks for super duper fast editorial MikeMirzayanov !
thanks for the greatest platform ever Codeforces and also Polygon <33
thanks for super duper fast editorial MikeMirzayanov !
thanks for the greatest platform ever Codeforces and also Polygon <33
thanks for super duper fast editorial MikeMirzayanov !
thanks for the greatest platform ever Codeforces and also Polygon <33
thanks for super duper fast editorial MikeMirzayanov !
thanks for the greatest platform ever Codeforces and also Polygon <33
thanks for super duper fast editorial MikeMirzayanov !
thanks for the greatest platform ever Codeforces and also Polygon <33
thanks for super duper fast editorial MikeMirzayanov !
thanks for the greatest platform ever Codeforces and also Polygon <33
thanks for super duper fast editorial MikeMirzayanov !
thanks for the greatest platform ever Codeforces and also Polygon <33
thanks for super duper fast editorial MikeMirzayanov !
thanks for the greatest platform ever Codeforces and also Polygon <33
thanks for super duper fast editorial MikeMirzayanov !
thanks for the greatest platform ever Codeforces and also Polygon <33
thanks for super duper fast editorial MikeMirzayanov !
thanks for the greatest platform ever Codeforces and also Polygon <33
thanks for super duper fast editorial MikeMirzayanov !
thanks for the greatest platform ever Codeforces and also Polygon <33
thanks for super duper fast editorial MikeMirzayanov !
thanks for the greatest platform ever Codeforces and also Polygon <33
thanks for super duper fast editorial MikeMirzayanov !
thanks for the greatest platform ever Codeforces and also Polygon <33
thanks for super duper fast editorial MikeMirzayanov !
thanks for the greatest platform ever Codeforces and also Polygon <33
thanks for super duper fast editorial MikeMirzayanov !
thanks for the greatest platform ever Codeforces and also Polygon <33
thanks for super duper fast editorial MikeMirzayanov !
thanks for the greatest platform ever Codeforces and also Polygon <33
thanks for super duper fast editorial MikeMirzayanov !
thanks for the greatest platform ever Codeforces and also Polygon <33
thanks for super duper fast editorial MikeMirzayanov !
thanks for the greatest platform ever Codeforces and also Polygon <33
thanks for super duper fast editorial MikeMirzayanov !
thanks for the greatest platform ever Codeforces and also Polygon <33
thanks for super duper fast editorial MikeMirzayanov !
thanks for the greatest platform ever Codeforces and also Polygon <33
thanks for super duper fast editorial MikeMirzayanov !
thanks for the greatest platform ever Codeforces and also Polygon <33
thanks for super duper fast editorial MikeMirzayanov !
thanks for the greatest platform ever Codeforces and also Polygon <33
thanks for super duper fast editorial MikeMirzayanov !
thanks for the greatest platform ever Codeforces and also Polygon <33
thanks for super duper fast editorial MikeMirzayanov !
thanks for the greatest platform ever Codeforces and also Polygon <33
thanks for super duper fast editorial MikeMirzayanov !
thanks for the greatest platform ever Codeforces and also Polygon <33
thanks for super duper fast editorial MikeMirzayanov !
thanks for the greatest platform ever Codeforces and also Polygon <33
thanks for super duper fast editorial MikeMirzayanov !
thanks for the greatest platform ever Codeforces and also Polygon <33
thanks for super duper fast editorial MikeMirzayanov !
thanks for the greatest platform ever Codeforces and also Polygon <33
thanks for super duper fast editorial MikeMirzayanov !
thanks for the greatest platform ever Codeforces and also Polygon <33
thanks for super duper fast editorial MikeMirzayanov !
thanks for the greatest platform ever Codeforces and also Polygon <33
thanks for super duper fast editorial MikeMirzayanov !
thanks for the greatest platform ever Codeforces and also Polygon <33
thanks for super duper fast editorial MikeMirzayanov !
thanks for the greatest platform ever Codeforces and also Polygon <33
thanks for super duper fast editorial MikeMirzayanov !
thanks for the greatest platform ever Codeforces and also Polygon <33
thanks for super duper fast editorial MikeMirzayanov !
thanks for the greatest platform ever Codeforces and also Polygon <33
thanks for super duper fast editorial MikeMirzayanov !
thanks for the greatest platform ever Codeforces and also Polygon <33
thanks for super duper fast editorial MikeMirzayanov !
thanks for the greatest platform ever Codeforces and also Polygon <33
thanks for super duper fast editorial MikeMirzayanov !
thanks for the greatest platform ever Codeforces and also Polygon <33
thanks for super duper fast editorial MikeMirzayanov !
thanks for the greatest platform ever Codeforces and also Polygon <33
thanks for super duper fast editorial MikeMirzayanov !
thanks for the greatest platform ever Codeforces and also Polygon <33
thanks for super duper fast editorial MikeMirzayanov !
thanks for the greatest platform ever Codeforces and also Polygon <33
thanks for super duper fast editorial MikeMirzayanov !
thanks for the greatest platform ever Codeforces and also Polygon <33
thanks for super duper fast editorial MikeMirzayanov !
thanks for the greatest platform ever Codeforces and also Polygon <33
thanks for super duper fast editorial MikeMirzayanov !
thanks for the greatest platform ever Codeforces and also Polygon <33
thanks for super duper fast editorial MikeMirzayanov !
thanks for the greatest platform ever Codeforces and also Polygon <33
thanks for super duper fast editorial MikeMirzayanov !
thanks for the greatest platform ever Codeforces and also Polygon <33
thanks for super duper fast editorial MikeMirzayanov !
thanks for the greatest platform ever Codeforces and also Polygon <33
thanks for super duper fast editorial MikeMirzayanov !
thanks for the greatest platform ever Codeforces and also Polygon <33
thanks for super duper fast editorial MikeMirzayanov !
thanks for the greatest platform ever Codeforces and also Polygon <33
thanks for super duper fast editorial MikeMirzayanov !
thanks for the greatest platform ever Codeforces and also Polygon <33
thanks for super duper fast editorial MikeMirzayanov !
thanks for the greatest platform ever Codeforces and also Polygon <33
thanks for super duper fast editorial MikeMirzayanov !
thanks for the greatest platform ever Codeforces and also Polygon <33
thanks for super duper fast editorial MikeMirzayanov !
thanks for the greatest platform ever Codeforces and also Polygon <33
thanks for super duper fast editorial MikeMirzayanov !
thanks for the greatest platform ever Codeforces and also Polygon <33
thanks for super duper fast editorial MikeMirzayanov !
thanks for the greatest platform ever Codeforces and also Polygon <33
thanks for super duper fast editorial MikeMirzayanov !
thanks for the greatest platform ever Codeforces and also Polygon <33
thanks for super duper fast editorial MikeMirzayanov !
thanks for the greatest platform ever Codeforces and also Polygon <33
thanks for super duper fast editorial MikeMirzayanov !
thanks for the greatest platform ever Codeforces and also Polygon <33
thanks for super duper fast editorial MikeMirzayanov !
thanks for the greatest platform ever Codeforces and also Polygon <33
thanks for super duper fast editorial MikeMirzayanov !
thanks for the greatest platform ever Codeforces and also Polygon <33
thanks for super duper fast editorial MikeMirzayanov !
thanks for the greatest platform ever Codeforces and also Polygon <33
thanks for super duper fast editorial MikeMirzayanov !
thanks for the greatest platform ever Codeforces and also Polygon <33
thanks for super duper fast editorial MikeMirzayanov !
thanks for the greatest platform ever Codeforces and also Polygon <33
thanks for super duper fast editorial MikeMirzayanov !
thanks for the greatest platform ever Codeforces and also Polygon <33
thanks for super duper fast editorial MikeMirzayanov !
thanks for the greatest platform ever Codeforces and also Polygon <33
thanks for super duper fast editorial MikeMirzayanov !
thanks for the greatest platform ever Codeforces and also Polygon <33
thanks for super duper fast editorial MikeMirzayanov !
thanks for the greatest platform ever Codeforces and also Polygon <33
thanks for super duper fast editorial MikeMirzayanov !
thanks for the greatest platform ever Codeforces and also Polygon <33
thanks for super duper fast editorial MikeMirzayanov !
thanks for the greatest platform ever Codeforces and also Polygon <33
thanks for super duper fast editorial MikeMirzayanov !
thanks for the greatest platform ever Codeforces and also Polygon <33
thanks for super duper fast editorial MikeMirzayanov !
thanks for the greatest platform ever Codeforces and also Polygon <33
thanks for super duper fast editorial MikeMirzayanov !
thanks for the greatest platform ever Codeforces and also Polygon <33
thanks for super duper fast editorial MikeMirzayanov !
thanks for the greatest platform ever Codeforces and also Polygon <33
thanks for super duper fast editorial MikeMirzayanov !
thanks for the greatest platform ever Codeforces and also Polygon <33
thanks for super duper fast editorial MikeMirzayanov !
thanks for the greatest platform ever Codeforces and also Polygon <33
thanks for super duper fast editorial MikeMirzayanov !
thanks for the greatest platform ever Codeforces and also Polygon <33
thanks for super duper fast editorial MikeMirzayanov !
thanks for the greatest platform ever Codeforces and also Polygon <33
thanks for super duper fast editorial MikeMirzayanov !
thanks for the greatest platform ever Codeforces and also Polygon <33
thanks for super duper fast editorial MikeMirzayanov !
thanks for the greatest platform ever Codeforces and also Polygon <33
thanks for super duper fast editorial MikeMirzayanov !
thanks for the greatest platform ever Codeforces and also Polygon <33
thanks for super duper fast editorial MikeMirzayanov !
thanks for the greatest platform ever Codeforces and also Polygon <33
thanks for super duper fast editorial MikeMirzayanov !
thanks for the greatest platform ever Codeforces and also Polygon <33
thanks for super duper fast editorial MikeMirzayanov !
thanks for the greatest platform ever Codeforces and also Polygon <33
thanks for super duper fast editorial MikeMirzayanov !
thanks for the greatest platform ever Codeforces and also Polygon <33
thanks for super duper fast editorial MikeMirzayanov !
thanks for the greatest platform ever Codeforces and also Polygon <33
thanks for super duper fast editorial MikeMirzayanov !
thanks for the greatest platform ever Codeforces and also Polygon <33
thanks for super duper fast editorial MikeMirzayanov !
thanks for the greatest platform ever Codeforces and also Polygon <33
thanks for super duper fast editorial MikeMirzayanov !
thanks for the greatest platform ever Codeforces and also Polygon <33
thanks for super duper fast editorial MikeMirzayanov !
thanks for the greatest platform ever Codeforces and also Polygon <33
thanks for super duper fast editorial MikeMirzayanov !
thanks for the greatest platform ever Codeforces and also Polygon <33
thanks for super duper fast editorial MikeMirzayanov !
thanks for the greatest platform ever Codeforces and also Polygon <33
thanks for super duper fast editorial MikeMirzayanov !
thanks for the greatest platform ever Codeforces and also Polygon <33
thanks for super duper fast editorial MikeMirzayanov !
thanks for the greatest platform ever Codeforces and also Polygon <33
thanks for super duper fast editorial MikeMirzayanov !
thanks for the greatest platform ever Codeforces and also Polygon <33
thanks for super duper fast editorial MikeMirzayanov !
thanks for the greatest platform ever Codeforces and also Polygon <33
thanks for super duper fast editorial MikeMirzayanov !
thanks for the greatest platform ever Codeforces and also Polygon <33
thanks for super duper fast editorial MikeMirzayanov !
thanks for the greatest platform ever Codeforces and also Polygon <33
thanks for super duper fast editorial MikeMirzayanov !
thanks for the greatest platform ever Codeforces and also Polygon <33
thanks for super duper fast editorial MikeMirzayanov !
thanks for the greatest platform ever Codeforces and also Polygon <33
thanks for super duper fast editorial MikeMirzayanov !
thanks for the greatest platform ever Codeforces and also Polygon <33
thanks for super duper fast editorial MikeMirzayanov !
thanks for the greatest platform ever Codeforces and also Polygon <33
thanks for super duper fast editorial MikeMirzayanov !
thanks for the greatest platform ever Codeforces and also Polygon <33
thanks for super duper fast editorial MikeMirzayanov !
thanks for the greatest platform ever Codeforces and also Polygon <33
thanks for super duper fast editorial MikeMirzayanov !
thanks for the greatest platform ever Codeforces and also Polygon <33
thanks for super duper fast editorial MikeMirzayanov !
thanks for the greatest platform ever Codeforces and also Polygon <33
thanks for super duper fast editorial MikeMirzayanov !
thanks for the greatest platform ever Codeforces and also Polygon <33
thanks for super duper fast editorial MikeMirzayanov !
thanks for the greatest platform ever Codeforces and also Polygon <33
thanks for super duper fast editorial MikeMirzayanov !
thanks for the greatest platform ever Codeforces and also Polygon <33
thanks for super duper fast editorial MikeMirzayanov !
thanks for the greatest platform ever Codeforces and also Polygon <33
thanks for super duper fast editorial MikeMirzayanov !
thanks for the greatest platform ever Codeforces and also Polygon <33
thanks for super duper fast editorial MikeMirzayanov !
thanks for the greatest platform ever Codeforces and also Polygon <33
thanks for super duper fast editorial MikeMirzayanov !
thanks for the greatest platform ever Codeforces and also Polygon <33
thanks for super duper fast editorial MikeMirzayanov !
thanks for the greatest platform ever Codeforces and also Polygon <33
thanks for super duper fast editorial MikeMirzayanov !
thanks for the greatest platform ever Codeforces and also Polygon <33
thanks for super duper fast editorial MikeMirzayanov !
thanks for the greatest platform ever Codeforces and also Polygon <33
thanks for super duper fast editorial MikeMirzayanov !
thanks for the greatest platform ever Codeforces and also Polygon <33
thanks for super duper fast editorial MikeMirzayanov !
thanks for the greatest platform ever Codeforces and also Polygon <33
thanks for super duper fast editorial MikeMirzayanov !
thanks for the greatest platform ever Codeforces and also Polygon <33
thanks for super duper fast editorial MikeMirzayanov !
thanks for the greatest platform ever Codeforces and also Polygon <33
thanks for super duper fast editorial MikeMirzayanov !
thanks for the greatest platform ever Codeforces and also Polygon <33
thanks for super duper fast editorial MikeMirzayanov !
thanks for the greatest platform ever Codeforces and also Polygon <33
thanks for super duper fast editorial MikeMirzayanov !
thanks for the greatest platform ever Codeforces and also Polygon <33
thanks for super duper fast editorial MikeMirzayanov !
thanks for the greatest platform ever Codeforces and also Polygon <33
thanks for super duper fast editorial MikeMirzayanov !
thanks for the greatest platform ever Codeforces and also Polygon <33
thanks for super duper fast editorial MikeMirzayanov !
thanks for the greatest platform ever Codeforces and also Polygon <33
thanks for super duper fast editorial MikeMirzayanov !
thanks for the greatest platform ever Codeforces and also Polygon <33
thanks for super duper fast editorial MikeMirzayanov !
thanks for the greatest platform ever Codeforces and also Polygon <33
thanks for super duper fast editorial MikeMirzayanov !
thanks for the greatest platform ever Codeforces and also Polygon <33
thanks for super duper fast editorial MikeMirzayanov !
thanks for the greatest platform ever Codeforces and also Polygon <33
thanks for super duper fast editorial MikeMirzayanov !
thanks for the greatest platform ever Codeforces and also Polygon <33
thanks for super duper fast editorial MikeMirzayanov !
thanks for the greatest platform ever Codeforces and also Polygon <33
thanks for super duper fast editorial MikeMirzayanov !
thanks for the greatest platform ever Codeforces and also Polygon <33
thanks for super duper fast editorial MikeMirzayanov !
thanks for the greatest platform ever Codeforces and also Polygon <33
thanks for super duper fast editorial MikeMirzayanov !
thanks for the greatest platform ever Codeforces and also Polygon <33
thanks for super duper fast editorial MikeMirzayanov !
thanks for the greatest platform ever Codeforces and also Polygon <33
thanks for super duper fast editorial MikeMirzayanov !
thanks for the greatest platform ever Codeforces and also Polygon <33
thanks for super duper fast editorial MikeMirzayanov !
thanks for the greatest platform ever Codeforces and also Polygon <33
thanks for super duper fast editorial MikeMirzayanov !
thanks for the greatest platform ever Codeforces and also Polygon <33
thanks for super duper fast editorial MikeMirzayanov !
thanks for the greatest platform ever Codeforces and also Polygon <33
thanks for super duper fast editorial MikeMirzayanov !
thanks for the greatest platform ever Codeforces and also Polygon <33
thanks for super duper fast editorial MikeMirzayanov !
thanks for the greatest platform ever Codeforces and also Polygon <33
thanks for super duper fast editorial MikeMirzayanov !
thanks for the greatest platform ever Codeforces and also Polygon <33
thanks for super duper fast editorial MikeMirzayanov !
thanks for the greatest platform ever Codeforces and also Polygon <33
thanks for super duper fast editorial MikeMirzayanov !
thanks for the greatest platform ever Codeforces and also Polygon <33
thanks for super duper fast editorial MikeMirzayanov !
thanks for the greatest platform ever Codeforces and also Polygon <33
thanks for super duper fast editorial MikeMirzayanov !
thanks for the greatest platform ever Codeforces and also Polygon <33
thanks for super duper fast editorial MikeMirzayanov !
thanks for the greatest platform ever Codeforces and also Polygon <33
thanks for super duper fast editorial MikeMirzayanov !
thanks for the greatest platform ever Codeforces and also Polygon <33
thanks for super duper fast editorial MikeMirzayanov !
thanks for the greatest platform ever Codeforces and also Polygon <33
thanks for super duper fast editorial MikeMirzayanov !
thanks for the greatest platform ever Codeforces and also Polygon <33
thanks for super duper fast editorial MikeMirzayanov !
thanks for the greatest platform ever Codeforces and also Polygon <33
thanks for super duper fast editorial MikeMirzayanov !
thanks for the greatest platform ever Codeforces and also Polygon <33
thanks for super duper fast editorial MikeMirzayanov !
thanks for the greatest platform ever Codeforces and also Polygon <33
thanks for super duper fast editorial MikeMirzayanov !
thanks for the greatest platform ever Codeforces and also Polygon <33
thanks for super duper fast editorial MikeMirzayanov !
thanks for the greatest platform ever Codeforces and also Polygon <33
thanks for super duper fast editorial MikeMirzayanov !
thanks for the greatest platform ever Codeforces and also Polygon <33
thanks for super duper fast editorial MikeMirzayanov !
thanks for the greatest platform ever Codeforces and also Polygon <33
thanks for super duper fast editorial MikeMirzayanov !
thanks for the greatest platform ever Codeforces and also Polygon <33
thanks for super duper fast editorial MikeMirzayanov !
thanks for the greatest platform ever Codeforces and also Polygon <33
thanks for super duper fast editorial MikeMirzayanov !
thanks for the greatest platform ever Codeforces and also Polygon <33
thanks for super duper fast editorial MikeMirzayanov !
thanks for the greatest platform ever Codeforces and also Polygon <33
thanks for super duper fast editorial MikeMirzayanov !
thanks for the greatest platform ever Codeforces and also Polygon <33
thanks for super duper fast editorial MikeMirzayanov !
thanks for the greatest platform ever Codeforces and also Polygon <33
thanks for super duper fast editorial MikeMirzayanov !
thanks for the greatest platform ever Codeforces and also Polygon <33
thanks for super duper fast editorial MikeMirzayanov !
thanks for the greatest platform ever Codeforces and also Polygon <33
thanks for super duper fast editorial MikeMirzayanov !
thanks for the greatest platform ever Codeforces and also Polygon <33
thanks for super duper fast editorial MikeMirzayanov !
thanks for the greatest platform ever Codeforces and also Polygon <33
thanks for super duper fast editorial MikeMirzayanov !
thanks for the greatest platform ever Codeforces and also Polygon <33
thanks for super duper fast editorial MikeMirzayanov !
thanks for the greatest platform ever Codeforces and also Polygon <33
thanks for super duper fast editorial MikeMirzayanov !
thanks for the greatest platform ever Codeforces and also Polygon <33
thanks for super duper fast editorial MikeMirzayanov !
thanks for the greatest platform ever Codeforces and also Polygon <33
thanks for super duper fast editorial MikeMirzayanov !
thanks for the greatest platform ever Codeforces and also Polygon <33
thanks for super duper fast editorial MikeMirzayanov !
thanks for the greatest platform ever Codeforces and also Polygon <33
thanks for super duper fast editorial MikeMirzayanov !
thanks for the greatest platform ever Codeforces and also Polygon <33
thanks for super duper fast editorial MikeMirzayanov !
thanks for the greatest platform ever Codeforces and also Polygon <33
thanks for super duper fast editorial MikeMirzayanov !
thanks for the greatest platform ever Codeforces and also Polygon <33
thanks for super duper fast editorial MikeMirzayanov !
thanks for the greatest platform ever Codeforces and also Polygon <33
thanks for super duper fast editorial MikeMirzayanov !
thanks for the greatest platform ever Codeforces and also Polygon <33
thanks for super duper fast editorial MikeMirzayanov !
thanks for the greatest platform ever Codeforces and also Polygon <33
thanks for super duper fast editorial MikeMirzayanov !
thanks for the greatest platform ever Codeforces and also Polygon <33
thanks for super duper fast editorial MikeMirzayanov !
thanks for the greatest platform ever Codeforces and also Polygon <33
thanks for super duper fast editorial MikeMirzayanov !
thanks for the greatest platform ever Codeforces and also Polygon <33
thanks for super duper fast editorial MikeMirzayanov !
thanks for the greatest platform ever Codeforces and also Polygon <33
thanks for super duper fast editorial MikeMirzayanov !
thanks for the greatest platform ever Codeforces and also Polygon <33
thanks for super duper fast editorial MikeMirzayanov !
thanks for the greatest platform ever Codeforces and also Polygon <33
thanks for super duper fast editorial MikeMirzayanov !
thanks for the greatest platform ever Codeforces and also Polygon <33
thanks for super duper fast editorial MikeMirzayanov !
thanks for the greatest platform ever Codeforces and also Polygon <33
thanks for super duper fast editorial MikeMirzayanov !
thanks for the greatest platform ever Codeforces and also Polygon <33
thanks for super duper fast editorial MikeMirzayanov !
thanks for the greatest platform ever Codeforces and also Polygon <33
thanks for super duper fast editorial MikeMirzayanov !
thanks for the greatest platform ever Codeforces and also Polygon <33
thanks for super duper fast editorial MikeMirzayanov !
thanks for the greatest platform ever Codeforces and also Polygon <33
thanks for super duper fast editorial MikeMirzayanov !
thanks for the greatest platform ever Codeforces and also Polygon <33
thanks for super duper fast editorial MikeMirzayanov !
thanks for the greatest platform ever Codeforces and also Polygon <33
thanks for super duper fast editorial MikeMirzayanov !
thanks for the greatest platform ever Codeforces and also Polygon <33
thanks for super duper fast editorial MikeMirzayanov !
thanks for the greatest platform ever Codeforces and also Polygon <33
thanks for super duper fast editorial MikeMirzayanov !
thanks for the greatest platform ever Codeforces and also Polygon <33
thanks for super duper fast editorial MikeMirzayanov !
thanks for the greatest platform ever Codeforces and also Polygon <33
What's wrong with you bro? Are you expressing your gratitude or making fun of him?
What's going on here, please don't fill comment section like that.
Can any kind soul please explain all types of solutions with time complexities $$$O(a+b+c)$$$, $$$O(log(a+b+c))$$$, $$$O(1)$$$ for 1950F - 0, 1, 2, Tree! clearly and intuitively :(
I have a question. yesterday I sent in and was accepted for four problems in the Division 4 contest while now it turns out that I only sent in one. Why?
Be patient, system testing is currently in progress. Your three others are in the line for rejudging.
thank you for your reply
what do you mean by rejudging? sorry i am new here
Normally in a Codeforces contest, in-contest submissions are judged by a preliminary testset (or more commonly called pretests) to reduce server load. After the contest ends (and with an extra delay for preparation and such), all AC submissions will be rejudged in a phase called "system test" with the full testset available.
For Div.3, Div.4 and Educational however, the in-contest testset is complete, yet after the contest ends, a 12-hour open hacking phase is presented for community to hack any AC submissions they felt incorrect but the original testset missed. After the hacking phase, those hacks are added to the testset, and after some more delay for preparation, system test will kick in.
Please help this suffering guy. In Problem E: Why only prefix and suffix of length of divisors of n is taken, I took all possible substring of the length of divisors of n instead of only prefix and suffix, and it will sure give TLE.
same question, got TLE by taking all possible substrings
Because it can be proven that if the prefix and suffix of some substring length c both don't pass that means that there must be more than 1 character for which the K-string is different than the original. You don't use any substrings in between because it is not optimal and doesn't make any sense to concatenate those substrings together some number of times to where the length of the entire string is equal to the original string because you are introducing offsetting character's to the original string from the get go. So, you don't even check those cases in the first place because anyway once you do that you are introducing wrong characters and your going in the wrong direction.
for example in a string abcabcabc it makes absolutely no sense to ever check the substring "bca" because no matter how many times you concatonate this string together, the characters just offset. because "abc" != "bca".
it's possible that you may have just overlooked that you compare the strings head on.
Wow, nice explanation thanks for your help. I really appreciate it. Codeforces community is really good.
Let's consider Problem E without the "1 mistake rule".
If that were the case, it would be enough to check all of the divisors of n (let d be a divisor of n) and only test the prefix of length d.
However, with the "1 mistake allowed", it's not guaranteed that the prefix is the correct pattern (perhaps the only mistake is within it). That's why we need another string to act as our pattern. You can use the next string starting from d of length d
s[d:2*d]
or the suffixs[n-d:]
. it might be easier to spot in this test case :In the contest, I implemented this idea without proving it. It was based on intuition.
Thanks for the complexity analysis in D. Note that most of the 30 numbers are IGNORED so the complexity is far lower than n^0.587.
If you do precomputation then its about $$$O(N^{1.4})$$$ (not a tight bound just a bigger bound than $$$O(N^{1+(log(2)/log(10))}$$$)).
Sorry, can anyone tell me where the problem is with this code? https://codeforces.me/contest/1950/submission/253805652 I made a graph and put an equal edge between both songs with at least one component, so the answer is equal to the longest path in the final graph.
why 2 segments are sufficient for problem E
hope this helps
Because the string after being divided into k parts has only maximum of 1 outlier. If you get a outlier in the 1st segment (
hshahaha
) then the 2nd segment musn't be an outlier, so it is enough.Is G NP-complete? G can be reduced into a longest path problem, but there are additional constraints.
Problem D: My Solution
Given: A number num(let)
We have to Check: Whether num is product of decimal numbers which contain 0's and 1's (binary) as their digits.
Explanation: ---- Below i have used binary word. It is denoting the decimal number having digit as 0 and 1.
---- Can we generate all decimal number having binary digits?
----- Iterate over these decimal(containing binary as digits) numbers and reduce n by the power of this number contained in n.
----- if atlast n=1 then answer is yes otherwise no.
Can Anyone explain the concept of 5th Question
A brute solution for D
...
in Ques. E, why do we need to iterate in reverse also?
"**acabab**"
look at the above testcase: Possible length of subarray is 1,2,3 or 6.
If we only consider the subarray starting from beginning, then the answer would have been 6.
But considering from last, we can achieve an optimal answer of 2, where we concatenate ab 3 times to get ababab which satisfies the given condition.
This condition wouldn't have satisfied if we had considered it from the beginning where we would have got acacac which differs from the given string in 2 places and won't be considered for solution. Hope that u have gotten my point.
thanks, got it. so it doesn't work if we increase the mistake count to 2 or above. how do we solve the general case?
It doesn't have to be reverse it can be the string starting from d with length d(d is a divisor of n). The key point it's another string starting from an index divisible by d and with length d. We did this because we assumed that there is a mistake in the first string of length d
Sometimes, i feel that i don't think correct to solve the problems like D.Product of Binary Decimals, i didn't think correct and i don't know DP to think about the solution to this problem. How can i fix this problem?
I think in term's of solution what are the different solutions can different solution have same pattern solution. Are there are finite solutions in terms of 'N' -> can this solution be pre-computerd
I managed to solve D without DP or precomputation. Although I was unsure about getting hacked.
can you tell me the proof of your solution and tell me why it works ? You basically checked for any factor i of n , i and n/i should both be binary ?
I can't proof but can feel the intuition. The constraint is not so big. Had the constraint be 1e6 and my solution would definitely fail.
Number of terms multiplied together to get N will not be very big.
11^3 * 10^2 >= N [ two factors is enough to check ]
11^2 * 11^2 * 10^1 >= N [ Three factors but you can first divide by 10 to get rid of 1 term, therefore left with two terms to check ]
11 * 101 * (11 or 10 at max) [ So it's easy to check. first divide by 10 then divide by 11, check if that's binary. If not look for it's two factors ]
I hope you get the idea.
My issue is not to solve with DP or any topic, but i want to learn how to think right to solve problems like this problem
Practice more. Solving math and recursive problems might help.
Thank you for help
During the contest i didn't get D from the first try and that's ok . I actually wrote three different codes for D until it worked . And in problem E I rushed to finish it in the last 30 minutes leaving a few minutes for F. I think the biggest take way from what i said is that you should not give up until the contest is over .I also think you should approach problems from different angles and solve more problems.
Thank you for help
Where s the tutorial for G?
why are ratings not updated yet?
They are
Is it possible to solve G using bitmask dynamic programming?
Yes, you don't even need to think about it as a graph.
My state will be dp(pos,last,mask)
from every state I'll increment pos by taking or not taking that element.
last will determine what my last taken position was.
mask will keep track what positions are already taken.
Do you think it can be solved like this?
Too slow, you don't need to care about the position, mask and last placed is enough.
But without pos, how I'll reach base case which is pos == n? Can you please explain a little bit?
base case is when the mask is all ones, that means you processed all songs
But how will I count the number of songs that I deleted?
That will be the value of the dp.
1950G — Shuffling Songs Tutorial unavailable. Someone please explain the solution in the meantime.
253971845 -> This is my solution which got TLE in test case 39.
Thank you very much for this round! Maybe I could have solved more problems (at least one more), but I finally became a pupil! This is great!
i just want to know that for e question,i submitted my code in c++17 and it got wrong answer on test2,then after contest i checked that test and it was giving right answer on my visualstudiocode compiler and then i submitted that same code in c++20 and it got accepted,now i want to know why is it so and am i responsible for this mistake of choosing compiler or is it a error from codeforces's side,also i dont think i used anything in my code which would not have worked in c++17 according to me.someone please help
pow
is a dangerous function in C++ since its precision is really bad, combining with the rounding-down nature of integer casting it might corrupt the prime check procedure. Probably 64-bit processing in CF's C++20 made it a bit more precise so you passed, but C++17 32-bit didn't.A safer / more stable way for square root alone should be
sqrt
. You can also try checking fori * i <= n
, but careful for overflow (normally if the step is justi++
I'm still confident that such overflow won't happen).Can anyone help me? I use dsu(Disjoint set union) to solve problem G, but I don’t know why it always goes Wrong answer on test 5. I spent a long time thinking about it, but I had no idea why.Here is my code:253955348
DSU is a wrong approach. A test like this would fail you:
Correct answer should be
1
.Thank you very much, you are absolutely right. I don't fully understand the question, that's stupid.
It's okay, everyone makes mistakes. Keep yourself up and do better next time.
Glad that I could help.
so sorry to ask but can you please check my submission for G. thank you. something is wrong
Since it's a Hamiltonian walk, you should know where that walk is currently stopping at — instead of trying to link an edge to any vertex in the subset — your DP is lacking an attribute for the last vertex of your path.
Bonus: comparing raw strings will TLE eventually (around test 33). Try to optimize that later.
I am sorry so what should i do :(
Hamiltonian walk and cycle are different??
hey!!! it got accepted apparently i just changed the position of for loops and it gave me AC :), thank you!
i was following 4. Check for existence of Hamiltonian walk from this blog:https://codeforces.me/blog/entry/337
in problem D when i am using this: for(ll i=2e5;i>=10;i--){ if(isBD(i)){ vd.pb(i); } }
to pre calculating binary numbers then it works correct for all test cases,but when i am doing for(ll i=10;i<=2e5;i++) it is producing wrong output on the last test case (1001) ,can anyone explains why the first one is fetching correct answer?
this is my approach 254040093
I had the same implementation and it was outputting wrong answer on 1001 . so i just added
if n in BD : print"YES"
the reason is that 1001 is divisible by1, 7, 11, 13, 77, 91, 143, 1001
notice how if you divide by 11 you won't be able to prove it's fine because you'll be left with 91 .another trick is to sort the array of binary decimals in non-ascending order and
for(ll i=2e5;i>=10;i--)
does that in your code.But i still don't get why this answer works . I hope someone can explain it .
For question g, is it wrong to use the length of the longest path in the graph?
No, it's right
sorry for the confusion with clz. Interesting, learnt something new, ty
include<bits/stdc++.h>
using namespace std; int main() { int t; cin>>t; while (t--) { int a,b,c; cin>>a>>b>>c; bool case1=(a<b&&b<c); bool case2=(a<b&&b>c);
}
I think this code for A without else looks better
Here is an elaganto solution with T(N) = O(log(N)), S(N) = O(1) for 1950F — 0, 1, 2, Tree!
Why my solution works? Submission I submitted this solution in hurry and it got AC.
I removed every divisor of n which is also a binary_decimal number from n, and in the end if the n is reduced to 1, then print "YES" else "NO".
I did it in greatest -> smallest binary_decimal number order which passed the soln. smalletst -> greatest binary_decimal number order can't work. Failing TC : 1001.
Where 11*91 = 1001
Basically, it was just a fluke, which went good.
I want to know How can i verify correctness of such wierd claims in a live contest?
Someone please help with problem G(im new to dp): 254308462
Waiting for editorial of G.....
Let's say we have a point (x,y) on a coordinate system. What are the possible rotations of the point?
I have a beautiful recursive approach for Question D https://codeforces.me/contest/1950/submission/253808823
Let F(n)=b1*b2*b3*..*bk , where b1,b2,..bk are binary decimal numbers . Then F(n)=b1*F(n/b1)
Thus if we find a binary decimal factor of n then if F(n/b1) is a product of binary decimal numbers then n also is .
It's been 4 days, still no tutorial for G?
Consider a graph there $$$i$$$-th vertex has two values $$$(g_i, w_i)$$$. We can move from $$$i$$$ to $$$j$$$ only if $$$g_i = g_j$$$ or $$$w_i = w_j$$$. Now a simple path in that graph is some permutation we want to get (if vertex is not in our path, we will delete it). We want to delete as many as possible, so we have to find maximum simple path in that graph.
i have done using graph only , could you tell what is wrong with it? https://codeforces.me/contest/1950/submission/254107386 , i have found the longest path in the graph and substracted it from the total number of edges
got it
https://codeforces.me/contest/1950/submission/254107386 could anyone help me with this (G question) , my logic is that i have made a graph with vertices having edge on having same genre or same writer or both , and then find the longest path in the graph , but it is giving wrong answer in testcase 3 at 163rd token :/
Can anyone help me for Question E, here is my solution Python code. It is giving TLE but I think the time complexity is O(128*N). Also the same code of C++ version is getting accepted code.
what is the difference between (a<b && b<c) and if(a<b){ if(b<c){ cout<<"STAIR"<<endl; }else{ cout<<"PEAK"<<endl; }else cout<<"NONE"<<endl;
Try a scenario where
a < b
andb >= c
and see for yourself.Is it possible to solve 1950G - Shuffling Songs without DP? SlavicG flamestorm mesanu
Could anybody tell me why my code fails? Idea of the solution is to create a graph where each node is a song and there is an edge between two songs if they have the same genre or writer. Then we can find the size of the largest connected component in the graph and the answer will be n — size of the largest connected component. This is because we can rearrange the songs in the largest connected component in any way we want and the rest of the songs will be removed.
I am glad to give you an example which your solution will be failed.
If we just consider "connected component" the answer will be 0, however we must get a continuous chain to make sure a correct shuffle. In this example, answer will be 1, as we choose to remove the song
<c, e>
and get a correct shuffle.E was a genius question, Thanks :)
I did, 1950E using string hashing, (i learned that concept few days ago, so i tried it over here), And it worked...... :)
F can be solved in O(1), so I squeezed the code in one line lol
for test in range(int(input())): a,b,c = [int(i) for i in input().split()]; print(-1 if a!=c-1 else (len(bin(c))+b//c + (-1 if 2*(c-(1<<(len(bin(c))-3)))+b%c>c else (-2 if (1<<(len(bin(c))-3))<(b%c)+c else -3))))