Codeforces celebrates 10 years! We are pleased to announce the crowdfunding-campaign. Congratulate us by the link https://codeforces.com/10years. ×

By vovuh, 2 years ago, translation, ,

Hello Codeforces!

On December 12, 18:05 MSK Educational Codeforces Round 34 will start.

Series of Educational Rounds continue being held as Harbour.Space University initiative! You can read the details about the cooperation between Harbour.Space University and Codeforces in the blog post.

This round will be rated for Div. 2 again. It will be held on extented ACM ICPC rules. After the end of the contest you will have one day to hack any solution you want. You will have access to copy any solution and test it locally.

You will be given 7 problems and 2 hours to solve them.

The problems were prepared by Mikhail PikMike Piklyaev, Ivan BledDest Androsov and me.

Good luck to all participants!

I also have a message from our partners, Harbour.Space University:

Scholarship Information

We are offering a Scholarship for each of our three tech programmes: Data Science, Computer Science and Cyber Securityfill out the Form for the January 2018 programme start period or the September 2018 programme start period. We will contact you soon. Can't wait to see you here!

Go to form

Congratulations to the winners:

Rank Competitor Problems Solved Penalty
1 dotorya 6 209
3 dreamoon 6 248
4 ivan100sic 6 273
5 Shayan_Jahan 6 308

Congratulations to the best hackers:

Rank Competitor Hack Count
1 Artmat 109:-9
2 blockingthesky 81:-1
3 ssor96 61:-1
4 BurningAss 61:-8
5 proptit_4t41 63:-18

1528 successful hacks and 786 unsuccessful hacks were made in total!

And finally people who were the first to solve each problem:

Problem Competitor Penalty
A proptit_4t41 0:01
B MrDindows 0:04
C Kitorp 0:02
D mdippel 0:20
E dotorya 0:27
F step_by_step 0:38
G dotorya 1:03

UPD Editorial

• +52

 » 2 years ago, # |   +7 Rated round again with lots of problem :) .Hope good rating to all
 » 2 years ago, # |   +20 I hope that the statements will be as short as those from last div2 and as interesting
 » 2 years ago, # |   +12 Thanks for another rating round for div2 :)
 » 2 years ago, # |   +11 Hope the queue is fixed.
 » 2 years ago, # |   +72 Since registration opened before the previous contest's rating changes, this bug happened again. Will this guy be rated?
 » 2 years ago, # |   +25 really rated again??? I just Love CodeForces
 » 2 years ago, # |   0 How do these help educate differently to normal contests? is there solution descriptions afterwards or something?
•  » » 2 years ago, # ^ |   0 Well these rounds were unrated before and thus were 'educational'. You could participate without your ratings being changed and learn from the contest. (How to attempt the real Div contests or learn to hack etc). Or its just a fancy name for it anyways it looks like they'll be rated now which isn't too bad too :P. But I'd rather know how the ratings change for these contests as last time there was a lot of confusion.
 » 2 years ago, # |   +9 Unrated educational rounds please!
 » 2 years ago, # |   +4 I hope the computation speed of the evaluation system could faster.
 » 2 years ago, # |   +5 a chance to recover from yesterday
 » 2 years ago, # | ← Rev. 2 →   +11 Wsl_F, Can you fix it so that the predictor will work well for the Educational rounds?
•  » » 2 years ago, # ^ |   +3 Yeah, I suppose it's not very complicated & I'll fix it for the next educational round. BTW, it is a bit weird that div 1 participants doesn't marked as "unofficial" like always in div2 only rounds.
 » 2 years ago, # |   0 A fast queue plz.
 » 2 years ago, # | ← Rev. 2 →   0 There will be any points on hacking?
 » 2 years ago, # |   -32 You said it is rated for Div 2. But is it rated for Div 1???????
•  » » 2 years ago, # ^ |   0 Only for Div 2.
•  » » » 2 years ago, # ^ |   -26 How you know??? I am asking from OP idiot.
•  » » » » 2 years ago, # ^ |   +4 Who is OP idiot?
•  » » » » » 2 years ago, # ^ |   -15 ORIGINAL POSTER IDIOT
 » 2 years ago, # | ← Rev. 2 →   +4 How Div. 2 participants of this educational round will be sorted in "Standings"?Is there the algorithm description available?I tried the related (New: Educational Rounds on Codeforces!] blog post but I failed to find this information there.My guess (based on the Educational Codeforces Round 33 results): First, sorted by = (the number of problems solved), descending. Second, sorted by Penalty, ascending. Penalty is the sum of penalties for each problem. Penalty for a problem is the sum of: the number of minutes after beginning of the round when the last successful submit was sent; penalty for additional submissions (20 minutes for each). Is this information available somewhere?What am I missing?
•  » » 2 years ago, # ^ |   +4 Ranking is exactly as per ACM rules. You've got it right except for the penalty partUser's penalty: sum of penalty of all 'accepted' problemsPenalty of an accepted problem: Time taken to get the problem accepted + 20 mins penalty for each wrong submissionYou can check ACM style ranklist rules here
•  » » » 2 years ago, # ^ | ← Rev. 2 →   0 Thank you very much!A subtle point is still this one: + 20 mins penalty for each wrong submission As I understood, there is no penalty for re-submit (several Accepted solutions from one participant for one problem), of multiple Accepted solutions the earliest one counts, the others are not considered.
•  » » » » 2 years ago, # ^ |   +1 I believe submissions only till the first accepted solution is considered when calculating penalties. Actually in an ACM styled contest, submission verdicts are generally final, if you get an AC then it is indeed AC, and does not change later on. Since it's not the case here, I believe it is as you say, and if a previously correct solution is hacked, penalty is changed to reflect the next correct solution (maybe, not so sure on this one)
 » 2 years ago, # |   -14 I hope every girl will downvote this :(
 » 2 years ago, # |   +5 Why you don't made div-1 participants out of competition like normal div-2 contests ?
