Привет, Codeforces!
12 декабря в 18:05 по Москве начнётся Educational Codeforces Round 34.
Продолжается серия образовательных раундов в рамках инициативы Harbour.Space University! Подробности о сотрудничестве Harbour.Space University и Codeforces можно прочитать в посте.
Этот раунд снова будет рейтинговым для Div. 2. Соревнование будет проводиться по немного расширенным правилам ACM ICPC. После окончания раунда будет период времени длительностью в один день, в течение которого вы можете попробовать взломать абсолютно любое решение (в том числе свое). Причем исходный код будет предоставлен не только для чтения, но и для копирования.
Вам будет предложено 7 задач на 2 часа. Мы надеемся, что вам они покажутся интересными.
Задачи вместе со мной готовили Михаил awoo Пикляев и Иван BledDest Андросов.
Удачи в раунде! Успешных решений!
У меня также есть сообщение от наших партнёров, Harbour.Space University:
Информация об обучении
Мы предлагаем записаться на курсы по одной из трёх наших программ, связанных с IT: Data Science, Computer Science и Cyber Security — заполните форму для того, чтобы принять участие в программе, начинающейся в январе или в сентябре 2018 года. Мы свяжемся с вами вскоре после заполнения формы. Надеемся увидеть вас среди участников наших курсов!
Поздравляем победителей:
| Rank | Competitor | Problems Solved | Penalty |
|---|---|---|---|
| 1 | dotorya | 6 | 209 |
| 2 | JustasK | 6 | 228 |
| 3 | dreamoon_love_AA | 6 | 248 |
| 4 | ivan100sic | 6 | 273 |
| 5 | Shayan | 6 | 308 |
Поздравляем лучших взломщиков:
| Rank | Competitor | Hack Count |
|---|---|---|
| 1 | Artmat | 109:-9 |
| 2 | gigabuffoon | 81:-1 |
| 3 | ssor96 | 61:-1 |
| 4 | Danylo99 | 61:-8 |
| 5 | AkiLotus | 63:-18 |
Было сделано 1528 успешных и 786 неудачных взломов.
И, наконец, поздравляем людей, отправивших первое полное решение по задаче:
| Problem | Competitor | Penalty |
|---|---|---|
| A | AkiLotus | 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 Разбор
Rated round again with lots of problem :) .Hope good rating to all
I hope that the statements will be as short as those from last div2 and as interesting
Thanks for another rating round for div2 :)
Hope the queue is fixed.
Since registration opened before the previous contest's rating changes, this bug happened again. Will this guy be rated?
really rated again??? I just Love CodeForces
How do these help educate differently to normal contests? is there solution descriptions afterwards or something?
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.
Unrated educational rounds please!
I hope the computation speed of the evaluation system could faster.
a chance to recover from yesterday
WasylF, Can you fix it so that the predictor will work well for the Educational rounds?
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.
A fast queue plz.
There will be any points on hacking?``
You said it is rated for Div 2. But is it rated for Div 1???????
Only for Div 2.
How you know??? I am asking from OP idiot.
Who is OP idiot?
ORIGINAL POSTER IDIOT
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):
=(the number of problems solved), descending.Penalty, ascending.Is this information available somewhere?
What am I missing?
Ranking is exactly as per ACM rules. You've got it right except for the penalty part
User's penalty: sum of penalty of all 'accepted' problems
Penalty of an accepted problem: Time taken to get the problem accepted + 20 mins penalty for each wrong submission
You can check ACM style ranklist rules here
Thank you very much!
A subtle point is still this one:
As I understood,
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)
I hope every girl will downvote this :(
Why you don't made div-1 participants out of competition like normal div-2 contests ?
shi kh rha hai londe
CF rated rounds are just like addiction.. If you try it once,you would want them again and again and even more frequently.
baat main dum hai londe sharma
Be careful, there is no known treatment for this addiction.
Rating baadme surakshit hogi pahle Codeforces Servers surakshit karwao :p
That moment you know you are fucked up and you also know everyone is fucked up.
It's also not guarenteed that answer fits into long long (((
2 mins of silence for the c++ codes :/
A contest about speed of resubmit? Cant accept this ending.
I apologize, i was wrong.
It's time for Codeforces to support __int128.
A moment of silence for those who read it "It it's guaranteed.."
:(
The final answer donesn't exceed, but the answer during calculation can exceed!
It hurts more when you try D before solving B
I literally spent 41 minutes to do this
int->long longin exactly one place -_-I guess I can't trust my own template
too bad that's not enough :)
lol
В задаче D надо было использовать длинную арифметику?
exclude the ans > 10^18 tests maybe?
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...
Will you consider the test cases for which answer exceeds 10^18?
Yes
So, you don't want to make it unrated? How I think you need to point on the exceed in the task
Why it should be? Statement is correct, tests are correct. What's the problem?
Actually yes. It is the job of problem solvers to figure that out.
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.
Does apologies make any sense?
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.
Will it fit in unsigned long long ??
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.
I took care of -ve values I need to know if |ans| fits in ull
Answer can be up to 10^20 in absolute value.
Ok, sorry, I definitely miscalced this, should be 10^19
OK
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?)
In my opinion, max test is that first half is 1 and the second half is 10^9 It will overflow long long, but not unsigned ll I have changed long long to unsigned ll. And I got accepted :)
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.
Yeah but it is rated for div2 and c++ users need bigint and thus nearly eliminates a language.
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.
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 .
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.
Of curse it is very good to know but I think in rated contests you should avoid the differences like this
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.
You could use:
1) long double (64 bit precision is enough)
2) unsigned int64_t for sum of positive and negative elements
3) two int64_t values
It is really not difficult to use any of these techniques.
or
4) java
I think it's unfair for beginners, especially people who only know C++
so if it was not intended, Why can't you just edit the tests?
It was intended by problem statement, and it's bad idea to edit problem statement after the contest end.
I used int64_t in D still Hacked! :(
update: fixed it!
it can be negative so u need more than just 64 bits. Two int64_t's would do it.
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 : 33192580
also i would like to ask does the judge solution use big integers?
Did need a BigInteger in the problem D?
yes if you were using c++
You'd need BigInteger for Java too.
I think, if first half 1, second half 10^9. It will overflow long long, but not unsigned ll
I have changed long long to unsigned ll. So I got accepted.
When I'll be able to submit code if I didn't participate in the contest?
You can now.
Thanks!
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.
Since all solutions are anyways public, why not?
Hello :D
Can someone see my code in problem E and tell me why am I getting TLE ?
Didn't see it carefully but maybe because you have four nested
forloops?The inner one will execute just one time if I found an answer.
Nice problems, I really enjoyed the contest.
How to solve E ???
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.
How can we prove this always works?
What is the complexity ???
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)
What should be the output for the case : 2 2 aa aa
I 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 :(
XD
same sad story to me
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.
Does it work for this test case ?
2 3 abc acb
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.
How do you calculate the new hamming distances ?
See the discussion in the editorial blog.
Got it. Thank you :)
I'm sorry, I made a mistake. How to write a 65-bit signed integer?
You didn't read the announcement carefully :D
It was announced that the answer can exceed 1e18.
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
Well, nice troll for D :D
BUT, NO PANIC! max answer is 2666666666600000 which fits long long. RIP who resubmitted
I got this value with greedy test case, but I see hacks, not sure T_T
Seems 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 :(
They put hack cases into system tests though so solutions without BigInt should still fail.
memcpy How did you arrive at that value?
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...
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
Dalisyron numbers >=1
Yep I guess I didn't notice that :/
The first half is 1, the rest — 10^9. Answer is 9999999990000000000.
first half 1, second half 10^9 definitely overflows long long, but not unsigned ll
awoo said, it can be up to 10^20, which would overflow ull (I don't know how)
How to do with unsigned? answer can be negative
You can keep a sign value. I did it using unsigned ll. But I don't know if I could be hacked.
33184706 handle positive and negative parts of the answer separately each in one ull
It's an ACM-ICPC Style, so if the first solution gets accepted there's no penalty.
Ох сейчас взломы по D полетят
How to solve D??? :(
I just read the clarification about D :(
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
1 <=n <= 2 * 1e5;
Where is 10^6 term coming from, in your explaination?
Sorry couldnt see it well in this hurry.Thanks for clarifying.
Congratulations, you posted the comment with id 400000. :-)
http://codeforces.net/blog/entry/56291?#comment-400000
Hack for D?
why you are so bad in problem D ? why long long in c++ isn't enough for you ?
lmao that D
I just realized that problem E had a O(nk) solution, but isn't O(n2k) supposed to get AC as well?
Did you wanted to say O(kn2)?
Yep I updated it already thanks :)
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.net/contest/903/submission/33193268
Hints for E please.
maybe dynamic programming with bitmask
UPD: i mean about problem F sorry
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.
A language-dependent problem in a rated contest, sounds ridiculous tbh.
Well, you can write bigints in c++, moreover you only need addition and printing
And You Can write Ai <= 1e5 :)),moreover you only need removing and printing
sounds even more ridiculous :)
Not at all. http://codeforces.net/blog/entry/22566
but its not fair that C++ waste more time to write big integer while jave only define it
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.
Java and python have higher speed(time) limits
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.
Do you mind sourcing that? I didn't know that CF did that.
Every website does it. Try submitting a TLE (infinite loop) solution to a question in both c++ and python/java to see it.
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.
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!
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.
Strongly suggest make it unrated
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?
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?
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. :/ :/
Are you people really asking to remove test cases from D or declare it unrated because you didn't know how to solve it? C++ is good for somethings and bad for other things. It's normal... Python sometimes gives TLE in a solution that is ACP in a c++ implementation. Should I complain when it happens? If you didn't get the correct answer next time try harder and learn more.
Nice language-dependent contest...
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...
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.
I've seen a few. For example: http://codeforces.net/contest/17/problem/D
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)
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.
random_shuffle(ranklist.begin(),ranklist.end());
Should've ensured that answers were less than 1e18. Sorry to say, but very careless question making.
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.
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
How to solve G?
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.
I tried this too
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.
Number of people who solved d in the contest is decrease from over 1000 to about 100, so don't be sad :D
I use index compression and BIT, but I got hack due to long long.
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.
My submission: 33193137
I 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.
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 :)
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
Thank you :)
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.
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 :)
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.
But can you use something coded out of contest? Except for defines and stuff like that.
you could just copy it, just like what people do in ACM-ICPC
You can use anything you prepare beforehand that you've written.
Source: http://codeforces.net/blog/entry/8790
There are some limitations on third-party/other people's code.
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
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.
The clarification just said: It isn't guaranteed that the answer doesn't exceed 10^18 by absolute value. Really sad.
omg! I read "it's guaranteed" when notification had come! This is sad :(
Me too!!! I didn’t realize until I found that almost every one is being hacked!
I didn't even look at that "isn't", i just read "...guaranteed.... doesn't exceed..." , and i was like "ok, no problem!"
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!
The announcement "the output > 1e18" doesn't make sense because LLONG_MAX > 9e18.
But LLONG_MAX < 9.9 * 10^18
But the output can be > 1e19 :D
AC in D with long double 33191777
You're asking to get hacked
Yep
Actually, a long double can hold all integers in the range (-2^64, 2^64). It will do just fine for this problem.
Everyone's switching to Python on D after getting hacked
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.
Why? Pretty much everyone got hacked, so no harm was done.
Well, who solved D before solving some other problems, will get more penalty than others, it's not a unfair?
What about those who tried D first?
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 :)
They announced that during the contest so people had time to fix their code.
Making this round unrated would also be really unfair to many contestants.
Don't worry. It seems to be rated, you are gonna be blue.
As long as nothing bad happens in the next 10 hours. :)
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.
AkiLotus
anyone higher than this?......
For now I can assure that nobody surpassed my record of 18 unsuccessful attempts in this contest xD
neko_nyaaaaaaaaaaaaaaaaa
81 hacks in a rated contest!
hacks is effectless in educational contests. :)
It's rated for Div 2. People will lose rating because they placed lower because they got hacked.
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.
I mean who hack someone else don't get lower penalty. so 81 hacks isn't good for him.
Everything happens for a reason. Maybe he'll find his own good in doing this (not obliged to be ratings/penalties) ;)
Right. :)
Why was the clarification "isn't" instead of "is NOT"?
Yes that is my concern too.
i read "it is guaranteed" instead of "it isn't guaranteed" when the notification had come.
same for me bro
Same :)
Same :)
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 !!
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.
yeah, prefix sum and map of occurrence only, got hacked too 33189540
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 :)
Yeah and a lot of people submitted their submission before the announcement :/
thanks man
Будет ли раунд для второго дивизиона рейтинговым, ведь реально не справедливо к задаче Д
Странный вопрос от человека, который не участвовал в раунде.
How to solve E ?
Someone mentioned calculating hamming distances for string, idk if that's true.
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)
Wanted to know rating predicted by CF-Predictor: Predicted <= Rating_Increase (Because Div1 would be removed), Predicted > Rating_Increase (As seen in last round)
Which would be true. If 2nd one, why is it so?
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_Increase
Which would be true. If 2nd one, why is it so?
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.
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
1instead ofy-xwhen the condition|x-y|>1is setisfied. Then the problem come up to be: [calculate the number of pairsai,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 pairsai,aj, so it isn*(n-1)/2+n, and sincencan be equal to2×10^5, we surely need to uselong long intdata type.]. All what we said was a result of our habit that the answer is eitherintorlong long, but this is not enough for a problem solver.when the rating update will be published ?
After System Testing with the all the hacks that have been submitted during the hacking phase.
Errr, may I ask why my rating haven't changed? I'm sure I'd played this game.
the answer in problem d can exceed 10^18 It is very unfair for c++ coders
How so? You shouldn't be able to slap long long onto every answer that will be an integer and expect it to work.
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
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.
But next_permutation is easier to code than bigint lol :D
How about nth_element :D
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.
When will the editorial be published?
after finishing hacking operation
But, they published it earlier last time.
NaCl
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!
How to solve F?
Use bitmask DP: http://codeforces.net/contest/903/submission/33215290
Represent 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.
Can you explain it in more detail. I didn't get it.
The integer overflow problem in Div2 D can be solved by using long double instead of long long in c++.
My solution
I am surprised that there are so few discussions about how to solve problem G.
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.
Completely agree. Moreover, people who had a correct solution from the beginning lost rank due to other people's resubmissions.
when will rating change take place?Hacking period is over
I don't think they've run the system tests with the hacks yet.
RIP rating :'v
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'.
I got AC in D with c++ without bigint.
You are molodchina
molodchina Means ??
This is a Russian humor. "Molodhina" = "молодчина!".
This phrase can be translated as "Congratulations!" (and also as "Good job!" or "Well done!").
Will you make a list of the top Div 2 competitors? :D
In problem D, why double gives WA on test 13 while long double gives AC ?
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
Can someone please explain F ? I do not understand it from the editorial.