### awoo's blog

By awoo, history, 20 months ago, translation,

1295A - Display The Number

Tutorial
Solution (BledDest)

1295B - Infinite Prefixes

Idea: Roms

Tutorial

1295C - Obtain The String

Idea: Roms

Tutorial
Solution (Roms)

1295D - Same GCDs

Tutorial

1295E - Permutation Separation

Tutorial

1295F - Good Contest

Idea: Roms

Tutorial
Solution (BledDest)

• +106

 » 20 months ago, # |   +10 Finally, the editorial is out :D
•  » » 20 months ago, # ^ |   +1 O(n^3) solution for F 69782525
•  » » » 20 months ago, # ^ |   0 69879879 lagrang interpolation can be done in O(n). This is also a O(n^3) solution.
 » 20 months ago, # | ← Rev. 3 →   0 in F how are we dividing into segments, little confused after reading tourist solution, also could someone help me what is this another way(link) of solving increasing sequences question.Thanks in advance.
•  » » 20 months ago, # ^ |   0 We use the values of $l_i$ and $r_i + 1$ as left borders of the segments: we sort all of them, get rid of the unique values, and each value now defines the beginning of a new segment. So, for each segment we get, all values from it can be used at the same positions of the non-descending sequence we are trying to construct.
 » 20 months ago, # |   0 Please,can anyone explain problem C,how you are calculating nxt table since I am not able to visualize it. thank you.
•  » » 20 months ago, # ^ | ← Rev. 2 →   0 If you are at index i in the string and want to calculate the smallest index of jth char between i and |s|, two possibilities occur. 1. s[i] is the jth character 2. s[i] is some other character than the jth characterFor the second case, s[i][j]=s[i+1][j] and for the first case s[i][j] is simply i
•  » » » 20 months ago, # ^ |   0 Think about it this wayFor each position we need the next position for all characters from 'a' — 'z' if they exist. So starting from back to front for the current position we get results from index in front and for the current index we can set next position for the character at index i to be index i, since that's closer.Hope this helps.
•  » » 20 months ago, # ^ | ← Rev. 6 →   0 case -1: if any char in t is not present in s. other wise: store the positions of a,b,c...z occurring in S, in a vector of size 26.now build z from t by taking one char at a time (starting from 0). now suppose you have build some part of z and you had just chosen a character which was at position 'cur' in s.now we want to add next char of t at the end of z — lets say the next char is x. hence we need the position of 'x' in s. if we think greedily we will chose that position which is just after our cur. if there is no x after cur. we can start from beginning and therefore setting cur=0, and number of steps ++.https://codeforces.com/contest/1295/submission/69747737
•  » » 20 months ago, # ^ |   0 Just maintain an array recording the nearest char C whose index is strictly bigger than the current index enumerated from n to 1
 » 20 months ago, # |   +7 What can be the possible divide and conquer solution for problem E? Thank you
•  » » 20 months ago, # ^ |   0 I think my point-update segment tree solution counts as divide-and-conquer, since it solves the problem for sublengths of the permutation and combines them: https://codeforces.com/blog/entry/73413#comment-576470
 » 20 months ago, # |   +14 Small correction: The combinatoric identity in F, the denominator of the last fraction is k and not k+1.
•  » » 20 months ago, # ^ |   +6 Will be fixed in a few minutes. Thank you!
 » 20 months ago, # |   +3 Is there any inclusion exclusion based solution to D?