•  » » 2 years ago, # ^ |   -20 shi kh rha hai londe
 » 2 years ago, # |   +15 CF rated rounds are just like addiction.. If you try it once,you would want them again and again and even more frequently.
•  » » 2 years ago, # ^ |   -22 baat main dum hai londe sharma
•  » » 2 years ago, # ^ |   +4 Be careful, there is no known treatment for this addiction.
 » 2 years ago, # |   +2 Rating baadme surakshit hogi pahle Codeforces Servers surakshit karwao :p
 » 2 years ago, # | ← Rev. 2 →   +151 That moment you know you are fucked up and you also know everyone is fucked up.
•  » » 2 years ago, # ^ |   0 It's also not guarenteed that answer fits into long long (((
•  » » » 2 years ago, # ^ |   +65 2 mins of silence for the c++ codes :/
•  » » 2 years ago, # ^ |   +10 A contest about speed of resubmit? Cant accept this ending.
•  » » 2 years ago, # ^ | ← Rev. 2 →   0 I apologize, i was wrong.
•  » » 2 years ago, # ^ |   +22 It's time for Codeforces to support __int128.
•  » » 2 years ago, # ^ |   +125 A moment of silence for those who read it "It it's guaranteed.."
•  » » » 2 years ago, # ^ |   0 :(
•  » » » 2 years ago, # ^ |   0 why this shit happens at the time of rated contest
•  » » 2 years ago, # ^ |   0 The final answer donesn't exceed, but the answer during calculation can exceed!
•  » » 2 years ago, # ^ |   -8 It hurts more when you try D before solving B
 » 2 years ago, # |   0 I literally spent 41 minutes to do this int->long long  in exactly one place -_-I guess I can't trust my own template
•  » » 2 years ago, # ^ |   +10 too bad that's not enough :)
•  » » » 2 years ago, # ^ |   0 lol
 » 2 years ago, # |   +13 exclude the ans > 10^18 tests maybe?
 » 2 years ago, # | ← Rev. 2 →   +40 We're extremely sorry for requiring BigIntegers in D, we didn't really mean it firstly. Neither authors, nor testers pointed this bug to us. :(We would like to apologize for that. I hope codeforces will be able to process all the hacks...
•  » » 2 years ago, # ^ |   +9 Will you consider the test cases for which answer exceeds 10^18?
•  » » » 2 years ago, # ^ |   0 Yes
•  » » » » 2 years ago, # ^ |   -24 So, you don't want to make it unrated? How I think you need to point on the exceed in the task
•  » » » » » 2 years ago, # ^ |   +23 Why it should be? Statement is correct, tests are correct. What's the problem?
•  » » » » » » 2 years ago, # ^ |   +15 Actually yes. It is the job of problem solvers to figure that out.
•  » » 2 years ago, # ^ |   +10 Now plz don't say u won't consider >10^18 because some people who were in middle of 5th problem had to leave that problem, learn new language and code into it (java in my case). If u announced it in the contest, kindly use that only.
•  » » 2 years ago, # ^ |   +3 Does apologies make any sense?
•  » » » 2 years ago, # ^ |   0 Doesn't it? I don't believe this is fine for contest in 2017. It would be ok in the beginning of 2000's but not now for sure.
•  » » 2 years ago, # ^ |   0 Will it fit in unsigned long long ??
•  » » » 2 years ago, # ^ | ← Rev. 2 →   -24 I don't think so. And it can be negative.Well, I was mistaken. ull is fine since the answer is up to 10^19 and not 10^20.
•  » » » » 2 years ago, # ^ |   0 I took care of -ve values I need to know if |ans| fits in ull
•  » » » » » 2 years ago, # ^ | ← Rev. 2 →   -25 Answer can be up to 10^20 in absolute value.Ok, sorry, I definitely miscalced this, should be 10^19
•  » » » » » » 2 years ago, # ^ |   0 OK
•  » » » » » » 2 years ago, # ^ |   0 33184706 so far nobody could come up with such a test case it seems, so will there be more tests by you after the hacking phase? (or is the final test just pretest + hacks?)
•  » » » » » » 2 years ago, # ^ |   0 Are you stupid? In my opinion max test is first half is 1, second half is 10^9 It will overflow long long, but not unsigned ll I have changed long long to unsigned ll. So I got accepted.
•  » » 2 years ago, # ^ |   +68 I don't think you really need to excuse. It is a practical educational point here. I think it is a good skill to estimate max answer and use proper types/methods. Such things happen and it is better to meet them on educational round than any other official contest.
•  » » » 2 years ago, # ^ |   +27 Yeah but it is rated for div2 and c++ users need bigint and thus nearly eliminates a language.
•  » » » » 2 years ago, # ^ |   +69 In innumerable number of problems С++ has the advantage. It is OK to have rare problems on Educational Rounds showing the other side. Also it's a good skill to be able to choose the appropriate language for programming depending on the task.
•  » » » » » 2 years ago, # ^ |   -37 It is very unfair for the beginners who can't write else c++ !! what is the purpose of problem else to impossible the beginners for not trying for solve !! I think there are a lot of us who are very very angry and ask you to edit the test cases to not exceed 10^18 .
•  » » » » » » 2 years ago, # ^ |   +5 I'm sure beginners weren't able to solve F either, but we're not getting rid of F because they don't know how to. There's nothing in the problem statements that limited the answer to < 10^18. Figuring out the bounds of your solution and using appropriate data types (and they even told you that the answer was not limited to 10^18) is part of problem solving.Of course you don't know how to do everything at first, but after seeing it once, a beginner can learn and might be able to do it next time.
•  » » » » » » » 2 years ago, # ^ |   0 Of curse it is very good to know but I think in rated contests you should avoid the differences like this
•  » » » » » » » » 2 years ago, # ^ |   +4 Rated contests are meant to be a measure for the contestant. In my opinion, it actually tests our knowledge about answer interval and data type. Pascal doesnt have a sort built-in function, but you can make one. C++ doesnt have bigInt data type, but you can make one.
•  » » » » 2 years ago, # ^ | ← Rev. 2 →   +4 You could use:1) long double (64 bit precision is enough)2) unsigned int64_t for sum of positive and negative elements3) two int64_t values It is really not difficult to use any of these techniques.
•  » » » » » 2 years ago, # ^ | ← Rev. 2 →   +16 or4) java
•  » » » 2 years ago, # ^ |   +19 I think it's unfair for beginners, especially people who only know C++
•  » » 2 years ago, # ^ |   0 so if it was not intended, Why can't you just edit the tests?
•  » » » 2 years ago, # ^ |   +18 It was intended by problem statement, and it's bad idea to edit problem statement after the contest end.
•  » » 2 years ago, # ^ | ← Rev. 3 →   -8 I used int64_t in D still Hacked! :(update: fixed it!
•  » » » 2 years ago, # ^ |   0 it can be negative so u need more than just 64 bits. Two int64_t's would do it.
•  » » 2 years ago, # ^ | ← Rev. 2 →   0 i think it can be solved using unsigned long long the worst answer can go up to |1019| you just need to handle that carefully : 33192580also i would like to ask does the judge solution use big integers?
 » 2 years ago, # |   0 Did need a BigInteger in the problem D?
