Codeforces Round #869 (Div.1, Div.2) Editorial

1818A - Politics

Problem idea: adamant
Preparation: adamant

1818B - Indivisible

Problem idea: adamant
Preparation: adamant

1817A - Almost Increasing Subsequence

Problem idea: dario2994
Preparation: jeroenodb

1817B - Fish Graph

Problem idea: jeroenodb
Preparation: jeroenodb

1817C - Similar Polynomials

Problem idea: adamant
Preparation: adamant

1817D - Toy Machine

Problem idea: adamant
Preparation: jeroenodb

1817E - Half-sum

Problem idea: adamant
Preparation: adamant

1817F - Entangled Substrings

Problem idea: adamant
Preparation: adamant

• 9 hours ago, # ^ | degree >= 4 won't ensure that that the tail of fish don't lie inside the cycle.

  • 9 hours ago, # ^ | Refer to editorial, if you still think it is not enough then try to make a counterexample and prove that it is impossible

    • 9 hours ago, # ^ | Sorry. The editorial came so fast that I thought I was replying on announcement blog.

  • 9 hours ago, # ^ | It does. If a fish tail is inside the cycle, then use that tail to make a smaller cycle instead. The edge that used to be in the old cycle but isn't in the new cycle will be a correct tail outside the cycle.

  • 47 minutes ago, # ^ | ← Rev. 2 →   0 i don't know what is wrong here, firstly i found every cycle and then check if it can be used as fish graph. but getting WA every time. Can anyone tell me what is wrong here? https://codeforces.com/contest/1818/submission/203991640

• 7 hours ago, # ^ | What if we form a bridge tree ( biconnected component decomposition) and then do dfs on the new tree and find a node with degree >=3 (as here we squeezed all cycles into a single node).

• 9 hours ago, # ^ | Nvm, I forgot to output the number of edges, dumb mistake, thank you the board for answering my question

• 6 hours ago, # ^ | i felt the same.

• 3 hours ago, # ^ | what is the original problem?

• 9 hours ago, # ^ | Understood Get back to Lagrange formula. Write it as . We have only in first product — . We want to get its . Its minus sum of its roots. So we get .

• 8 hours ago, # ^ | TLE results that were non-trivial, i.e., you had to change ur code even the slightest, they don't regrade it.

  • 8 hours ago, # ^ | Well, you remind me. I tried the same code and got AC now, it's really a judge fault.

    • 7 hours ago, # ^ | Well, my fault. I tried the same code with different compiler. GNU C++17 for AC, GNU C++20 (64) for TLE. Bad luck for me :(

• 8 hours ago, # ^ | I have used the brute force approach to generate all possible answer to see any answer for each test case follow some pattern. bool check(vector<int>& a,int n){ for(int i=0;i<n-1;i++){ int sum=a[i]; for(int j=i+1;j<n;j++){ sum+=a[j]; if(sum%(j-i+1)==0){ return false; } } } return true; } void solve() { int n;cin>>n; cout << "n: " << n << '\n'; vector<int> a(n); loop(0,n-1){a[i]=i+1;} do{ if(check(a,n)){ print(a); } }while(next_permutation(all(a))); cout << '\n'; } if you run this code for small test, like from 1 to 11, you will observe that answer exist if n is even and if n==1, and for each n(keep in mind that it is even) there is permuatation which follow some pattern like 2 1 4 3 6 5 ..... n-2 n-3 n n-1 you can try the above code and check it out yourself The only problem is that this brute force will work till n=11, after that it will take very long time to produce answer. So, we cannot check it for large test cases. Also n=1 is the only odd number that produce valid answer which is 1 only.

  • 8 hours ago, # ^ | After 1 hour of trying, this is what I did to find the pattern.

• 8 hours ago, # ^ | Hi, could you share some details please?

• 9 hours ago, # ^ | You can also solve in by finding bridges and running one BFS or DFS to print the cycle.

  • 9 hours ago, # ^ | Thank you, could you please elaborate on the bridges part? I am not really familiar with bridges and articulation points

• 7 hours ago, # ^ | Wouldn't it then be the max number of strings that are the same?

• 9 hours ago, # ^ | On the third line of the editorial.

Indeed, if we denote by S an operator such that SA(x)=SA(x+1)

• 8 hours ago, # ^ | Thanks for noticing! I will fix it soon.