•  » » 20 months ago, # ^ |   +13 Maybe this could help
•  » » 20 months ago, # ^ |   +5 Of course there is :) https://codeforces.com/contest/1295/submission/69760075
•  » » » 20 months ago, # ^ |   0 Sorry, can you please explain your idea? I understand the general idea but not the specifics. Thanks
•  » » » 16 months ago, # ^ |   0 can you please explain
•  » » 20 months ago, # ^ |   +3
•  » » » 16 months ago, # ^ | ← Rev. 2 →   0 can you plz plz explain atleast explain if(nf%2==1){ // wh(count/mul); rem=rem+count/mul; } else{ // wh(count/mul); rem=rem-count/mul; } } this
•  » » 20 months ago, # ^ |   0 There exists a combinatorial proof of Euler Phi Function formula that uses the inclusion-exclusion principle.
•  » » 16 months ago, # ^ | ← Rev. 2 →   +4 my stupid ass was not able to understand even the tutorial..... for all the stupid ones out there my friend Thallium54 have a blog https://thallium.space/题解/tutorial/2020/01/29/CF1295D
•  » » 15 months ago, # ^ |   +1 I also did it with Inclusion-Exclusion https://codeforces.com/contest/1295/submission/84912597
 » 20 months ago, # |   0 IN PROBLEM D HOW IS 0 GETTING MANAGED BY USING THE EULER TOILENT FUNCTION.EDITORIAL SAYS THAT GCD(0,m')=m'but 0 can be added to a and gcd(a,m) will be same as gcd(a+0,m);please help..Thanks in advance ..
•  » » 20 months ago, # ^ |   0 $x' = x' ' g$ and author shows why 0 is not valid for $x' '$. The case $gcd(a, m) = gcd(a + 0, m)$ is covered when $x' ' = a'$
•  » » » 14 months ago, # ^ |   0 i am not able to understand the tutorial for 1295D can you explain
•  » » » » 14 months ago, # ^ |   0 Let $gcd(a,m) = g$. Also Let $x' = x+a$.We want $gcd(x',m) = g$ which is equivalent to $gcd(\frac{x'}{g},\frac{m}{g}) = 1$So we need find number of $x'' = x'/g$ co-prime with $m' = m/g \in [1,m'-1]$ Since $x+a > 0$ This is the Euler Phi Function.
•  » » » » » 13 months ago, # ^ |   0 thanks finally got it
 » 20 months ago, # |   +6 Please explain problem E in simple words..
•  » » 20 months ago, # ^ |   +12 Which words do you not understand?
•  » » » 20 months ago, # ^ |   0 We are iteration on val or on POS and what we store on segment tree. And Finally this thing -- So what will happen if we increase val by 1? Let's define the position of pk=val as k. For each pos≥k we don't need to move pk to the second set anymore, so we should make t[pos]−=ak. On the other hand, for each pos
•  » » » » 20 months ago, # ^ | ← Rev. 2 →   0 Every node of segment tree stores the minimum cost if we select a segment [0,r] and we want all the elements between [0,r] lie between [0,val]. Initially assume val is -1. Therefore for every segment [0,r] we will have to shift its elements to the other segment (since no value lies between [0,val], i.e., [0,-1]). Now we will iterate over val. Now when value is 0, let the position of 0 in the original array be 'ind'. How to update the answer now?? For every segment [0,r] which contain the index 'ind', we do not need to shift val to the other segment (we shifted it when val was -1,). Thus for every segment [0,r] which contain 'ind' we will add (-a[ind]). And for every segment [0,r] which does not contain 'ind' we need to get it, therefor we will add (a[ind]). Hope you got it. Feel free to ask if you didn't understand anything.
•  » » » » » 20 months ago, # ^ |   0 We build segment tree on the given array and then check ind for every node Right? And why we iterate on Val not on pos.
•  » » » » » » 20 months ago, # ^ |   0 As we are sweeping according to val, which means we already know the answer for val, and we want to know the answer for val+1.
•  » » » » » » » 20 months ago, # ^ |   0 So what will happen if we increase val by 1? Let's define the position of pk=val as k. For each pos≥k we don't need to move pk to the second set anymore, so we should make t[pos]−=ak. On the other hand, for each pos
•  » » » » » » » » 20 months ago, # ^ |   0 Suppose your current value of val='V' and possible segments are [0,0],[0,1],[0,2],[0,3],[0,4]...,[0,n-1]. For each of these segments we know the cost. I will define the cost for a segment [0,x], cost[x] as follows: for i in [0,x]:// lets call this loop 1 if(p[i]>V) // removing the elements // which are greater than V cost[x]+=a[i]; for i in [x+1,n-1]:// lets call this loop 2 if(p[i]<=V) // adding the elements which // are less than equal to V // into the current set cost[x]+=a[i];  2. Now I need to find the answer for V+1. Let k be the index of V+1 in the permutation. Now for the segments [0,0],[0,1],[0,2],.....[0,k-1], cost of loop 1 will remain same (why? try to think). But answer for loop 2 will change. We need to add V+1 into the segment, thus we need to add a[k] (since I need to shift V+1 from the second segment to these segments.), and for segments [0,k],[0,k+1],[0,k+2],[0,k+3],.....[0,n-1], answer of loop 2 will remain same but answer for loop 1 will be different (why? think) thus we need to subtract a[k].
•  » » » » » » » 20 months ago, # ^ |   0 Why are we sweeping from 1 to n+1 ? shouldn't it be from 1 to n ? n+1 doesn't even exist in the permutation.
•  » » » » » » » » 20 months ago, # ^ |   +1 "All elements in the left set smaller than all elements in the right set" means that there is such value val that all elements from the first set less than val and all elements from the second set are more or equal to val. " Since all elements on the left set are less than (not less than equal to )val therefore sweeping till n+1, means left set will contain numbers from [1,n].
 » 20 months ago, # |   0 what is n in the editorial of Problem-B ? i mean what does n mean?