•  » » 2 years ago, # ^ |   0 yes if you were using c++
•  » » » 2 years ago, # ^ |   +3 You'd need BigInteger for Java too.
•  » » 2 years ago, # ^ |   +9 I think, if first half 1, second half 10^9. It will overflow long long, but not unsigned llI have changed long long to unsigned ll. So I got accepted.
 » 2 years ago, # |   0 When I'll be able to submit code if I didn't participate in the contest?
•  » » 2 years ago, # ^ |   0 You can now.
•  » » » 2 years ago, # ^ |   +1 Thanks!
 » 2 years ago, # |   0 Should we talk about solutions in this phase (hacking) ? Because I have idea for D so I just wanted to ask if anyone solved it that way.
•  » » 2 years ago, # ^ |   -8 Since all solutions are anyways public, why not?
 » 2 years ago, # |   0 Hello :DCan someone see my code in problem E and tell me why am I getting TLE ?
•  » » 2 years ago, # ^ |   0 Didn't see it carefully but maybe because you have four nested for loops?
•  » » » 2 years ago, # ^ | ← Rev. 2 →   0 The inner one will execute just one time if I found an answer.
•  » » » » 2 years ago, # ^ |   0 try fast fourier transform on lamona's theory for diplom shatara
 » 2 years ago, # |   +4 Nice problems, I really enjoyed the contest.
 » 2 years ago, # |   0 How to solve E ???
•  » » 2 years ago, # ^ |   +13 the frequencies of every character must be the same in all strings. calculate the hamming distance between the first string with all other strings. for every swap (i,j) of characters of the first string, calculate the new hamming distances. If all distances are less than or equal than 2, then swapping (i,j) in the first string gives the answer.
•  » » » 2 years ago, # ^ |   0 How can we prove this always works?
•  » » » » 2 years ago, # ^ |   0 What is the complexity ???
•  » » » » 2 years ago, # ^ |   +3 The string that we are finding can be obtained by swapping exactly two characters of the first string. So we are brute-forcing all possibilities. If we swap two characters the resulting string will be different in at most two positions. Complexity is O(n^2*k)
•  » » » 2 years ago, # ^ | ← Rev. 2 →   +3 What should be the output for the case : 2 2 aa aaI think it should be -1 because in the question it's mentioned they have different indices but here you can swap only (1, 2), so in the next string there's nothing left to swap ?Am I missing something ?UPDATE I think I misunderstood the question :(. That's why I was failing test case 4 :(
•  » » » » 2 years ago, # ^ |   0 XDsame sad story to me
•  » » » 2 years ago, # ^ |   +6 Also if you swap some characters (i,j) and the new hamming distance for some string is 0, there needs to be a duplicate character somewhere in all strings for that pair to work.
•  » » » 2 years ago, # ^ | ← Rev. 2 →   0 Does it work for this test case ?2 3 abc acb
•  » » » 2 years ago, # ^ |   0 If you make a swap then at most two or at least 0 character will change its position (if the swapping characters are same). So for the hamming distance 1 ans should be -1.
•  » » » 2 years ago, # ^ |   0 How do you calculate the new hamming distances ?
•  » » » » 2 years ago, # ^ |   +3 See the discussion in the editorial blog.
•  » » » » » 2 years ago, # ^ |   0 Got it. Thank you :)
 » 2 years ago, # | ← Rev. 4 →   0 I'm sorry, I made a mistake. How to write a 65-bit signed integer?
