### awoo's blog

By awoo, history, 20 months ago, translation, 1476A - K-divisible Sum

Idea: vovuh

Tutorial

1476B - Inflation

Tutorial

1476C - Longest Simple Cycle

Tutorial

1476D - Journey

Idea: BledDest

Tutorial
Solution 1 (BledDest)
Solution 2 (BledDest)

1476E - Pattern Matching

Idea: BledDest

Tutorial
Solution 1 (awoo)
Solution 2 (awoo)

1476F - Lanterns

Idea: BledDest

Tutorial
Solution (BledDest)

1476G - Minimum Difference

Idea: Neon

Tutorial
Solution (Neon)  Comments (66)
 » Problem E was beautiful! Thanks :D
 » Finally a contest with less ad-hoc!
 » past 2 contests have realised me that i'm more noob at maths than programming :(
•  » » me too
•  » » » Me Tooooooooooooo
 » Great Contest! Thanks
 » Too many Hacks for problem A . My solution was also hacked .
 » great contest. life is loop.
 » contest is good but statement of E was awful
 » Isnt problem D much easier than problem C?
•  » » that's what she said : | : |
 » In problem C , How the value of the following test case will be 6? please explain.. input 3 2 4 2 -1 2 4 -1 2 1 output 6 
•  » » Excuse the use of Paint lol, but it looks something like this (the blue edges are the ones forming the cycle): •  » » » thanks !!
•  » » » Can u please have a look why my solution for C is giving wrong answer for first test case , subtest 3 :( https://ideone.com/VlyDdV
 » I think Problem D is simpler to use the Disjoint-set. Am I right?
•  » » It can be done simply by moving from current city to Right to find the largest pattern of RL...RL or RL...RLR and similarly on left from current city to left as LR...LR or LR...LRL and length of both the patterns + 1 will be the max cities visited from current cityYou can see my solution : https://codeforces.com/contest/1476/submission/106090614
•  » » » I did the exact same thing.. but my solution didn't work. Any edge cases I might be missing? My code
 » 20 months ago, # | ← Rev. 2 →   This was a very nice contest after a while. Kudos to the authors, each and every problem in the contest that I solved / up-solved taught me something new. Hope for more such rounds :)
•  » » definitely an alt :rofl:
•  » » » Lol I took the idea from here
 » 20 months ago, # | ← Rev. 2 →   Can someone help me figure out the error of code for submission below? My Code Here is my code for problem F. It gets wrong answer on test 5, case 1259. However, I can't get that sample.
 » Can Anyone tell me how to solve question D recursively and doing memoization?
•  » » Not by recursive dp, but Errichto explained the iterative dp approach in his yesterday's stream
•  » » » No like I am asking like can we solve it that way(recursive dp) like I am stuck and unable to move forward in my approach.
•  » » » » You can solve it by recursion just reverse the starting position
•  » » check my solution using memoization https://codeforces.com/problemset/submission/1476/128826229
 » For B, can anyone explain why there's a k-1 added to 100ll * p[i] - k * pSum?
•  » » It is basically done to take ceil of the value.Let me make it more clear — Ceil(a/b) == (a+(b-1))/b You can check this by taking two cases - a = k*b. Both functions return k a = k*b + x (0
•  » » » but in editorial he didn't mention the ceil thing i understand it from the code but i dont understand the purpose of it, if u can explain please
•  » » » » It is mentioned in the editorial that -$x \ge \left\lceil \frac{100 \cdot p_j - k \cdot (p_0 + \dots + p_{j - 1})}{k} \right\rceil$Notice the bracket, that is for denoting ceil function.Now the next question is why do we even need that — because x is a non negative integer and right hand side acc. to maths will return a floating value (which may not be integer). Let's take an example — You know x is an integer and after solving RHS you get - $x \geq 1.2$So definitely you know you should pick next integer (ceil value) as answer i.e. x = 2.
•  » » » why we need to take the ceil.
•  » » » Thank you for clarifying that. However, when I use ceil(100ll * p[i] - k * pSum), it says Wrong Answer. What is the reason for this? Also no one has used the in-built ceil function in their code. Please clarify if possible.
•  » » » » You can have a look at my solution. Hope you it helps :) The way I have used the ceil function is more intutive. ~~~~~ #include #define fst ios_base::sync_with_stdio(false);cin.tie(0) #define all(x) (x).begin(),(x).end() #define int long long #define rep(i,a,b) for(int i=a;ib;i--) #define sz(x) (int)((x).size()) using namespace std; void solve(){ int n,k; cin>>n>>k; vector p(n); rep(i,0,n){ cin>>p[i]; } double t = (double)k/100; int s = p,ans = 0,diff = 0; rep(i,1,n){ double f = (double)p[i]/s; if(f > t){ int x = ceil((double)p[i]*100/k); diff = (x-s); ans += diff; s += diff; } s += p[i]; } cout<>t; while(t--) solve(); } ~~~~~
 » A constant optimization for 1476G - Minimum Difference -- observing that the upper bound of value $c$ always equals to the lower bound of $(c + 1)$, we can store only the lower bounds (but not both as in the model solution), You can see my submission 106048247 for the detail.
•  » » There is no need of segment trees for 1476F - Lanterns. We need only two operations: The one is to query $\max\{(j + p_j), \dots, (i + p_i)\}$ for increasing $i$. The other one is to find the minimum $j$ where $\mathrm{dp}[j] \geq i - p_i - 1$. The two operations can be supported by two standard (monotonic) stack and std::lower_bound. My submission 106219219.
•  » » » forget about this stupid problem is your profile photo-real ??
•  » » » » Sure. What's your point?
•  » » » » » First of all, I have to wait for 10 minutes to comment, and second, you are cute (are you interested in unrated guys ??)
•  » » » » » » Can ya bitches stop being creepy to random ladies over the internet?
•  » » » » » » » you created an account just to comment on this. I respect that.
•  » » » Hello, can you take a look at my submission for problem F Lanterns.I have not used a segment tree but a sparse table and for each lantern(let us say i) that points to the left, I have kept a pointer to the last lantern(let us say j) such that the lanterns 1 to j cover some continuous segment of lanterns not covered by the lantern i.I am failing at some 1200+ subtest of test case 5 and will be much thankful if you can help me point out where my algorithm fails. Or if you can provide some test case where it fails?Any help will be much appreciated. Thanks!
 » in the numerator why x = max(x, (100ll * p[i] — k * pSum + k — 1) / k); k-1
 » For E, why can't I topsort it?
 » 20 months ago, # | ← Rev. 3 →   BledDest problem E : can there be a pattern which matches non of given string?i meant redundant pattern.Edit : yup!! that was silly,
 » In E you can also find a match converting the string to integer. The number of possible strings is $27^k$, so every pattern can be indexed.
 » couldn't you also have used two pointers in problem D (journey)?using two other pointers to find the longest distance you can travel to the left/right, and calculating if you are able to travel in the direction or not.the answer would be one plus the distance you can travel to the right and the distance you can travel to the left, as you would be able to travel back in any point in timemy solution
 » Question for problem EInput 4 4 4 aaaa aaaa aaaa aaaa aaaa 2 aaaa 2 aaaa 2 aaaa 2 The solution's output is "NO", but I think 2 1 3 4 is right, do I understand the problem wrong?
•  » » 20 months ago, # ^ | ← Rev. 2 →   Your input is not correct. All patterns should be pairwise distinct.
•  » » » Oh, many thanks! :)
 » 17 months ago, # | ← Rev. 2 →   For problem D, can someone let me know , how can i optimise it? i am getting tle on test case 14 https://codeforces.com/contest/1476/submission/113641003
 » in solution of problem b x = max(x, (100ll * p[i] — k * pSum + k — 1) / k); why we need to add k and minus 1 here k * pSum + k — 1
 » In the first problem, I did the same thing with ceil function but it threw wrong answer...How is it possible to get the correct answer by just using ceil in a different mathematical way as shown in tutorial??