•  » » 20 months ago, # ^ |   0 $n$ is the length of the string.
•  » » » 16 months ago, # ^ | ← Rev. 3 →   0 In B, getting Wa on Test 62 81570680. Investigation for many hours found that for this case: 1 100000 -99999 111111111111....0 Local computer outputs 2 (correct answer) but Custom invocation output 1 (WA). Smaller cases like 10 -9, 100 -99, 1000 -999, 10000 -9999 works but only problem with 1e5. What could be the possible reason?Update: Changing to Clang compiler got AC
 » 20 months ago, # |   0 C can also be solved using binary search, pretty easy to understand.69761627
•  » » 20 months ago, # ^ |   0 yep even i have done something very similar. 69899087.
•  » » 20 months ago, # ^ |   0 Hey, I didn't get your code.How you are applying a binary search. Can you explain in detail please.
•  » » » 20 months ago, # ^ |   0 Firstly we store the positions of all the appearance of each characters in string s. Then for each character in string t, we want the first appearance of that character after the position of the last character, which could be done with binary search.
•  » » » » 20 months ago, # ^ |   0 last character of what? string s or t ?
•  » » » » » 20 months ago, # ^ |   0 I mean the last character that has been obtained in string t. Sorry for my bad English.
 » 20 months ago, # | ← Rev. 5 →   +3 F says: we will count all the non-descending sequences but must be non-increasing, since pair (1, 2) is inversion according to taskUPD: sorry, must be descending with possible equal, since descending with possible equal != non-increasing (1, 3, 2) is not-increasing, but not a descending with possible equal
•  » » 20 months ago, # ^ |   0 descending means a[i+1]=a[i]
•  » » » 20 months ago, # ^ |   +3 yes, but we need the array to look something like this: 3 3 2 1 a[i] >= a[i+1] it's not a strict decrease, but not a non-decrease or non-increase
•  » » » » 20 months ago, # ^ | ← Rev. 2 →   0 a[i+1] is less than a[i]----------a[i+1]=a[i]. -------non-descendingIn this problem, we need to count the sequence a[] which satisfied:a[1]<=a[2]<=...<=a[n].And it means the sequcence a[] is a non-descending sequence.
•  » » 20 months ago, # ^ |   +3 Yeah I got confused by that; once I realized the issue, I just reversed the array after reading the input to get the right answer
 » 20 months ago, # |   +4 What programming language is the D solution written is? Is that just pseudocode?
•  » » 20 months ago, # ^ |   +12 Looks like Kotlin.
•  » » » 20 months ago, # ^ |   0 Sure, it is Kotlin!
 » 20 months ago, # | ← Rev. 2 →   +1 Any other solution for problem D? or more detailed explanation for the one mentioned in the tutorial?