•  » » 2 years ago, # ^ |   +1 You didn't read the announcement carefully :D
•  » » 2 years ago, # ^ |   0 It was announced that the answer can exceed 1e18.
 » 2 years ago, # |   +17 It isn't guaranteed that the answer doesn't exceed 10^18 by absolute value.You didn't know that before the beginning of the contest, right ? :D
•  » » 2 years ago, # ^ |   0 yes , but sometimes no
 » 2 years ago, # | ← Rev. 16 →   0 Well, nice troll for D :DBUT, NO PANIC! max answer is 2666666666600000 which fits long long. RIP who resubmittedI got this value with greedy test case, but I see hacks, not sure T_TSeems like answer fits in long long but we should do — operations first, still not sure.OK GUYS! SAY GOODBYE TO YOUR RATINGS AND GO TO SLEEP. WE ARE FUCKED UP :(
•  » » 2 years ago, # ^ |   0 Are you sure?I would suck you up if it is so.
•  » » 2 years ago, # ^ |   0 They put hack cases into system tests though so solutions without BigInt should still fail.
•  » » 2 years ago, # ^ | ← Rev. 2 →   0 toooooeasy How did you arrive at that value?
•  » » 2 years ago, # ^ |   0 How did you calculate that? In my opinion if there are cases where the answer exeed 10^18, it is not fair, because some languages support big numbers, but c++ doesn't...
•  » » 2 years ago, # ^ |   0 you're wrong max answer is actually 20000000000000000000:consider the case where n = 2 * 10^5 and first half are -10^9 and the rest are 10^9
•  » » » 2 years ago, # ^ |   +1 Dalisyron numbers >=1
•  » » » » 2 years ago, # ^ |   0 Yep I guess I didn't notice that :/
•  » » » » » 2 years ago, # ^ | ← Rev. 5 →   0 The first half is 1, the rest — 10^9. Answer is 9999999990000000000.
•  » » » » 2 years ago, # ^ | ← Rev. 2 →   +3 first half 1, second half 10^9 definitely overflows long long, but not unsigned llPikMike said, it can be up to 10^20, which would overflow ull (I don't know how)
•  » » » » » 2 years ago, # ^ |   0 How to do with unsigned? answer can be negative
•  » » » » » » 2 years ago, # ^ | ← Rev. 3 →   +5 You can keep a sign value. I did it using unsigned ll. But I don't know if I could be hacked.
•  » » » » » » 2 years ago, # ^ |   +12 33184706 handle positive and negative parts of the answer separately each in one ull
•  » » 2 years ago, # ^ |   0 It's an ACM-ICPC Style, so if the first solution gets accepted there's no penalty.
 » 2 years ago, # |   0 How to solve D??? :(
 » 2 years ago, # |   +5 I just read the clarification about D :(
 » 2 years ago, # | ← Rev. 2 →   0 I thought i had solved D with this alghorithm,but it failed on first test.It was right on sample cases too.Whats the problem with this?First,i thought threre were no rules at all,for every i<=j you increment your answer by a[j]-a[i].You compute beforehand how many times you add and subtract one element,so you can get answer for no rules in O(n)We now have to think about rules.They only say that for any a[i] you have to consider a[i]-1, a[i] and a[i]+1 values beforehand.Their counts are important here,so we have to store them in a place.Arrays arent suitable since a[i] can go up to 10^9 so i used multiset and even map to update their counts as i iterated through the values.Even after the warning i used long long values.They could overflow in C++ as maximum ans could be 10^5*10^5*10^9 for an input consisting half zeros and 10^9s after
•  » » 2 years ago, # ^ |   0 1 <=n <= 2 * 1e5;Where is 10^6 term coming from, in your explaination?
•  » » » 2 years ago, # ^ |   0 Sorry couldnt see it well in this hurry.Thanks for clarifying.
•  » » » » 2 years ago, # ^ |   +17 Congratulations, you posted the comment with id 400000. :-)http://codeforces.com/blog/entry/56291?#comment-400000
 » 2 years ago, # |   0 Hack for D?
 » 2 years ago, # |   +18 why you are so bad in problem D ? why long long in c++ isn't enough for you ?
 » 2 years ago, # |   +3 lmao that D
 » 2 years ago, # | ← Rev. 2 →   0 I just realized that problem E had a O(nk) solution, but isn't O(n2k) supposed to get AC as well?
•  » » 2 years ago, # ^ |   +2 Did you wanted to say O(kn2)?
•  » » » 2 years ago, # ^ |   0 Yep I updated it already thanks :)
•  » » » » 2 years ago, # ^ |   +6 I tried to solve E in O(kn2) with maps (even own hashmap) and didn't succeed. But when I replaced map with vector and sorting, I finally managed to get AC with this brute force complexity. http://codeforces.com/contest/903/submission/33193268
 » 2 years ago, # |   +3 Hints for E please.
•  » » 2 years ago, # ^ | ← Rev. 2 →   0 maybe dynamic programming with bitmaskUPD: i mean about problem F sorry
•  » » 2 years ago, # ^ |   0 First of all frequency of all the strings should be same. Then imagine your initial ans is the first given string. Now generate all the possible strings by swapping two characters of that string. Now you have to calculate the hamming distance with all other strings.If the calculated hamming distance for all the given string is 2 or 0(if there is a duplicate character) then you got your ans.
 » 2 years ago, # |   +17 A language-dependent problem in a rated contest, sounds ridiculous tbh.
