### Edvard's blog

By Edvard, history, 4 years ago, translation,

Hello, Codeforces!

Educational Codeforces Round 13 will take place on 13 June 2016 at 19:00 MSK for the first and the second divisions. Almost two months passed from the previous round. That is due the next reasons: 1) I coordinated regular CF-round at the end of April; 2) about whole CP community were busy with preparing and competing in ACM ICPC WF in May; 3) at the beginning of this month I start to work at AimTech (I hope that I'll have enough time to continue prepare ERs).

<It's need to read at least once maybe you'll find something interesting>

The round will be unrated for all users and it will be held with extented ACM ICPC rules. You will have two hours to solve six problems. After that you will have one day to hack any solution you want. You will have access to copy any solution and test it locally.

If you have ideas for some problems or maybe already prepared problems that you can't use in rounds or official competitions, you can write to me.

It seems that it is harder to invent interesting simple problems (like A and B) than difficult ones. So don't be afraid to suggest interesting simple or very simple tasks (of course the difficult tasks are also needed). Please send only the problems for which you know the solution with clear statement (the story is not required). And also please add one or two samples to make the problem statement more clear.

</It's need to read at least once maybe you'll find something interesting>

The problemset was suggested by Codeforces users. The problem А was suggested by user Abdrakhman Ismail Ismail_A. The problem B was suggested by Arthur Jaworski KingArthur. The problem C was suggested by Sheikh Monir skmonir. The problem D was suggested by Zi Song Yeoh zscoder (there are a lot of unused his problems). The problem E was suggested and prepared by Alexey Dergunov dalex. The simpler version of the problem F was suggested by AmirMohammad Dehghan amd.

Thanks a lot to them and all others who are sending the problems! The number of unused problems are increasing. If I didn't miss anything I already replied to all who sent me the problems at least 5-6 days ago. Please be patient if your problem was not used a long while.

As I said the problem E is prepared by Alexey Dergunov dalex. All other problems was prepared by me (Edvard Davtyan). Thanks to Tatiana Semyonova Tatiana_S for checking the English statements. The problems was tested by users suggested them, respectively: Abdrakhman Ismail Ismail_A, Arthur Jaworski KingArthur, Sheikh Monir skmonir, Zi Song Yeoh zscoder, Alexey Dergunov dalex and AmirMohammad Dehghan amd. Thanks a lot to all of them!

I hope you will enjoy the problems! Previous time the problems were too hard. I've tried to fix that. The problems should be simpler than usual.

Good luck and have fun!

UPD: The round is finished. The editorial is published.

It's the first summer round :-)

• +185

 » 4 years ago, # |   +42 Where is Delinur?
•  » » 4 years ago, # ^ |   +2 They don't need her since Edvard is a native Russian speaker and he also knows English (obviously!) and Tatiana Semyonova has checked English statement.
•  » » » 4 years ago, # ^ |   +19 Usually I'm translating the problems by myself (it helps me to improve my English) and the interpreter (Maria and now Tatyana) just checking the problem statements and making fixes.
•  » » » » 4 years ago, # ^ |   +16 Interpreter — это тот, кто устно переводит. В данном случае наверное надо было использовать translator. By нужно убрать перед myself. Дальше у вас со временами все перепутано
•  » » 4 years ago, # ^ |   +127 Actually, Maria left the project, she asked to convey greetings and best wishes to all people on Codeforces! Tatyana Tatiana_S Semenova agreed to help us with English :-)
•  » » » 4 years ago, # ^ |   +16 I did not know her handle and could not find it. Now I'll add it to the post.
•  » » » 4 years ago, # ^ |   -28 Mike, I want The Educational Codeforces is rated *. *
 » 4 years ago, # |   -14 Couldn't give the previous one....had been waiting for this one for long! Excited! Hoping for a matrix exponentiation problem...I never solved it in a contest!
•  » » 4 years ago, # ^ | ← Rev. 2 →   +53 participate to kiya nhi
•  » » 4 years ago, # ^ |   +1 Looks like you still haven't solved a matrix exponentiation problem in a contest. :P I solved my first today :D
•  » » » 4 years ago, # ^ |   0 Could easily be solved with simple fast exponentiation without forming a matrix. Result = (exp(a,n)*x + b*(exp(a,n)-1)%M * exp(a-1,m-2,m))%M , a not equal to 1 (x+b*n)%m if a = 1
•  » » » » 4 years ago, # ^ | ← Rev. 2 →   0 Result = (exp(a,n)*x + b*(exp(a,n)-1)%M * exp(a-1,m-2,m))%MCan you explain what happens there? I have found formula: a^n*x + b((a^n-1)/ (a-1))And this is only point which I don't understand.
•  » » » » » 4 years ago, # ^ | ← Rev. 2 →   +3 (a/b)%MOD=(a%MOD*(modular mult. invserse of b modulo MOD))%MOD See this for more:https://github.com/ishan-nitj/Competitve-Programming/blob/master/Number%20theory/Modular%20arithmetic.pptx
 » 4 years ago, # |   +42 "It's the first summer round"No here, I'm freezing
 » 4 years ago, # | ← Rev. 2 →   +2 I know this if Off topic. But Believe me, my rating was 1905. Any changes in rating system?
•  » » 4 years ago, # ^ |   0 See the standing http://codeforces.com/contest/677/standings I did this contest unofficial.
•  » » 4 years ago, # ^ |   0 check this: http://codeforces.com/blog/entry/44214
 » 4 years ago, # |   +14 Is this round being delayed for 10 minutes?
•  » » 4 years ago, # ^ |   0 Yes I think so.
•  » » 4 years ago, # ^ |   +5 At least.
•  » » 4 years ago, # ^ |   -18 Наверное,технические проблемы.
•  » » 4 years ago, # ^ |   +19 Looks like it. Now I get to properly finish my lunch xD
 » 4 years ago, # |   +29 Well, I know what is needed to solve F and I also know that I can't code it so I quit, good luck! :D
•  » » 4 years ago, # ^ |   0 Can you tell what was the idea behind solving F??
•  » » » 4 years ago, # ^ |   +1 It can be solved like this http://codeforces.com/blog/entry/22031, look at the comments :)
•  » » » » 4 years ago, # ^ | ← Rev. 2 →   0 I did it same way but it timed out. My solutionI guess it timed out because of SQRT DECOMPOSITION .
•  » » 4 years ago, # ^ |   +39 That's why you're purple. I used to had this "well, it's obvious this problem can be solved by persistent 2D segment trees with heavy light decomposition built on linkcut trees, hire monkeys to code it for me" and walk away proudly for coming up with such a 'brilliant' solution, but I discovered that's not the way one should follow. In half of cases it turns out such problem has some nice tricky solution using very simple techniques and in half of cases it turns out solution is in fact what I thought, but still a lot of people have no troubles with implementing it which is a sign that I should definitely improve my coding skills in that area. Treat contests (especially educational rounds) as opportunities to learn not just the place where you solve problems which you already know how to solve.
•  » » » 4 years ago, # ^ |   +45 After becoming red approach changes, right? :p
•  » » » » 4 years ago, # ^ |   +2 Looks like he hired monkeys to code it for him, or coded all the stuff like a monkey himself.This way he can be smart in the discussion: Yes, think carefully about nice and tricky ideas and maybe you can become red (like me) someday. While copy pasting ton of stuff on every problem in 2 minutes, get the whole problemset done in 10 minutes and red color very quickly :P
•  » » » » » 4 years ago, # ^ | ← Rev. 2 →   +13 I didn't want to say "I invent tricky ideas, so I am red", I wanted to say "Stop giving up, that is not the right way to progress" and "Sometimes appropriate way to solution leads through tricky ideas and sometimes it leads through fighting one's weaknesses with coding something, and surely it doesn't lead through being satisfied with coming up with complicated solution". "I am not able to do this, so I won't even try" attitude is the worst way to improve your skills.
•  » » » » 4 years ago, # ^ |   0 What I said here and copying prewritten code are kinda irrelevant. "hire monkeys to code it for me" was the key part. Main point here is that one definitely should not treat coming up with solution as all the logical difficulty and implementation as dirty duty one can omit and be satisfied (as I used to on high school). Another thing is that as long as code is prewritten by me and contest rules allow me to freely copy-paste it then if it helps me getting fast AC I feel the right to be fully satisfied with it — such scenario is rather the exact opposite to scenario of getting no AC at all which we are talking about.
•  » » » » » 4 years ago, # ^ | ← Rev. 3 →   +10 Edit. The reply should be to your upper comment. I got confused by the comments tree :)My comment refers to "That's why you're purple".Basically it suggests that red coders either find a nice and tricky idea or have such a good coding skills that can implement a complicated idea quite fast. Which means red coder = very smart or skillful and not red = !(smart or skillful) = !smart & !skillful.You forgot to add that you also use additional approach. You got such a huge library, because of spending a lot of time on problem solving and practicing/participating in many contests, that you can just copy-paste most of the complicated stuff.This changes things a lot as it means red coder = ((1) very smart or (2) skillful) and (3)having a lot of practice and a lot of libraries.And in this case not red means !(((1) | (2)) & (3)) so smart and skillful meets that criteria.This was example of discrimination by cf color. I don't know why do you think that once you are red, you can treat not red as somehow worse and less talented.I think that being high rated in short competitions really means 2 things: you are extremely smart or you can afford to spend tons of time on participating in the contests and solve a lot of problems 12 hours per day. This way you can become a really skillful and have enormous library of code, which gives you additional advantage in such type of contests.
•  » » » » » » 4 years ago, # ^ |   0 Maybe "That' why you're purple" was oversimplification, because at any point I didn't want to address the actual smartness or abilities to code some particular thing, so I would like to cut out part of the discussion regarding to being smart, having a lot of practice, having developed library etc. which are of course important factors of someone's colour, but they were not what I was going to point at what may have been a reason for a little misuderstanding.Only thing I wanted to focus on was the attitude when facing problems. From my own experiences I can say that difference between purple me and red me is surely also a lot of practice, but also very importantly revolutionizing my way of thinking. No matter of someone's current abilities to code and smartness, "I am not able to do this, so I won't even try, good luck" attitude is a place for severe improvements (no matter whether "I am not able to do this" part relates to coming up with solution (which connected with "so I won't even try" never has been my point of view) or coding a solution (which was exactly exactly very often my point of view in past and I am not happy with this, but fortunately it is no longer the case)). My initial comment's main purpose was in fact to be a purely motivational one.Btw on a completely irrelevant note, you made it seem like copying prewritten code is essential part of today's competitive programming. In fact (apart from template) I copy some codes from library in approximately one in 20 problems.
•  » » » » » » 4 years ago, # ^ |   +16 My personal red experience is that "whatever you say can be used against you", that is, no matter how careful you are, something you say is going to be perceived as arrogant by someone (hell, some people told me they thought I was arrogant before they had the chance to talk to me!). So I'd say at least a large part of this discrimination you mention can be attributed to the lower-rated contestants themselves.That being said, here's a simplified version of Swistakk's statement:"Programming contests consist of coding and implementation, so if you want to be a very good contestant you need to practice both, not only one of them".Sounds like really good advice to me (and I should follow it more often, my implementation skills are crap)
•  » » » 4 years ago, # ^ |   0 Could you givgive an example of such a problem (requiring all techniques you mentioned)?
 » 4 years ago, # | ← Rev. 2 →   0 what is wrong with my code it is failing on test 5 http://sprunge.us/iFNf? THe code is for problem D.
•  » » 4 years ago, # ^ |   0 Same is happening for my case also.
•  » » 4 years ago, # ^ |   0 I think, we cannot simply divide like this: second = (B*((tmp-1l)/(A-1l)))%MOD;Probably there is a smarter way to deal with modular division.
•  » » 4 years ago, # ^ | ← Rev. 2 →   +6 (a/b) mod m is not equal to a mod m / b mod m so you cant divide by (a-1) so easily. you should use modular inverse
•  » » 4 years ago, # ^ | ← Rev. 2 →   0 Instead of dividing (tmp-1) by (A-1) directly, (tmp-1) can be multiplied with the modular inverse of (A-1). UPD: I did this but my solution got hacked anyway.
•  » » 4 years ago, # ^ |   +8 Here Scroll down to the modular inverse part!
•  » » » 4 years ago, # ^ |   0 Thanks.
•  » » 4 years ago, # ^ | ← Rev. 2 →   0 By Euler's theorem, you can use ((divisor) ** (mod - 2)) % mod to divide if mod is prime. In this case, divisor would be (a — 1) and mod would be 10 ** 9 + 7.https://en.wikipedia.org/wiki/Modular_multiplicative_inverse
•  » » » 4 years ago, # ^ |   0 oooh no I have used this technique many times (problem 300C)but i did not use it this time :'(
 » 4 years ago, # |   +7 That N = 1 case in E. -_-
•  » » 4 years ago, # ^ |   0 Same :/
 » 4 years ago, # |   0 How to solve problem E?
•  » » 4 years ago, # ^ |   0 i think dynamic programming, like hamiltonian cycle but im not sure, i couldnt make it pass test 4http://codeforces.com/contest/678/submission/18433012
•  » » 4 years ago, # ^ |   0 I tried DP, but its complexity is bad.
•  » » 4 years ago, # ^ |   +5 You need to find an order which maximizes your probability of winning. This is a standard Bitmask DP. My solution : code
•  » » » 4 years ago, # ^ |   0 What to search for to get this standard dp problem?
•  » » » 4 years ago, # ^ |   0 Your code is a little messy , so can you tell me the DP states you used?
•  » » » » 4 years ago, # ^ |   +4 Lets define DP[mask][prev_winner] as the max probability such that we have covered people in mask and prev_winner is our winner. Now we try N * (N — 1) possibilities for first 2 position and try to find the max ans. Transition is : if prev_winner = 0: DP[mask][prev_winner] = max(prob[prev_winner][i] * DP[mask | (1 << i)][prev_winner]) for all i's which we have not seen. else: DP[mask][prev_winner] = max(prob[prev_winner][i] * DP[mask | (1 << i)][prev_winner] + prob[i][prev_winner] * DP[mask | (1 << i)][i]) for all i's which we have not seen. I hope this helps.
•  » » » » » 4 years ago, # ^ |   0 Now we try N * (N — 1) possibilities for first 2 position and try to find the max ans. I thought we have to consider two disjoint subsets and use their maximum values for the union of these subsets. I can't prove why we only need first two positions. I'm missing something very obvious, possibly.
•  » » » » » 4 years ago, # ^ |   +3 I don't understand these formulas:"DP[mask][prev_winner] = max(prob[prev_winner][i] * DP[mask | (1 << i)][prev_winner]) for all i's which we have not seen."It means that in order to cover people in mask you look at all the masks with one more people, you ask what is the probability that 0 will win among all these people and then you calculate the value for the mask with the smaller amount of people. It looks like your final state is dp[0][0]?
•  » » » » » » 4 years ago, # ^ |   0 Final state for DP is dp[(1 << n) — 1][0]. I add one more person into mask and ask what is the probability that the person I want to win is the winner. And I split the dp based on whether I have seen 0 or not. So above formula is for the case when I have seen 0 (what is the probability that 0 is the winner when I add one more person into mask). Other formula covers the second case as both of them can win.
•  » » » » 4 years ago, # ^ |   +3 A simple way is to set dp[mask] = best probability for Ivan to win among people with bit=1 in the mask.18433677
•  » » » » » 4 years ago, # ^ |   0 How do you prove that only mask is important? I believed that the last winner is also important, but stress-test of your solution says that it isn't.
•  » » » » » » 4 years ago, # ^ |   0 I choose two fighters to move between dp states, maybe this confuses you.So basically for a given mask we can independently get the best probability of Ivan to win. To compute this, we take maximum over all possible choices for next fight (choice of two fighters, possibly including Ivan).
•  » » » » » » » 4 years ago, # ^ | ← Rev. 3 →   +5 That's a nice solution, but it is very magical for me.If you choose the last 2 people it is against the rules, as you can choose only 1 last person.So if you are going to choose the last 2 people (i,j): Ivan had to win in the mask without j, so now you multiply that by the probability that i beats j (and we know that i already got beaten by Ivan, so Ivan beats the whole new mask this way). or Ivan had to win in the mask without i -> the same logic holds. I don't know how do the people come up with such ideas, but is there a way to do this problem more straight forward?Like you have the probability dp[mask] that Ivan wins the mask or dp[mask][winner] that winner wins the mask and you are selecting one player in each move? Despite being more straight forward, that solution would also reduce the complexity to O(n*2^n).Edit — it will reduce the complexity only in case with dp[mask] state.Edit2. Now I see that you are not choosing the last fight, as you can't do that. Ivan has to fight the last fight in each mask. You are choosing the best fight among all possible fights within the mask and you take the sum of 2 different outcomes of it. It is more clear now.
•  » » » » » » » » 4 years ago, # ^ |   0 Actually now I realized that I forgot that the winner from the last fight has to be chosen. That is, my solution assumes a tournament, where there are multiple fights with elimination in parallel.So I solved a different problem and that's why the solution seemed clear for me (and unclear for others).It is quite strange that this got AC.. Maybe it could be hacked? Though, intuitively, it would fall on large random tests, which I assume already exist in the set.Maybe this works because the strategy from the problem is indeed optimal? :)
•  » » » » » » » » » 4 years ago, # ^ | ← Rev. 3 →   0 Your solution works because:dp[mask] = maximum probability that Ivan wins the mask.If there is no Ivan in the mask dp[mask] = 0.If there is Ivan in the mask, you choose the best tournament in that fight. You have 2 cases here:a) You choose 2 fighters without Ivan and I explained that case above. That fight would happen in any but last position — my explanation covers that too. But to make it more clear: you don't care at which stage that fight would happen, the point is that the winner of that fight would be defeated by Ivan later.b) You choose Ivan and another fighter — that fight has to happen as the last one.So you evaluate the fight between 0 and i.So your formula will take dp[mask^1]*prob[i][0] and this is 0, because dp[mask^1] = 0 dp[mask^(1<
•  » » » » » » » » » 4 years ago, # ^ | ← Rev. 2 →   0 this explanation is wrong, lol
•  » » » » » » » » » 4 years ago, # ^ | ← Rev. 2 →   0 That's what I wrote in case a). In case b) you are adding the new candidate to the mask. The mask is already beaten by Ivan — so it will be the last fight with new candidate.
•  » » » » » » » » » 4 years ago, # ^ |   0 Are you sure every sequence can be made into a chain? For instance, what about 3 beats 4, 5 beats 6, 2 beats 3, 2 beats 5?And even if that transformation is possible, the sequence of fights is not determined in advance (because as you said you can change it depending on prior results), so you wouldn't necessarily know what transformation to use. It's very interesting that this solution works, but I think the explanation why is not that simple...
•  » » » » » » » » » 4 years ago, # ^ | ← Rev. 3 →   0 I'm not sure about a chain, but I can't see what is the problem with my explanation.It is clear that you choose the most profitable battle. If Ivan is engaged, it is the last battle, no matter what was the order of the other battles.If he is not engaged, that battle is not last, as the winner of it got already beaten by Ivan in the state we have calculated. So we can insert it everywhere, but the last position.Your example doesn't include Ivan and for such case the solution immediately outputs 0.
•  » » » » » » » » » 4 years ago, # ^ |   0 I was replying to dalex's explanation, not yours, which I only read now. As far as I can see, you don't address the requirement that the winner of the last fight has to be part of the next fight.
•  » » » » » » » » » 4 years ago, # ^ | ← Rev. 6 →   0 Because we already reached the discussion depth limit — it is hard to say to which answer was the reply.That requirement is addressed in the following way:If Ivan won the last battle, he obviously will be participating in the next one.Below part was edited:I got lost in one case.If you choose the battle between (i,j) and i won that battle. You know that in the dp[mask^(1<
•  » » » » » » » » » 4 years ago, # ^ |   0 I constructed a case by ffao, which ruined the explanation about chains: http://ideone.com/QYmfXx... or not? Look what it outputs for mask 31 (after 5 defeats 6).
•  » » » » » 4 years ago, # ^ |   0 My solution uses the same idea as yours, but I don't really know why it works! I just code it to see if it solved the problem, but I was skeptical. In my mask I store the participants that are dead, and try all possible pairs, and sum the combinations that result in only Ivan alive. The code turns out to be very simple but I don't know why it works! 18510404
•  » » » 4 years ago, # ^ |   0 can you tell me what i did wrong here, please?http://codeforces.com/contest/678/submission/18433012
•  » » » » 4 years ago, # ^ |   +3 Reads comment and then realises that it's pointless.
•  » » 4 years ago, # ^ |   +1 I solved it using dp, Let f[s][i] be the probability that the jedi winns if s is the set of siths that are alive, and i the sith that won the last round. We can try over all possible siths j!=i, and over all possible outcomes (of the fight between i and j), of course we should chose the one that maximizes the probability that the jedi winns.
•  » » » 4 years ago, # ^ |   0 But don't you have to deal with two subsets each time?
•  » » » » 4 years ago, # ^ |   0 Why two subsets? As you can see my recurrence use just one subset. Note that the set of died siths is the complement of the alive siths
•  » » » » » 4 years ago, # ^ |   0 two mutually exclusive subsets , with one winner of each subset, fighting in the current round which covers union of both subsets. At least this is all I could come up with.
•  » » » 4 years ago, # ^ | ← Rev. 2 →   0 @Alei : I do nt get in ur dp how u are ensuring that 0th index is the last winner. could u pls elaborate how uve done that.. or how is it implicitly taken care of.?
•  » » » » 4 years ago, # ^ |   0 ok got it now didnt read the base condition carefully.. very nice code :)
•  » » » 4 years ago, # ^ |   0 Tnx for providing us with your clear and simple solution. :)
 » 4 years ago, # |   0 in problem E, how the sample gives 0.68?? Stuff that can happen so 1st person win are: 1 win 2, 1 win 3 1 win 3, 1 win 2 2 win 3, 1 win 2 3 win 2, 1 win 3 All this happen with 0.49333 probability. What am i missing?
•  » » 4 years ago, # ^ |   0 Question asks to find the maximum probability which comes from this order 2, 3, 1. 2 wins, 1 wins : 0.4 * 0.5 3 wins, 1 wins : 0.6 * 0.8 Total prob = 0.2 + 0.48 = 0.6
•  » » » 4 years ago, # ^ |   +13 Note that optimal choices can differ depending on the results of the previous battles. So talking about "order" is not correct.
 » 4 years ago, # | ← Rev. 2 →   -8 PROBLEM C: It is wrong with my code? #include using namespace std; int main() { int n,a,b,p,q; cin>>n>>a>>b>>p>>q; long long s=0; int na=0,nb=0,nab=0; na=n/a; nb=n/b; long long z=(a*b)/__gcd(a,b); nab=n/z; long long val= p>=q?nab*p:nab*q; s=(na-nab)*p+(nb-nab)*q+ val; cout<
•  » » 4 years ago, # ^ |   +3 z overflows try 1000000000 1000000000 1000000000 1000000000 1000000000
•  » » » 4 years ago, # ^ | ← Rev. 2 →   0 the solution change the data type of the input variables int a long long #include using namespace std; int main() { long long n,a,b,p,q; cin>>n>>a>>b>>p>>q; long long s=0; int na=0,nb=0,nab=0; na=n/a; nb=n/b; long long z=(a*b)/__gcd(a,b); nab=n/z; long long val= p>=q?nab*p:nab*q; s=(na-nab)*p+(nb-nab)*q+ val; cout<
•  » » » » 4 years ago, # ^ | ← Rev. 2 →   0 You can do: a / __gcd(a, b) * bTo avoid overflows as the division will be carried out at first
•  » » 4 years ago, # ^ |   -8 Why do you need __gcd()? What are you trying to achieve with the variable z?
•  » » » 4 years ago, # ^ |   +3 find the number of numbers divisible by two numbers given
•  » » » » 4 years ago, # ^ |   0 Interesting, I haven't thought about that. I've calculated that number with expression n / (a * b).It is good that the contest is not rated :)
•  » » » » » 4 years ago, # ^ |   0 the trouble is that overflows a correct code I found is this from the same approach cout << (n / a) * p + (n / b) * q- (n / (a * b / __ gcd (a, b))) * min (p, q) << endl; in which it no longer stored in a variable.
•  » » 4 years ago, # ^ |   0 Probably (na-nab)*p overflows, try (na-nab)*1ll*p (and same with q). Or simply use long long for all vars.
 » 4 years ago, # | ← Rev. 2 →   +4 Thanks, the problem really was easier than last time. Maybe you had to swap B and C. UPD. Take back a words about the B and C after start of hacking.
 » 4 years ago, # | ← Rev. 2 →   0 I sent two solutions for problem B that got OK. One of them was hacked, the other wasnt. But the table says I havent solved this problem. Why?
•  » » 4 years ago, # ^ |   0 Relax, the contest is not rated. Enjoy the moment =)
•  » » » 4 years ago, # ^ |   -19 I wouldnt allow anyone to hack my solution in a rated contest))))
 » 4 years ago, # |   +9 C was solved by 1500+. now it has become 900+. #HackEffect
 » 4 years ago, # |   0 Can someone tell me why my solution fails for C? int main(){ long long int a,b,c,d,e; int cnt=0; scanf("%lld%lld%lld%lld%lld",&a,&b,&c,&d,&e); long long int res = 0; long long int res1 =0; res= ((a/b)*d) + ( abs((a/b) - ((a/b+a/c)-(a/(b*c))) ) * e); res1= ((a/c)*e) + ( abs((a/c) - ((a/b+a/c)-(a/(b*c))) ) * d); if(res>res1){ printf("%lld",res); } else printf("%lld",res1); } 
•  » » 4 years ago, # ^ |   0 Compiler got confused by cnt and abs, so it gave up =)
•  » » 4 years ago, # ^ | ← Rev. 2 →   0 You can't just divide by (b * c), it should be GCD(b,c). Consider this input: 6 2 4 1 3 Your code gives 6 as an answer, where it should be 5. Edit Wrote 3 instead of 6, corrected.
•  » » » 4 years ago, # ^ |   +1 Not gcd, but lcm
 » 4 years ago, # |   0 My first hacking attempt and i hacked 15 solutions for problem C
•  » » 4 years ago, # ^ |   +27 You forgot to hack yourself))
 » 4 years ago, # |   0 How could problem D be solved using matrices?
•  » » 4 years ago, # ^ |   +1 a[0][0] = A; a[0][1] = B; a[1][0] = 0; a[1][1] = 1; this matrix multiplying with [x 1] gives [A*x+b 1] and we can repeat this process.. 
•  » » » 4 years ago, # ^ | ← Rev. 2 →   0 why a[1][0]=0 and a[1][1]=1??
•  » » » » 4 years ago, # ^ |   +1 Because of this 0 and 1 we get column vector with Ax+b and 1 from column vector of x and 1.and since Ax+B is our next x we actually have new x ,1 column vector.so this allows us repeating the process.but is actual program we will do the matrix multiplication in log(n) time rather than doing all the multiplications. 
•  » » 4 years ago, # ^ |   0 Simpler way: you can exponentiate f itself: f^2 = (a*a)*x + a*b+b. Then use fast exponentiation to compute W,R from f^n = W*x+R:Python code: cur = x while n > 0: if n & 1: cur = (a * cur + b) % MOD a, b = a*a % MOD, (a*b + b) % MOD n >>= 1 print cur 
 » 4 years ago, # | ← Rev. 3 →   +5 What is the hack case for D?My solution is to find value An·x + (1 + A + A2 + A3... + An) * B. To find sum of GP, I use the standard formula with an exception case where A = 1, when GP sum = n. What is wrong with this 18423561UPD: Mine was hacked due to overflow of GPSUM*b in special case as I forgot to take modulo with n and it overflowed even long long :(
•  » » 4 years ago, # ^ |   +1 Overflow in gpsum * b is the problem here. I made the same mistake :(
 » 4 years ago, # | ← Rev. 3 →   0 I am getting overflow in Java7 at problem C when running this test : 1000000000 1 3 1000000000 999999999 My code: https://ideone.com/kHjrJTAny idea?EDIT: Now I see that I was not the only one facing this problem. I changed every variable from int to long and now everything seems to work. God, I hate when this happens. But better here than IRL.
•  » » 4 years ago, # ^ |   0 if operands are int, then result is int. So in pieces: long nr = a * b; ... sum = sum.add(BigInteger.valueOf(Math.max(p, q) * x)); overflow exists. Two possible solutions:1) Make all operands long-type;2) Add 1l literal: long nr = a * 1l * b; 1l — is long-type const so during multiplications overflow wouldn't appear.
 » 4 years ago, # |   +25 My god, problem C is a pure hacking bloodbath...
 » 4 years ago, # |   +14 I want some advice about hacking. Sometimes the contestant doesn't initialize a variable, so it contains a garbage value, which might give WA. What should I do in such cases, is the garbage value machine dependent or is it some fixed value? This thing happened in last CF round, one solution didn't initialize a variable, and he was taking max of it with another variable. Fortunately for him, the garbage value was some large negative value, so I couldn't hack him. I would have hacked if the garbage value was some large positive value. What to do in such cases?
•  » » 4 years ago, # ^ |   -8 I shall advice u properly tomorrow..just wait...
 » 4 years ago, # |   +6 What's the idea for problem F?
•  » » 4 years ago, # ^ |   +11 I instantly came up with the idea of using a fully dynamic convex hull and then evaluating at certain coordinates. I coded it and debugged it without thinking, only to fail at Test #9. Then I thought a little bit and I realized that when deleting a line, some lines that were removed earlier because they weren't relevant anymore, might become relevant again, so I'm not sure if fully dynamic convex hull is something we can do.I still don't know how to solve it.
•  » » » 4 years ago, # ^ | ← Rev. 2 →   +8 I think you can solve it without fully dynamic convex hull. Just process queries by blocks (block can have sqrt(n) size, but this is not the best choice). Build convex hull on previous blocks (without deleted pairs in current block of course). Then lookup answer for query in O(sqrt(n) + log(n)). O(n * sqrt(n)) for all.I think it is good solution, but I am too lazy to check it today =D
•  » » 4 years ago, # ^ | ← Rev. 3 →   +8 One solution is that: for each line there is an interval it exists. So, build a segment tree each node contain a convex hull. See link. The other one is sqrt decomposition query. Build a convex hull at each block!
•  » » » 4 years ago, # ^ |   0 Huh, I haven't written a single task using either of those techniques, guess I have to try :)
 » 4 years ago, # | ← Rev. 2 →   0 What does "Unexpected verdict" mean for my hacking attempts #236256, 236261, and 236265?UPD: fixed.
 » 4 years ago, # |   +8 i hacked myself in problem D due to this- ans = ((b%mod * n %mod)+x)%mod test case — 1 1000000000 10000000000000000000 1000000000due to operator preference b%mod * n will take place first thus overflow!
•  » » 4 years ago, # ^ |   0 in the test case you mentioned, the value for n is 10^19 which won't fit even in long long. I think you meant to type 10^18.
•  » » » 4 years ago, # ^ |   0 yeah true
 » 4 years ago, # |   0 there will be no tutorial for this round?
•  » » 4 years ago, # ^ |   0
 » 4 years ago, # |   +6 Where is the editorial for fifth question??
»
4 years ago, # |
-32

When i run c number code on my laptop it answered me 813.But why codeforces answered 625?

# define c continue

using namespace std; int main() { ios::sync_with_stdio(0),cin.tie(0); ll m,n,o,p,q,a=0; cin>>m>>n>>o>>p>>q; a+=(m/n)*p; a+=(m/o)*q; a-=(m/(n*o))*(min(p,q)); if((n*o)>m) if((m!=1)&&(((m==n)&&(!(m%o)))||((m==o)&&(!(m%n))))) a-=min(p,q); cout<<a<<endl; end; }