•  » » 20 months ago, # ^ | ← Rev. 2 →   +21 1) gcd(a, m) is fixed -> let it be G2) Want to find gcd(a + x, m) = G, 0 <= x < m3) Same as gcd(X, m) = G, a <= X < a + m3.5) gcd(X, m) = gcd(X % m, m) (Think about euclidean algorithm)3.75) When you loop X from a to a + m — 1, X % m includes all possible outcome from 0 to m — 1.4) Same as gcd(Y, m) = G, 0 <= Y < m5) Same as gcd(Y / G, m / G) = 1, 0 <= Y / G < m / G (Floor division)6) So count number of Z such that gcd(Z, m / G) = 1 under m / G. That's the definition of euler's totient function.
•  » » » 20 months ago, # ^ |   0 How could you be sure that (in point 5) after divide all numbers (0 to m-1) by G there can be found φ(n) numbers of value those are coprime to m/G ??
•  » » » » 20 months ago, # ^ |   0 For gcd(a, b) = G, a = k1*G and b = k2*G where gcd(k1, k2) = 1So gcd(a / G, b / G) = 1 is a necessary and sufficient conditionDoes that help?
•  » » » » 20 months ago, # ^ | ← Rev. 3 →   0 What do you mean by $\phi(n)$? If you want number of numbers coprime to $m/G$, then you use $\phi(m/G)$. $\phi(n)$ gives number of numbers coprime to $n$, and smaller than $n$.
•  » » » 2 months ago, # ^ |   0 THANKS
•  » » 20 months ago, # ^ | ← Rev. 2 →   +2 I hope my blog would help a bit.
•  » » » 10 months ago, # ^ |   0 It did,thanks!
•  » » » 5 weeks ago, # ^ |   0 can you please re-upload the blog that explains problem D?It says the blog is no more existing . Thallium54
•  » » » » 5 weeks ago, # ^ |   0 Fixed
•  » » » » » 5 weeks ago, # ^ |   0 thanks
 » 20 months ago, # |   +1 Can someone explain editorial for B?
•  » » 20 months ago, # ^ |   +1 To me it was easier to see it like this.Suppose the input was 011101000100, then you build the "balance" array of it, which is what the editorial mentioned: s: 0 1 1 1 0 1 0 0 0 1 0 0 b: 1 0 -1 -2 -1 -2 -1 0 1 0 1 2 The last number in the balance array, $bal(n)$, is going to be a "delta", and you can see that in the next iteration of the input the balance array will be the same, only delta units higher, like this: s: 0 1 1 1 0 1 0 0 0 1 0 0 b1: 1 0 -1 -2 -1 -2 -1 0 1 0 1 2 b2: 3 2 1 0 1 0 1 2 3 2 3 4 b3: 5 4 3 2 3 2 3 4 5 4 5 6 From here you can see that from each position $i$ the numbers you can reach are $bal(i) + \delta \times k$, where $\delta = bal(n)$, for some $k \geq 0$.You also need to be careful of two things. What if the delta is 0? then the balance array is going to repeat itself to infinity, so if the $x$ is in the initial balance, then the answer is -1, and if it's not it's 0. Lastly, how many times will $x$ appear? well for each position $i$, $x$ can be reached 0 or 1 times. If it can be reached more than once, that immediately means delta is 0, so the answer is -1. You can check if $x$ can be reached from an initial balance $bal(i)$ easily using modulo or the formula in the editorial.
•  » » » 20 months ago, # ^ |   0 Thanks for helping!
•  » » » 20 months ago, # ^ |   0 Amazing explanation!
•  » » » 11 months ago, # ^ |   0 Amazing explanation. THANK U SO MUCH.
 » 20 months ago, # |   +4 "So let's make a sweep line on val from 1 to n+1 while trying to maintain all answers for each prefix pos". What does making a sweep line mean?