•  » » 2 years ago, # ^ |   -14 Well, you can write bigints in c++, moreover you only need addition and printing
•  » » » 2 years ago, # ^ |   +43 And You Can write Ai <= 1e5 :)),moreover you only need removing and printing
•  » » » 2 years ago, # ^ |   +20 sounds even more ridiculous :)
•  » » 2 years ago, # ^ |   -6 Not at all. http://codeforces.com/blog/entry/22566
•  » » 2 years ago, # ^ |   +4 but its not fair that C++ waste more time to write big integer while jave only define it
•  » » » 2 years ago, # ^ |   +24 Same with next_permutation. It's not fair that cpp gets it handed to them while Java coders need to waste time to define it.Or with cpp's speed. It's not fair that cpp is many times faster than Python. Python coders can write more optimized algorithms that still end up running slower than cpp code.Languages are different. You have the choice of picking one that suits your needs or learning to do things not natively supported in your language.
•  » » » » 2 years ago, # ^ | ← Rev. 2 →   -26 Java and python have higher speed(time) limits
•  » » » » » 2 years ago, # ^ |   0 He's also talking about implementation time not running time. As in next_permutation that is implemented in C++ but not in Java.And also: Sometimes, with the same solution, Python gets TLE and C++ doenst.
•  » » » » » 2 years ago, # ^ |   +13 Do you mind sourcing that? I didn't know that CF did that.
•  » » » » » » 2 years ago, # ^ |   -18 Every website does it. Try submitting a TLE (infinite loop) solution to a question in both c++ and python/java to see it.
•  » » » » » » » 2 years ago, # ^ | ← Rev. 2 →   +15 I really dislike anecdotal evidence.You can see the time limit at the top of every cf problem, and that's given before you choose what language you're submitting in, so it should be the same for all languages.
•  » » 2 years ago, # ^ |   0 All contests are language-dependent... A lot of times the same solution implemented in Python gives TLE while solutions in C++ don't... Is that unfair too for you? Or that next_permutation exists in c++ but not in java. Is that unfair when a contest requires it?I think you all have the conception c++ is the best in everything but it has its limitations too obviously... You are a good coder if you know them and can adapt. Congratulations to all who solved D. If you didn't better luck next time. Keep improving everyone!
 » 2 years ago, # |   -26 Yo , please make it unrated dudes, i solved D at the same time as C and B and it so correct but because of the fact that you wrote unclear only about 100 people from 1300 will get AC on D. Please don't atleast decrease the rating of others not cool.
 » 2 years ago, # |   -35 Strongly suggest make it unrated
 » 2 years ago, # |   0 I look at the statusboard and I found there're a lot of people get a WA in the 29th case of the D problem,and I also found that nearly all of them have a same wrong answer, so is anybody able to detail the test data? I want to know where I'm wrong? please?
 » 2 years ago, # |   +32
 » 2 years ago, # |   0 Oh, no its rated. I was heedless about the name. As usual seeing the name as Educational round I start contest though 30 minutes left. I saw this part (Rated for Div. 2) while its 10 minutes left only. :( :( Then there's left a cheap situation for myself. :/ :/
 » 2 years ago, # |   +21 Nice language-dependent contest...
•  » » 2 years ago, # ^ |   +4 Granted its nice to have problems not dependent on specific languages. But when you have so many languages with different characteristics, its very hard to design such problems. Yeah it was not the author's intention to include big integers, but that doesn't make the problem wrong. I have seen plenty of problems requiring big integers but not mentioning explicitly in the statement. Sometimes you should be able to figure out what data types you need and in this problem it was quite straightforward to do so.If its unfair for C++ users, think how many problems are unfair for python or java users? I know some of you are pissed, but put aside your personal feelings and think neutrally.And its also not that it can't be solved in C++ at all...
•  » » » 2 years ago, # ^ |   +5 Were there BigInt problems on CodeForces? I don't think I saw one yet and felt like it was an unwritten rule that we don't need BigInt here.
•  » » » » 2 years ago, # ^ |   0 I've seen a few. For example: http://codeforces.com/contest/17/problem/D
•  » » 2 years ago, # ^ |   0 All you C++ coders complaining, you've never coded competitively in other language... many many many contests are 'language dependent' in favor of C++, but nobody complains, because we are used to it. This is the first contest where C++ is at a disadvantage and there's so much complaining. (and it's still very possible with c++, while sometimes other languages are literally too slow to pass)
 » 2 years ago, # |   -19 If you think (like me) that answer on D > 10^18 is a bit unfair for c++ users, upvote this in the idea that CF responsalbes will see this and will see how many we are. It was a nice contest, short statements and beautiful problems, but this thing on D deteriorate the value of the contest.
 » 2 years ago, # |   +21 random_shuffle(ranklist.begin(),ranklist.end());
 » 2 years ago, # |   0 Should've ensured that answers were less than 1e18. Sorry to say, but very careless question making.