•  » » I think it's the floor function that we have to take. If you are using c++, you simply have to do the calculation as to store a floating point number in an int data type, the number is automatically floored.
»

# include<bits/stdc++.h>

using namespace std;

# define fo(i,l,r) for(int i=l;i<r;i++)

void solve(); int main() {

int t;
cin>>t;

while(t--)
{
solve();

}
return 0;

} void solve() { long long n,k; cin>>n>>k; if(n==k) { cout<<1<<endl; } if(n>k) { cout<<2<<endl; } if(n<k) { cout<<ceil((long double)(k)/(long double)(n))<<endl; } }  y is my code wrong for a?

•  » » Anyone, please explain the binary search approach for 1476A - K-divisible Sum
•  » » » 16 months ago, # ^ | ← Rev. 2 →   //K-divisible Sum int main(){ long long int n,k,t,max,min; cin>>t; while(t--){ cin>>n>>k; if(n<=k){ if(k%n==0) cout<
•  » » » » I asked for Binary Search!!
 » what is cf in problem A??
 » Problem B : Inflation. int n =sc.nextInt(); double k =sc.nextDouble(); `double a[] = new double[n]; for(int i=0;i
 » Can anybody explain B? I couldn't understand even after reading the tutorial. Thank you in advance.
 » Can D be solved using binary search?Submission Getting TLE on test14.
 » In the second problem i.e inflation, for the test case : 4 1 20100 1 202 202why is the answer 99? Shouldn't it be zero coz all the elements satisfy the given condition? Please help me out. Thank you!!
•  » » It shouldn't be zero...Check the condition like that :-p[i]*100 <= k*sumWhere sum = p+p+...+p[i-1]
 » My code to F Lanterns fail at some 1200+ test of test case 5. Can someone take a look at my submission and guide me to where my code's failing? Or provide a test case where it fails?Help will be much appreciated. Thanks!
 » How A is binary search? somebody, please explain.