•  » » 20 months ago, # ^ | ← Rev. 4 →   0 It means we reconceptualize the $val$ dimension as physical time, and find a way to transition our program's state from $val = x$ to $val = x + 1$ (so like a line "sweeping" over that dimension over time). Working it out as in the editorial reveals that we want an array that we can do range additions and range minimums quickly, which can be implemented by a lazy-propagating segment tree.
 » 20 months ago, # |   0 Thanks guys for the editorial. By the way. Happy Lunar New Year ! 
 » 20 months ago, # |   +13 F says: ** Calculating the number of ways to take K elements from an interval [L,R) in sorted order can be reduced to calculating the number of ways to compose K as the sum of R-L non-negative summands (order matters). **, but must be the number of ways to compose R-L as the sum of k non-negative summands (order matters)
 » 20 months ago, # |   0 can anyone please optimize this code ? thanks in advance. this is my submission
 » 20 months ago, # |   +1 REGARDING QUESTION D can this question be solved by taking prime factors of m and then by inclusion and exclusion of factors of these prime numbers?
 » 20 months ago, # |   0 In the tutorial of problem B, $j$ should be replaced by $bal(j)$
 » 20 months ago, # |   0 Hello guys! Can anyone explain me solution for Problem E in much easier way(I tried reading every comment but no help).Also what does val,pos in solution signify? It would be great if someone explains with a small example Thank you!
 » 20 months ago, # | ← Rev. 3 →   0 Can anyone help me to find out the bug of my solution? Problem: 1295E - Permutation Separation Code/** * “Experience is the name everyone gives to their mistakes.” – Oscar Wilde * * author : prodipdatta7 * created : **/ #include #include #include // #pragma GCC optimize("Ofast") // #pragma GCC target("avx,avx2,fma") // #pragma GCC optimize("unroll-loops") using namespace std ; using namespace __gnu_pbds ; #define ll long long #define ld long double #define ull unsigned long long #define pii pair #define pll pair #define vi vector #define vll vector #define vvi vector> #define debug(x) cerr << #x << " = " << x << '\n' ; #define rep(i,b,e) for(__typeof(e) i = (b) ; i != (e + 1) - 2 * ((b) > (e)) ; i += 1 - 2 * ((b) > (e))) #define all(x) x.begin() , x.end() #define rall(x) x.rbegin() , x.rend() #define sz(x) (int)x.size() #define ff first #define ss second #define pb push_back #define eb emplace_back #define mem(a) memset(a , 0 ,sizeof a) #define memn(a) memset(a , -1 ,sizeof a) #define fread freopen("input.txt","r",stdin) #define fwrite freopen("output.txt","w",stdout) #define TN typename typedef tree , rb_tree_tag, tree_order_statistics_node_update > ordered_set; typedef tree , rb_tree_tag, tree_order_statistics_node_update > ordered_multiset; /* Note : There is a problem with erase() function in ordered_multiset (for less_equal tag). lower_bound() works as upper_bound() and vice-versa. Be careful to use. i) find_by_order(k) : kth smallest element counting from 0 . ii) order_of_key(k) : number of elements strictly smaller than k. */ /*###############-> Input Section <-###############*/ template inline void Int(T &a) { bool minus = false; a = 0; char ch = getchar(); while (true) { if (ch == '-' or (ch >= '0' && ch <= '9')) break; ch = getchar(); } if (ch == '-') minus = true; else a = ch - '0'; while (true) { ch = getchar(); if (ch < '0' || ch > '9') break; a = a * 10 + (ch - '0'); } if (minus)a *= -1 ; } template < TN T, TN T1 > inline void Int(T &a, T1 &b) {Int(a), Int(b) ;} template < TN T, TN T1, TN T2 > inline void Int(T &a, T1 &b, T2 &c) {Int(a, b), Int(c) ;} template < TN T, TN T1, TN T2, TN T3 > inline void Int(T &a, T1 &b, T2 &c, T3 &d) {Int(a, b), Int(c, d) ;} template < TN T, TN T1, TN T2, TN T3, TN T4> inline void Int(T &a, T1 &b, T2 &c, T3 &d, T4 &e) {Int(a, b), Int(c, d, e) ;} /*###############-> Debugger <-###############*/ #define error(args...) { string _s = #args; replace(_s.begin(), _s.end(), ',', ' '); stringstream _ss(_s); istream_iterator _it(_ss); err(_it, args); } void err(istream_iterator it) {cout << endl ;} template void err(istream_iterator it, T a, Args... args) { cerr << *it << " = " << a << ' ' ; err(++it, args...); } /*###############-> Constraints <-###############*/ const int N = (int)2e5 + 5 ; const int maxN = (int)1e6 + 6 ; const ll Mod = (ll)1e9 + 7 ; const int inf = (int)2e9 ; const ll Inf = (ll)1e18 ; const int mod = (int)1e9 + 7 ; inline int add(int a, int b, int mod) {a += b ; return a >= mod ? a - mod : a ;} inline int sub(int a, int b, int mod) {a -= b ; return a < 0 ? a + mod : a ;} inline int mul(int a, int b, int mod) {return (ll)a * b % mod ;} /*...... ! Code starts from here ! ......*/ int a[N], b[N] ; ll L[N], R[N] ; int main() { // ios_base::sync_with_stdio(false) ; // cin.tie(NULL) ; cout.tie(NULL) ; int test = 1 , tc = 0 ; //Int(test) ; while (test--) { int n ; Int(n) ; for(int i = 1 ; i <= n ; ++i){ Int(a[i]) ; } for(int i = 1 ; i <= n ; ++i){ int x ; Int(x) ; b[a[i]] = x ; } set < int > extra ; ll sum = 0 ; for(int i = 1 ; i <= n ; ++i){ while(sz(extra) > 0 and *extra.begin() <= i){ sum -= b[*extra.begin()] ; extra.erase(extra.begin()) ; } if(a[i] > i)sum += b[a[i]], extra.insert(a[i]) ; L[i] = sum ; } extra.clear() ; sum = 0 ; for(int i = n ; i >= 1 ; --i){ while(sz(extra) > 0 and *extra.rbegin() >= i){ sum -= b[*extra.rbegin()] ; extra.erase(*extra.rbegin()) ; } if(i > a[i])sum += b[a[i]], extra.insert(a[i]) ; R[i] = sum ; } ll res = min(b[a[1]], b[a[n]]) ; for(int i = 1 ; i < n ; ++i){ res = min(res, L[i] + R[i + 1]) ; } cout << res << '\n' ; } return 0 ; }  ApproachFor every prefix of from 1 to i, I calculate the dollar needed to make this segment fully covered with only elements less or equal to i (stored this result to L[i]). The same process for every suffix of the array and stored the result to R[i]. Then for all possible partitions from 1 to n, I calculate the minimum one.