•  » » 2 years ago, # ^ |   +3 Did they change the statement for D? It doesn't say in the statement that the answer would be less than 10^18. I don't see why it would be the fault of the problem setter instead of a fault of an assumption of the solver.
•  » » » 2 years ago, # ^ |   0 I'm not saying I'm not at fault, but I feel such variables should not been involved in such contests. The fact that they had to clarify mid contest clearly indicates that they had not prepared to trick people and instead it was something they overlooked, which I repeat, is very careless
 » 2 years ago, # |   +9 Anyone solved D with index compression + segment tree? I had this idea, I know its much harder than other solutions, but its just the opposite way of what everyone did. If anyone solved this way, please write me.
•  » » 2 years ago, # ^ |   0 I tried this too
•  » » » 2 years ago, # ^ |   0 Great, thank you. Im glad I didnt have time to code this solution, because it would consume for me so much time, and then i would get hack because of bigint.
•  » » » » 2 years ago, # ^ | ← Rev. 2 →   0 Number of people who solved d in the contest is decrease from over 1000 to about 100, so don't be sad :D
•  » » 2 years ago, # ^ |   +6 I use index compression and BIT, but I got hack due to long long.
•  » » » 2 years ago, # ^ |   0 Nice, I also knew it can be done with BIT, but I dont have too much experience with coding it, thats why i thought to code segment tree.
•  » » 2 years ago, # ^ |   0 My submission: 33193137I solved D with compression + BIT. I have used pair, so the first value is the sum and the second value is how many values are in the interval.
•  » » 2 years ago, # ^ |   0 Hii.. I am new and learnt BIT sometime ago.. Can you please explain me what does compression means in this context?Link to any resource too would be much appreciated. Thanks :)
•  » » » 2 years ago, # ^ |   0 Compression means scanning all the inputs beforehand and mapping them to smaller value when only order of element matters. https://www.quora.com/What-is-array-compression-technique-and-how-is-it-used-for-solving-problems-in-competitive-programming
•  » » » » 2 years ago, # ^ |   0 Thank you :)
•  » » 2 years ago, # ^ |   0 I used compression+segtree, got AC but failed due to long long. Here's my solution: 33182205. It's probably way too complicated, but it works.
 » 2 years ago, # |   -24 So next time I read a problem, I first decide what language to use, then learn the language from scratch in contest time, and then if time permits, find out the logic and eventually code the solution. Thank You CF for teaching me a new approach today :)
•  » » 2 years ago, # ^ |   0 You can implement your own BigInts in cpp. It would just be something else you prepare before a contest like your other templates.Although I guess learning a language in 2 hours would be another viable strategy.
•  » » » 2 years ago, # ^ |   0 But can you use something coded out of contest? Except for defines and stuff like that.
•  » » » » 2 years ago, # ^ |   0 you could just copy it, just like what people do in ACM-ICPC
•  » » » » 2 years ago, # ^ |   +8 You can use anything you prepare beforehand that you've written. There are some limitations on third-party/other people's code.
•  » » 2 years ago, # ^ |   0 You really only know C++? That's a really bad habit. Mainly when cases as this appear... It's like only knowing javascript or python
 » 2 years ago, # | ← Rev. 3 →   0 The hack been used to for D is incorrect I guess, cause it shows answer to be -9999999990000000000 =-9.9 * 1018. Please check.Update: My bad. The update post mentions "It isn't". I overlooked.
•  » » 2 years ago, # ^ |   0 The clarification just said: It isn't guaranteed that the answer doesn't exceed 10^18 by absolute value. Really sad.
•  » » » 2 years ago, # ^ |   +8 omg! I read "it's guaranteed" when notification had come! This is sad :(
•  » » » » 2 years ago, # ^ |   +1 Me too!!! I didn’t realize until I found that almost every one is being hacked!
•  » » 2 years ago, # ^ | ← Rev. 2 →   +13 I didn't even look at that "isn't", i just read "...guaranteed.... doesn't exceed..." , and i was like "ok, no problem!"
 » 2 years ago, # |   0 All contests are language-dependent... A lot of times the same solution implemented in Python gives TLE while solutions in C++ don't... Is that unfair too for you? Or that next_permutation exists in c++ but not in java. Is that unfair when a contest requires it?I think you all have the conception c++ is the best in everything but it has its limitations too obviously... You are a good coder if you know them and can adapt. Congratulations to all who solved D. If you didn't better luck next time. Keep improving everyone!
 » 2 years ago, # |   +12 The announcement "the output > 1e18" doesn't make sense because LLONG_MAX > 9e18.
•  » » 2 years ago, # ^ |   0 But LLONG_MAX < 9.9 * 10^18
•  » » » 2 years ago, # ^ |   0 But the output can be > 1e19 :D
 » 2 years ago, # |   0 AC in D with long double 33191777
•  » » 2 years ago, # ^ |   +19 You're asking to get hacked
•  » » » 2 years ago, # ^ |   +14 Yep
•  » » » 2 years ago, # ^ | ← Rev. 2 →   0 Actually, a long double can hold all integers in the range (-2^64, 2^64). It will do just fine for this problem.
 » 2 years ago, # |   +30 Everyone's switching to Python on D after getting hacked
•  » » 2 years ago, # ^ |   0 When I saw the name Stroustrup I was shocked, I thought that the founder of C++ was using phyton. Then I relieved when I checked the profile to see that the person is from Ukraine not Denmark :D
 » 2 years ago, # |   +6 Why you announced like "Output can exceeds 10^18"? You should use maximum range of long long data type instead of 10^18. Making this round rated will really unfair to many contestants.