•  » » 20 months ago, # ^ |   0 Yeah, I tried in the same way, I wonder why too.
 » 20 months ago, # |   0 In problem B , How is bal(n) defined ? What does it mean ? I'm unable to understand the tutorial please help !!!
•  » » 20 months ago, # ^ | ← Rev. 2 →   0 balance of a string is difference between number of zero and number of one containing this string. balance = count_0 — count_1. where count_0 is number of zero and count_1 is number of 1. Let str = "01001000", then balance of this string, balance=6-2=4. similarly balance of "1010001111" is 4-6=-2.you have to find number of prefix(in concatenation of s) can possible which balance equal to x.  let s = "10000" and x = 6. then ans = 2. balance(s)=3 after one concatenation of s, t=ss = 1000010000, balance of (ss) = 6(one prefix of ss and it is not possible to find a prefix of ss which balance is equal to 6). after two concatenation of s, t=sss=100001000010000, if we take prefix of length 12 then balance of 100001000010 = 6. and it is not possible to find any prefix after concatenation of s. so ans = 2.
•  » » » 20 months ago, # ^ |   0 Thanks a lot !!
 » 20 months ago, # |   0 Can anybody help me with the following?"Otherwise for each such j there is at most one k satisfying bal(j) + k.bal(n) = x ?
•  » » 20 months ago, # ^ |   0 We look at the string in iterations. One iteration is one time copy the string s to the end of the whole infinite string.If the balance for the string s bal(n)!=0, then it is so that the balance at a position j is at most once equal to x in all iterations.This is so because the balance at a position j changes from iteration to iteration by bal(n), and because it changes, it can be equal to x only once.That one time is the k-th iteration. To find the answer, we count the positions j where such a k exists.
 » 20 months ago, # |   0 Can anybody help me figure out why my DP solution for E is wrong ? dp[i] means the minimum cost if I choose there is i elements in the first set. Considering array a is a permutation, so there is exactly [1, i] in the first set if it is "good", am I right? I wrote my solution based on that. Here is my submission. 70131818 Thanks!