•  » » 2 years ago, # ^ |   0 Why? Pretty much everyone got hacked, so no harm was done.
•  » » » 2 years ago, # ^ |   +7 Well, who solved D before solving some other problems, will get more penalty than others, it's not a unfair?
•  » » » 2 years ago, # ^ |   +6 What about those who tried D first?
•  » » » 2 years ago, # ^ |   0 Announcing the hack test is not unfair? Why did they have to to that? -_-If they didn't announce that "Output can exceed 10^18" then it would be totally fair to get hacked for that case :)
•  » » » » 2 years ago, # ^ |   0 They announced that during the contest so people had time to fix their code.
•  » » 2 years ago, # ^ |   0 Making this round unrated would also be really unfair to many contestants.
•  » » » 2 years ago, # ^ |   0 Don't worry. It seems to be rated, you are gonna be blue.
•  » » » » 2 years ago, # ^ |   0 As long as nothing bad happens in the next 10 hours. :)
•  » » » » 2 years ago, # ^ |   0 I wasn't talking about me originally though. There's many people who did D and did it correctly, and it would be unfair to them if the contest was made unrated.
•  » » » » » 2 years ago, # ^ |   0 *There are
 » 2 years ago, # |   +6 anyone higher than this?......
•  » » 2 years ago, # ^ |   +12 For now I can assure that nobody surpassed my record of 18 unsuccessful attempts in this contest xD
•  » » 2 years ago, # ^ |   +20
•  » » » 2 years ago, # ^ |   +10 81 hacks in a rated contest!
•  » » » » 2 years ago, # ^ |   +2 hacks is effectless in educational contests. :)
•  » » » » » 2 years ago, # ^ |   0 It's rated for Div 2. People will lose rating because they placed lower because they got hacked.
•  » » » » » » 2 years ago, # ^ | ← Rev. 2 →   0 Not really. In Educational rounds, all hacks are included in the final system test, which runs after the hacking phase.So nobody could evade the hacks eventually. The hacking is kind of a mechanism to test your ability to generate tests and exploit weaknesses from other people's codes.
•  » » » » » » 2 years ago, # ^ | ← Rev. 2 →   +1 I mean who hack someone else don't get lower penalty. so 81 hacks isn't good for him.
•  » » » » » » » 2 years ago, # ^ |   0 Everything happens for a reason. Maybe he'll find his own good in doing this (not obliged to be ratings/penalties) ;)
•  » » » » » » » » 2 years ago, # ^ |   0 Right. :)
 » 2 years ago, # |   +67 Why was the clarification "isn't" instead of "is NOT"?
•  » » 2 years ago, # ^ |   +4 Yes that is my concern too.
•  » » 2 years ago, # ^ |   +37 i read "it is guaranteed" instead of "it isn't guaranteed" when the notification had come.
•  » » » 2 years ago, # ^ |   +5 same for me bro
•  » » » » 2 years ago, # ^ |   0 Same :)
•  » » 2 years ago, # ^ |   0 Same :)
•  » » » 2 years ago, # ^ |   0 and if it is , they should make a note for that , not an announcement after more than 1 hour from the beginning of the contest !!
 » 2 years ago, # | ← Rev. 2 →   0 my algorithm for D is first sorting the given array and then keep a map for every i and then use a fenwick tree for find the answer. To compute the number of elements 1 greater and 1 less than this element and update the answer. Also insert in fenwick tree. My submission is 33181133. Is there an easier method to solve this. Although i got hacked for not using big int of unsigned ll.
•  » » 2 years ago, # ^ |   0 yeah, prefix sum and map of occurrence only, got hacked too 33189540
•  » » 2 years ago, # ^ |   +14 A nicer way is to compute all the differences between any pair of elements, then find all the differences that are equal to 1 or -1 and subtract them from the answer. this can be done easily with a map.Of course, bigint got us all :)
•  » » » 2 years ago, # ^ |   0 Yeah and a lot of people submitted their submission before the announcement :/
•  » » » 2 years ago, # ^ |   0 thanks man
 » 2 years ago, # |   0 How to solve E ?
•  » » 2 years ago, # ^ |   0 Someone mentioned calculating hamming distances for string, idk if that's true.
•  » » 2 years ago, # ^ |   0 my idea inside the contest was using hashing , first in O(k*n^2) find the hashes of all the strings except for the 1st one and store all the hashes in a set for that string.. (make a set s[K] , k == no. of strings)..After this , for the first string , in O(n^2) find all the swaps , get the hash corresponding to the NEW first string in O(1) ( we calculate the hash from the 1st string's orignal hash,because SWAPPING 2 characters means we have to just add and subtract 2 values ).. So for all possible swaps of 1st string , check in O(klogn) for all the other (k-1) strings if they have the hash in their set.... if they do have the hash , then print the current NEW(after swap) first string...Implemented this in contest because had 1:30 hours on hand but somehow gave segmentation fault , then I quit , it was getting very late,went to sleep..I havent corrected my bug yet .. so if please someone finds fault in my way please correct me , I am learning, also I would like to know how others did this.. , again , if my way is wrong please correct me and tell me why :)TOTAL COMPLEXITY = O(k*n^2)
 » 2 years ago, # | ← Rev. 3 →   -9 Wanted to know rating predicted by CF-Predictor:Predicted < Rating_Increase (Because Div1 would be removed)Predicted > Rating_Increase (As seen in last round)Predicted = Rating_IncreaseWhich would be true. If 2nd one, why is it so?