•  » » 20 months ago, # ^ |   0 Sorry, never mind this, I figured it out already.
•  » » » 20 months ago, # ^ |   0 Can you explain where was the problem? My approach is similar with yours and I have the same wrong answer on 10th test case (69928822).
•  » » » » 20 months ago, # ^ |   +3 We miss many situations, if we split the array into [1, k] and [k+1, n] at first, the "good" array after we move the elements may not as the same length as the original(k in the first and n-k in the second, this is nay not the minimum). That is the point. So naive but right solution must be two loops, one is the pos to split, another is the length(or val).
•  » » » » » 20 months ago, # ^ |   0 Thanks!
 » 20 months ago, # |   0 Problem A is almost same with 774C - Maximum Number.
 » 20 months ago, # |   +3 Can anybody help me please: I cannot understand why in problem E we cannot compute L and R arrays as well as in prodipdatta7' solution in such way: Let's consider given permutation P and sequence 1,..., n — denote as N; current sum for L — denote as sum; set S. For i from 1 to n — 1: If k > i such that P(k) = i then: S.insert(i); sum += a(i) (- function a(x): cost of x in P) If P[i] belongs to S then: sum -= a(P[i]); S.erase(P[i]). Such approach fails on 10th test.
•  » » 20 months ago, # ^ |   0 I think that the following example can help:Input:42 4 1 38 6 9 7Correct output: 6Your output: 7The correct solution (total cost = 6):Step 1: Split the initial permutation into [2, 4, 1] and [3];Step 2: Move 4 from the first set to the second set (total cost = 6). The final sets are [2, 1] and [4, 3].Your solution (total cost = 7):Step 1: Split the initial permutation into [2, 4, 1] and [3];Step 2: Move 3 from the second set to the first set (total cost = 7). The final sets are [2, 4, 1, 3] and [].
•  » » » 19 months ago, # ^ |   0 Thank you very much !
•  » » 20 months ago, # ^ |   0 You're making the same mistake as https://codeforces.com/blog/entry/73467?#comment-578439
•  » » » 19 months ago, # ^ |   0 And you too !
•  » » » » 19 months ago, # ^ |   0 Yeah :')
 » 19 months ago, # |   0 in Problem D why m>1 ? I need explanation :( it's too hard
 » 16 months ago, # |   0 please help me with PROBLEM D THANKS IN ADVANCE
 » 15 months ago, # |   +5 E can also be solved using Ternary search.Solution link — here
 » 14 months ago, # |   0 C using Binary Search https://codeforces.com/contest/1295/submission/87246971
 » 13 months ago, # | ← Rev. 2 →   0 Problem D is just Insane. Since I found the editorial and all other comments quite tough to understand, here's my Detailed Beginner friendly approach. As Someone above said, this is what I tend to explain, a bit more clearly Perhaps.Step By Step Approach For D: Let gcd(a,m) = g. So, we can say a=g*k and m=g*l. Now Putting back a and m , gcd(g*k,g*l) = g. Obviously , we can say gcd(k,l)=1. Now looking closely, we need to find all x such that gcd(a+x,m)=g. means that in our answers, x should also be a multiple of g. So let x=y*g. Now, gcd(g*k + g*y , g*l) = g, or gcd(k+y , l) = 1. Now What could be the range of y ? See, we have x=y*g and xl, we can say temp = l*some_number + tmp%l . See, we can also say that gcd(temp%l,l)=1 . (See this step again). Now, we have established that we have a Range (of length l) [k....l.....k+l] to look for which of these have gcd()=1 with l, and for all those numbers z in this range greater l, we can simply replace them by z%l. So in the end, we have our Range as [1...l] only. Now to find all the numbers in [1,l] which are coprime with l, just use the Totient Function in O(sqrt(n) Code.
•  » » 12 months ago, # ^ |   0 You tried to explain it well but it is not a good explanation at all.
 » 12 months ago, # |   0 I really liked Problem E