•  » » 2 years ago, # ^ |   0 It would depend on your placement. If you are currently beating a lot of Div1 people, then it would overestimate. Otherwise, it would be closer to accurate or maybe underestimate.
 » 2 years ago, # | ← Rev. 2 →   +1 I hope that the problem about problem D ended, but I prefer to share an idea with you as a lesson to us: let us assume that the function d(x,y) give 1 instead of y-x when the condition |x-y|>1 is setisfied. Then the problem come up to be: [calculate the number of pairs ai,aj (where 1<=i<=j<=n) that setisfy the condition mentioned upove]. In this case, we, as problem solvers, will say in our minds: [the upper bound of the answer is the number of all that pairs ai,aj, so it is n*(n-1)/2+n, and since n can be equal to 2×10^5, we surely need to use long long int data type.]. All what we said was a result of our habit that the answer is either int or long long, but this is not enough for a problem solver.
 » 2 years ago, # |   0 when the rating update will be published ?
•  » » 2 years ago, # ^ |   0 After System Testing with the all the hacks that have been submitted during the hacking phase.
 » 2 years ago, # |   +6 the answer in problem d can exceed 10^18 It is very unfair for c++ coders
•  » » 2 years ago, # ^ |   +3 How so? You shouldn't be able to slap long long onto every answer that will be an integer and expect it to work.
•  » » » 2 years ago, # ^ | ← Rev. 2 →   +1 but there are a lot of languages like java that has big integers so , I am talking about the judge should avoid the differences between the languages
•  » » » » 2 years ago, # ^ |   +21 That's like saying we shouldn't have any problems that use next_permutation because cpp has it built in, but Java doesn't.Languages are different, and Codeforces lets you pick from a variety of languages to solve problems. It's up to the coder to pick the best language for the problem or to know how to make an inferior one (for that problem) work.
•  » » » » » 2 years ago, # ^ | ← Rev. 2 →   +6 But next_permutation is easier to code than bigint lol :D
•  » » » » » » 2 years ago, # ^ |   0 How about nth_element :D
•  » » » » » » 2 years ago, # ^ |   0 You didn't even need bigint. You could get away with two unsigned long longs or even just use a long double and call it a day.There are many ways to do a bigint very simply if you do not need to hold values that large.
 » 2 years ago, # |   +8 When will the editorial be published?
•  » » 2 years ago, # ^ |   0 after finishing hacking operation
•  » » » 2 years ago, # ^ |   0 But, they published it earlier last time.
 » 2 years ago, # |   +75
•  » » 2 years ago, # ^ |   0 NaCl
 » 2 years ago, # |   0 Thanks for problem D! I got to learn something new from it. If anyone knows any problem related to it can they please comment the link? Thanks!
 » 2 years ago, # |   +5 How to solve F?
•  » » 2 years ago, # ^ |   +3 Use bitmask DP: http://codeforces.com/contest/903/submission/33215290Represent the "*" of the last three columns, with 2^(3*4) = 4096 masks in total. For the 4*4 submatrix just directly clear the mask and pay the cost instead of storing 2^(4*4) states.
•  » » » 2 years ago, # ^ |   +3 Can you explain it in more detail. I didn't get it.
 » 2 years ago, # |   +5 The integer overflow problem in Div2 D can be solved by using long double instead of long long in c++.My solution
 » 2 years ago, # |   +8 I am surprised that there are so few discussions about how to solve problem G.
 » 2 years ago, # |   +28 I feel like the statement about ans exceeding 10^18 should not have been made public. As a programmer, it's our responsibility to estimate ans and use data types accordingly. That announcement assisted all the hackers who were unaware about it at first. Only the one's who actually knew that the ans would exceed long long were the ones who deserved the points gotten by hacking.
•  » » 2 years ago, # ^ | ← Rev. 3 →   +4 Completely agree. Moreover, people who had a correct solution from the beginning lost rank due to other people's resubmissions.
 » 2 years ago, # |   +9 when will rating change take place?Hacking period is over
•  » » 2 years ago, # ^ |   +4 I don't think they've run the system tests with the hacks yet.
 » 2 years ago, # |   +9 RIP rating :'v
 » 2 years ago, # |   +12 Problem D reminded me the painful memory with problem Prize from IOI 2017. I made the same mistake in both of these problem: making false assumption because of 'it has never happened before'. For this problem, I made an assumption that BigInteger is not needed because 'Codeforces problem rarely required that'. For the IOI, I made the assumption that the checker is not adaptive because 'I haven't seen an IOI problem with an adaptive checker before'.
 » 2 years ago, # |   0 I got AC in D with c++ without bigint.
•  » » 2 years ago, # ^ |   +19 You are molodchina
•  » » » 2 years ago, # ^ |   +5 molodchina Means ??
•  » » » » 2 years ago, # ^ |   +14 This is a Russian humor. "Molodhina" = "молодчина!".This phrase can be translated as "Congratulations!" (and also as "Good job!" or "Well done!").
 » 2 years ago, # |   +17 Will you make a list of the top Div 2 competitors? :D
 » 2 years ago, # |   +4 In problem D, why double gives WA on test 13 while long double gives AC ?
•  » » 2 years ago, # ^ |   +8 because double can not represent numbers up to 10^18 with precision of at leat one (that is, the diference starts to be, for example 2 or more, if the current number is 99...93 the next can be 99..95, skipping 99...94), long double, due to its bigger representation, has a better precision
 » 2 years ago, # |   +3 Can someone please explain F ? I do not understand it from the editorial.