Блог пользователя NelsonMondialu

Автор NelsonMondialu, 4 года назад, перевод, ,

Всем привет!

Приглашаю вам принять участие в двухчасовом Div2 раунде, который состоится в эту субботу 30-го августа в 11:30 по московскому времени. Как обычно, участники из первого дивизиона могут решать задачи вне конкурса.

Задачи были подготовлены мной и MirceaFF (задачи B и C). Хочу сказать спасибо Gerald за помощь в подговке раунда, MirceaFF за перевод задач на английский и MikeMirzayanov за создание Codeforces.

Главными героями задач сегодняшнего раунда будут Caisa и Gargari. Надеюсь задачи вам понравятся. Желаю удачи и удовольствия от контеста!

UPD: Будет использоваться стандартная разбалловка.

•
• +222
•

 » 4 года назад, # |   +96 First time to take part out of competition :)
•  » » 4 года назад, # ^ |   +6 Also for me, I'm not waiting for it as hard as I waited before :)
•  » » » 4 года назад, # ^ |   +26 Congratulations ! Maybe you can become a nice couple (●′ω●)
•  » » » » 4 года назад, # ^ |   +20 too late man I already got Engaged :P
•  » » » » 4 года назад, # ^ |   +8 Well that escalated quickly :P
•  » » » » » 4 года назад, # ^ | ← Rev. 2 →   0 ignore.
•  » » 4 года назад, # ^ |   -9 But you can solve problems ,but your ratings will not change :)
•  » » 4 года назад, # ^ |   0 Second time!
 » 4 года назад, # |   0 I think this is the first round made by someone from Vaslui (my hometown, too) :D My round is coming soon :P
 » 4 года назад, # |   0 The day is just to sign up for a new term, and it's afternoon in China! we happen to have much time for it ^_^ !
•  » » 4 года назад, # ^ |   -11 Yes. I just think I saw it by mistake.
•  » » 4 года назад, # ^ |   -8 I'm from China too.It's a good contest time:)
 » 4 года назад, # |   +1 Very unusual contest time! :DI think there will be a high decrease of the number of registrants! Good Luck.
•  » » 4 года назад, # ^ |   +3 That is because in the same day there will be topcoder SRM + Hackerrank 101 hack august
•  » » » 4 года назад, # ^ |   +1 Oh! I didn't know these! Do the times have interference too?
•  » » » » 4 года назад, # ^ | ← Rev. 3 →   +4 Fortunately not, you can see them here
•  » » » » » 4 года назад, # ^ |   0 Thx very much, it help me much.
•  » » 4 года назад, # ^ |   0 It will surely increase there are a great number of chinese coder will join:)
•  » » 4 года назад, # ^ |   0 4077 registrants... :) In round 263 there were 3988 registrants...
 » 4 года назад, # |   0 Please add time conversions :)
•  » » 4 года назад, # ^ |   0 You can check time conversion from contests -> current contest and click on the time given :).
•  » » » 4 года назад, # ^ |   0 Oh, cool
•  » » 4 года назад, # ^ |   +9 According to this comment, you are not a programming contest addict... :PYou know you are a programming contest addict when : You have become the master of converting timezones to your country's standard time.
•  » » » 4 года назад, # ^ |   0 Hahaha, I became used to clicking the links in announcement post to check.
•  » » » 4 года назад, # ^ |   +20 That is an implication. But is it an equivalence?
 » 4 года назад, # |   -9 Very nice. I will do my best to do this round and get >1700 rating.
•  » » 4 года назад, # ^ |   0 Best of luck! I hope I take part in this contest(I don't like the time of this contest) . If I do, I wish I atleast become blue again.
•  » » » 4 года назад, # ^ |   +6 I wish you good luck. :D
•  » » 4 года назад, # ^ |   0 According to my own experience, I think that you will stay in expert for a few rounds before getting to div1
 » 4 года назад, # |   0 finally a chance to participate in a good time :D
•  » » 4 года назад, # ^ |   0 Not a good time for US though: 12:30 AM to 3:30 AM depending on the time zone...
 » 4 года назад, # |   +3 Converted Time Washington DC, District of Columbia, U.S... 3:30 AM EDT http://fc02.deviantart.net/fs71/f/2013/281/0/0/sleep_is_overrated__by_austin_comix_inc-d6ps3kj.gif
•  » » 4 года назад, # ^ |   -6 narcis_vs tnks for this contest :)
 » 4 года назад, # |   +1 There wasn't any hurry for posting the blog :D
 » 4 года назад, # | ← Rev. 2 →   -6 alert("dsjgds");
•  » » 4 года назад, # ^ |   +1 what does it mean? :)
•  » » » 4 года назад, # ^ |   +3 XSS
 » 4 года назад, # |   +5 Всегда бы такое время =)P.S. Я не садист и не мазахист, обычное время для контестов 19:30 для меня — это 2:30 ночи, а в это время мозги обычно уже не соображают совсем.
•  » » 4 года назад, # ^ |   +1 Ну извини) ладно летом и в выходной такое время. То еще можно написать. А если в будни и для московского времени, кто-то работает, кто-то на учебе. Не особо подходящее).P.S. Хотя в этот раз для меня отлично вышло. В 19.30 не успел бы написать)
 » 4 года назад, # |   +11 May be i will Miss this contest Due to My Exam
•  » » 4 года назад, # ^ |   +3 My exams ended 3 hrs before contest. Yay!
 » 4 года назад, # |   0 is there any contest for beginner problem solving to start practice with ?? HELP
•  » » 4 года назад, # ^ |   +5 Take any previous contest in virtual mode, for beginners DIV 2 is the place. Why not try the last contest itself : Click here Simply register and familiarize yourself with how a codeforces round actually is.
 » 4 года назад, # |   0 very excited about contest. First time to unofficially participate!!! Hoping to solve ABCD for first time :)
•  » » 4 года назад, # ^ |   +24 Since solving AB doesn't really give you anything and there's no rating to lose, you should start from D or E. These div2 contests are a true golden mine for trying out risky new approaches :D
•  » » » 4 года назад, # ^ | ← Rev. 2 →   0 Good advice :). I'll probably start from C, try D+E, then go to ABAlso, do you read all of the problem statements before starting to work on any problems?
 » 4 года назад, # |   0 I want have a good grades in this contest,bless all!
•  » » 4 года назад, # ^ |   -11 thanks(!):D
 » 4 года назад, # |   +4 I hope the problems have something to do with elegant graphs/dp/trees/combinatorics problems and not some greedy approach with a lot of conditions and corner cases!
 » 4 года назад, # |   0 Hope the problems will be interesting. Let's enjoy it. :)
 » 4 года назад, # | ← Rev. 2 →   0 this is my first contest
•  » » 4 года назад, # ^ |   +6 New genius one?
•  » » » 4 года назад, # ^ | ← Rev. 2 →   +2 no, i'm not genius
 » 4 года назад, # |   0 Waiting for a nice problemset!!
 » 4 года назад, # |   +1 good time for contest :) <3
 » 4 года назад, # |   0 А где же всеми любимый персонаж контестов Яблов?
 » 4 года назад, # |   0 Объясните пожалуйста, почему, когда я пытался открыть свой код на задачу С, который хакнули, у меня КФ сразу же зависал, и приходилось просто закрывать страницу.
 » 4 года назад, # |   +6 условие задачи A. Один я понял, что виды это не обязательно 1 мешок сахара?
•  » » 4 года назад, # ^ |   0 я сначала также подумал, что можно купить не 1, а несколько пакетов сахара
•  » » 4 года назад, # ^ |   +6 Нет, там ничто об этом не говорит, кроме 5 теста
•  » » 4 года назад, # ^ | ← Rev. 2 →   0 В супермаркете всего имеется n различных видов сахараКакое максимальное количество конфеток в качестве сдачи Caisa может получить, если купит ровно один вид сахара?Я здал задачу, но до сих пор не понимаю, можно купить только 1 мешок какого либо вида сахара?Если можно покупать много мешков, то на тест 1 10 2 30 у автора не правильное решениеУже понял, Каиса хочет купить только 1 сахар
•  » » 4 года назад, # ^ |   0 Я вообще сначала норм понял задачу, но одно лишнее условие написал, поэтому ВА3. Потом стал думать, что этот придурок таки хочет несколько пачек купить и ВА5. Успел решить Б, С (упала на частном случае) и Д, и только когда до конца оставалось 1-2 минуты — понял как должно быть.
 » 4 года назад, # | ← Rev. 2 →   0 What was the solution of problem D?I starting taking the LCS of the first and seccond line. And then LCS the result with the third line and ... (LCS calculation was DP — But I called it recursively for the new check).I got segmentation fault. Does anyone know the reason? Is my algorithm correct?
•  » » 4 года назад, # ^ | ← Rev. 2 →   0 My idea was same too, but this technique wouldn't pass the sample I/O. I mean if there is several subsequence with same length , which one would you consider ? For examplebetween 1 4 2 3 4 1 2 3 you have 1 2 3 and 4 2 3 , which one would you choose for 1 4 2 3 , here it is obviously 1 2 3 eventually you have to try all the sequences. I think there are some other technique.
•  » » » 4 года назад, # ^ |   0 I think they should have accepted all of the possible answers.
•  » » 4 года назад, # ^ |   -12 You must use suffix automat.(Sorry for mistakes ) :D
•  » » 4 года назад, # ^ | ← Rev. 3 →   0 This problem is as like as SPOJ: X-MEN Difference is in the problem of spoj, we have to find out LCS between only one pair. But In D of this round, we have to find out LCS between each pair. And it is possible, as maximum value of k can be 5.*** The problem of SPOJ(given above) can be converted into LIS... Then I solved it in nlog(n).
•  » » 4 года назад, # ^ |   +10 Your algorithm is not correct, because there could be more than one LCS.The solution is quite simple — for every you make a vector Vx = {a1, ... ak}, where ai means position of x in i-th permutation. Now you create a directed graph — iff . Now an observation — if u1, u2, ..., um is a common subsequence, then u1, ... , um is a path in our graph. So now your problem is to find the longest path in a graph. But this is a DAG, so it is easy — you can either make a topological sort, or just brute it in O(n2).
•  » » » 4 года назад, # ^ |   0 Can you explain the graph creating part a bit please , I mean this part .
•  » » » » 4 года назад, # ^ |   +1 Sure. Let's look at positions of numbers 1 and 2 in our permutations. {x1, ..., xk} are positions of 1 (i.e. in i-th permuation number 1 is on xi -th position) and {y1, ... , yk} are positions of 2. Now we create a graph with vertices labeled with 1,2,...,n.When x1 < y1, x2 < y2, ... xk < yk, then we create a directed edge from vertex 2 to vertex 1. In other words, we create such an edge when in each permutation 2 comes after 1.
•  » » » » » 4 года назад, # ^ |   0 it seems we can't do bitmask DP over k. At least my code failed. Could you give me a hint why? I do not get why it fails. :(
•  » » » » » 4 года назад, # ^ |   0 Thank you , a little question though , if the array was not a permutation , i.e there was repeated numbers , could we have solved the problem using similar approach ? I mean can the normal lcs problem be solved like this?
•  » » » » » 4 года назад, # ^ |   0 Thanks for nice explanation :)
•  » » » 4 года назад, # ^ | ← Rev. 3 →   0 it seems we can't do bitmask DP over k. At least my code failed. Could you give me a hint why? I do not get why it fails. :(
•  » » 4 года назад, # ^ |   +3 That will have problems in case of multiple LCSs. Eg, consider (1,2,3,4,5), (1,2,3,5,4) and (4,1,2,3,5). First two have two LCS : (1,2,3,4) and (1,2,3,5). If you took only one, and that was (1,2,3,4), then you will get final answer 3, whereas the final answer is 4.
•  » » 4 года назад, # ^ |   0 The trick here is that input is a permutation (no repeats). Hope this gives a hint to those who still want to think about D.
•  » » 4 года назад, # ^ |   0 i donot think u need all of that there is a very important observation which is for every sequence the numbers are found only once so u can save the index of every digit for every sequence and try to start with any of them but u will need to know the last digit taken so that the sequence in valid then u check if all the numbers are in valid position (after the last number) u add this digit in all the sequences to the solution so the state will be (last digit taken) and u will have a loop on the all the digits except the last one trying to choose any valid digit sorry if it seems a little bit messy or alot
 » 4 года назад, # |   0 Pretest 2 for problem E seems so strange...... So many people get WA or RE on this......
 » 4 года назад, # |   +4 Div.2 B — find max?
•  » » 4 года назад, # ^ |   +3 yup
 » 4 года назад, # |   0 What is the explanation of B seriously -_- . I first thought that it may be the maximum number . But I couldn't prove it. But at the last of the just before 3 min contest I see B was solved more than A , So , I just submitted by calculating the maximum number. I don't know if it is true though.
•  » » 4 года назад, # ^ |   0 It seems to be obvious that in each step the current energy is equal to h[0] — h[current_step], so you just need to increase h[0] (from 0 to max(h[]))
•  » » 4 года назад, # ^ |   +1 Instead of increasing height of some pylons you can just increase on all your money height of the first pylon, answer would be the same because increasing height of the first pylon just increases your starting energy. So you calculate minimum energy on the way and then add this energy (or 0) as a height to the first pylon.
 » 4 года назад, # |   +1 Problem C?
•  » » 4 года назад, # ^ |   +1 make dp matrix for 4 diagonal you will need 4 dp arrays for that one to add dollars from up-left and from bottom-left , up-right , bottom-right. then make another dp matrix to collect all of them dp[i][j]=dp1[i][j]+dp2[i][j]+dp3[i][j]+dp4[i][j]-3*mat[i][j] --> mat[i][j] is original value we subtract 3 of them because we add the same cell 4 times and we need just once. one observation is that the one bishop will be on white cell and another will be on black one (like a chess board) because problem statement says that "there is no cell that is attacked by both of them" if you tried to put both on white cells you will see there is a cell attacked by two , try it so just loop on all i,j in dp and take maximum in black cells and maximum in white one and result is the sum. feel free to ask
 » 4 года назад, # |   0 When 1 hours remaining, then my father call me and come to eat pizza..:
 » 4 года назад, # |   +12 Скажите мне пожалуйста, как можно понять, что в задаче A можно покупать только одну единицу какого-либо вида сахара? Написали бы, что это какой-то товар в единственном экземпляре, чтобы не путать бедных участников. Такое неверное понимание не только проходит оба претеста, но и проходит еще два теста после них.
 » 4 года назад, # | ← Rev. 2 →   0 Скажите пожалуйста почему на первую задачу на тест1 10 2 30авторское решение выдает 70? Вроде бы должно 80UPD Вопрос снят.
•  » » 4 года назад, # ^ | ← Rev. 2 →   0 Потому что сдача будет равна семи долларам и 70 конфетам
•  » » » 4 года назад, # ^ | ← Rev. 3 →   0 а если взять 4 сахара, то выйдет 9.20, то есть здача 0 долларов и 80 конфет.
•  » » » » 4 года назад, # ^ |   0 Покупать можно только один раз
•  » » » » 4 года назад, # ^ |   0 увы, можно брать только 1 мешок сахара
•  » » 4 года назад, # ^ |   0 Вы за $10 покупаете сразу целый "вид" сахара, который стоет$2 30ct. Вам дают сдачу $7 и 70 конфеток.  » 4 года назад, # | 0 Объясните, пожалуйста, почему это некорректный тест для Сшки?http://pastebin.com/YWWKHb6yхотел по TL завалить, отправил этот тест за 10 секунд до конца и получил "некорректный тест", а там решение за куб было, обидно.Валидатор выдал "ожидался EOFL". •  » » 4 года назад, # ^ | 0 у меня также было, решилось добавлением пробела в конец файла •  » » » 4 года назад, # ^ | 0 Странно, что написанный руками тест с таким же форматированием, но меньшим размером валидатор принимает. •  » » 4 года назад, # ^ | 0 В конце вывода зачем убрали '\n' ?  if (i + 1 < N) cout << endl;  •  » » » 4 года назад, # ^ | +5 До этого он был, но был еще в конце каждой строки пробел. После отправил без пробелов и пустой строки. Следующая попытка была бы без этих 2х строк кода, но времени уже не было. Не знал, что нужна пустая строка в конце. Спасибо! =)  » 4 года назад, # | 0 Я упоролся, или в Е все-таки нужен персистентный массив? •  » » 4 года назад, # ^ | 0 Если бы апдейтов было много, то, возможно, было бы так. С таким маленьким их количеством можно спокойно все перестраивать и чистить. •  » » 4 года назад, # ^ | +3 Думаю можно запрос второго вида можно за линию делать(их не больше 50 по условию), то есть обновлять значения до корня. •  » » 4 года назад, # ^ | 0 а как нужно решать задачу с помощью персистентного массива?  » 4 года назад, # | 0 Как решать D и E? •  » » 4 года назад, # ^ | ← Rev. 3 → 0 С: Если слоны стоят на одном цвете (шахматной доски), то линии их атак обязательно пересекутся. Значит решаем отдельно для одного слона на белых клетках и для другого на черных. Просто перебираем позицию, а сумму можно посчитать динамическим программированием. •  » » » 4 года назад, # ^ | +3 это C :) •  » » » » 4 года назад, # ^ | 0 ахах) •  » » » » 4 года назад, # ^ | ← Rev. 2 → +3 Сорри. D (настоящая): Динамика dp[i] — максимальная НОП, что в первой перестановке она заканчивается perm[0][i] элементом. Переберем предпоследний элемент в первой перестановке. Проверим, что в других перестановках он тоже идет раньше, чем perm[0][i], если это так, то срелаксируем динамику dp[i] = max(dp[i], dp[j] + 1), где j — индекс предпоследнего элемента в первой перестановке. •  » » » » » 4 года назад, # ^ | 0 Отличная идея. Буду знать) Спасибо •  » » » 4 года назад, # ^ | 0 Это С :) •  » » 4 года назад, # ^ | -14 D — суффиксный автомат. Нa e-maxx.ru почитай, там в разделе суффиксный автомат в самом низу про наибольшую общую подпоследовательность нескольких строк. •  » » » 4 года назад, # ^ | ← Rev. 2 → +9 Можно и гвозди микроскопом забивать, но можно просто идти в порядке упоминания элементов в любой из перестановок и решать обычную задачу LCS за квадрат. •  » » » 4 года назад, # ^ | +11 Эм, задача решается сведением к задаче о нахождении наибольшей возрастающей подпоследовательности за O(n2), где элементы последовательности — вектора позиций элементов a0 в каждом ai. •  » » » 4 года назад, # ^ | +16 И, кажется, что суффавтомат тут не работает — он ищет подстроку, а не подпоследовательность. •  » » 4 года назад, # ^ | ← Rev. 21 → 0 Я в D сделал так: сначала построил ориентированный граф по первой перестановке. От i - го элемента до всех, кто справа. Затем повычеркивал ребра, которые противоречат остальным перестановкам. А далее задача о максимальной подпоследовательности на полученном графе. Вроде работает =) O(K * N2 * logN)  » 4 года назад, # | ← Rev. 3 → 0 Nice contest Narcis and Mircea! I'm a little bit surprised that there are more pretest passed submissions on B than on A (because B was trickier in my opinion). A was very good for Div2. About C I would like to say that it's nice. I liked D the most, because it's really beautiful despite its very simple input. Initially I thought that E is some kind of HLD with segment tree, so didn't try it for long. Got the right idea in the last 20 minutes (some kind of sorting + DFS). Not the most prolific round for hacking though. Anyway, keep up the good work.P.S.: Caisa is a really nice name for a task hero. Don't you think? (image) I'm curios what does Gargari comes from.  » 4 года назад, # | -30 Контест на реализацию. Скучно :\ •  » » 4 года назад, # ^ | ← Rev. 2 → +9 Тогда почему же Вы не реализовали D и E?UPD: да еще и С •  » » » 4 года назад, # ^ | ← Rev. 2 → -29 Я не умею писать суффиксный автомат(D). Алгоритм описан на e-maxx.ru. Тривиальная задача. UPD: сорри, тупанул) (я же говорил, что не разбираюсь в суф. автомате) :) •  » » » » 4 года назад, # ^ | +19 Там не суффиксный автомат. Повторюсь, он ищет подстроку, а не подпоследовательность. •  » » » » 4 года назад, # ^ | +16 там наибольшая общая подстрока находится  » 4 года назад, # | +6 I missed a hack attempt in problem C. At 01:56 (4 minutes remaining), I saw a solution with overflow problem. I then wrote a code to generate worst case of 2000x2000 with all entries 10^9. Submitted at 01:59:57 ... It itself TLEd!... Then it striked that a 2x2 matrix would have been sufficient. LOL !! =(  » 4 года назад, # | +7 What a contest! I hacked for the first time! •  » » 4 года назад, # ^ | +17 What a contest! I was hacked for the first time! :/  » 4 года назад, # | 0 Does anyone know how to solve C?I precomputed the sums for each position where a bishop could be placed in O(n^2), but I don't know how to find the pair of bishops without checking each possible pair. •  » » 4 года назад, # ^ | +1 Find the best bishop for (i+j)%2=0 and the best bishop for (i+j)%2=1, then add them. Like the board for chess. •  » » » 4 года назад, # ^ | 0 Why is this necessary? What if two bishops are placed in squares who are equivalent modulo 2 and they don't attack each other ? •  » » » » 4 года назад, # ^ | 0 Give me example, please) (When two bishops are placed in squares who are equivalent modulo 2 and they don't attack each other) •  » » » » » 4 года назад, # ^ | +5 Oh sorry, Just realized that is not possible as as soon as you select a bishop , if you draw a line on the board along the square's diagonals , you have divided the board into two halves. Now if you place a bishop in another equivalent square (modulo 2) you have to cross this line which will have an intersection and that square will be attacked by both the bishops. •  » » » » » 4 года назад, # ^ | ← Rev. 2 → 0 I have to disagree with you here. Two Bishops attacking each other will have to be in the same diagonal. There is a difference between "two bishops attacking each other" and "two bishops attacking the same cell". The problem statement failed to differentiate between these two. Read this wolfram article. Cell (2,2) and (0,2) will both attack cell (1,3) but they are not directly attacking each other. •  » » 4 года назад, # ^ | 0 colors of bishops should be different •  » » 4 года назад, # ^ | 0 You don't need to check each and every combination of pairs. It is stated in the problem statement that "No position should be attacked by both the bishops", this made the problem simpler.Now you need to check the max for bishop on black positions and max for bishop on white position and add those. Thats it :) •  » » 4 года назад, # ^ | 0 If you look carefully then you will see the board is bipartite.A white bishop cannot attack a black one. So find the max black diagonal and max white diagonal. answer is the summation. •  » » 4 года назад, # ^ | 0 Oh, I missed that part. Thanks! •  » » 4 года назад, # ^ | 0 Well , I think you know what a white cell and black cell in chess is. Now see , if you place a bishop in a black cell than you can't put the other in black too. because then they would attack atleast one common cell . try drawing it in paper. So , the problem is no bishop lines intersect each other. so you calculate for each one seperately like this //first bishop for(int i=1;i<=n;++i) int j; if(i%1) j=1 // for second bishop , j=2 else j=2 // for second bishop, j=1 for(;j<=n;j+=2) // calculate sum from fourcorners if(sum>bishop1Max) //change max value and position   » 4 года назад, # | 0 why so many people get wrong answer on pretest 5 in DIV 2 A problem ? •  » » 4 года назад, # ^ | -14 I didn't) •  » » » 4 года назад, # ^ | 0 Well done!!! •  » » 4 года назад, # ^ | +1 they thought they can buy more than one pocket with sugar •  » » 4 года назад, # ^ | 0 This is tricky test case. 1 9 9 0 Output:0 not -1 •  » » 4 года назад, # ^ | +1 i got wrong answer because i do not see anywhere written that you cannot buy more that one unit of same sugar. I still do not see that, can someone please point out where it is mentioned in the problem A Div 2.  » 4 года назад, # | 0 Отдавайте переводить условия лучше Маше. "Какое максимальное количество конфеток в качестве сдачи Caisa может получить, если купит ровно один вид сахара? Обратите внимание, что Caisa не старается минимизировать стоимость покупки, она хочет получить как можно больше конфет."Как из этого я должен был понять что нужно покупать всего один пакет? •  » » 4 года назад, # ^ | 0 если купит ровно один вид сахара •  » » » 4 года назад, # ^ | 0 Вы имеете ввиду несколько пакетов одного и того же? •  » » » » 4 года назад, # ^ | +1 да, я так и делал. От куда я должен был узнать что количество ОДНОГО ВИДА, тоже один? •  » » » » » 4 года назад, # ^ | 0 Да, обидно вышло. Хорошо, что участие вне конкурса) •  » » » » » » 4 года назад, # ^ | 0 Для кого то коркусный тур) я вот зделал кучу попыток) а вторую здал через 13 минут после первой •  » » » » » 4 года назад, # ^ | 0 Я и в С подумал что "Gargari хочет разместить на шахматной доске два слона таким образом,что не существует клетки, которая находится под ударом обоих слонов."означает лишь то, что не надо учитывать клетку, когда ее бьют двое.  » 4 года назад, # | 0 Hi, I am a newbie for Codeforces. I found that I was unable to view the results of pretest of my submissions. Everytime I clicked the number linking to the submissions which failed on pretest, the popup was just displaying my source code but no pretest results. And in the direct link of the submission was also just displaying the source. Any can help? Thanks in advance. •  » » 4 года назад, # ^ | ← Rev. 2 → 0 this is only possible during practice. In contest You have to figure out by yourself :) •  » » 4 года назад, # ^ | 0 You can't see your output.. You have to figure it out yourself •  » » 4 года назад, # ^ | 0 That is the intended behavior during a codeforces round. You do not get to see the pretest that caused your program to fail. •  » » 4 года назад, # ^ | 0 You can not see pretests during the round. You must find a wrong test and mistake in your solution yourself. •  » » 4 года назад, # ^ | 0 You cannot see pretests during the contest ;)  » 4 года назад, # | 0 Does anyone know the second test case of C?  » 4 года назад, # | 0 This is very good contest that I participate first time but I could not solve any problems :D  » 4 года назад, # | 0 in problem C change ll mx1=0,mx2=0; to ll mx1=-1,mx2=-1; Accepted :( :( •  » » 4 года назад, # ^ | +3 Or use <= instead of < when comparing. I had the same bug unfortunately ^^ •  » » 4 года назад, # ^ | +3 Same :D •  » » 4 года назад, # ^ | +6 Same things happen with me SmartCoder ; At least this contest was unofficial for me :P •  » » 4 года назад, # ^ | ← Rev. 2 → 0 I got TLE for using cin/cout :/ •  » » » 4 года назад, # ^ | 0 I got both the problem :p pity for me -_-  » 4 года назад, # | 0 Too fast systest!!When I saw my ranking it was at 30% testing. In a few (~30) seconds, after I again checked the dashboard, it was 100%. I was expecting it to be around 40 — 60 at that time.this is unbelievably fast!  » 4 года назад, # | 0 Как посмотреть тесты по С? Они у меня не высвечиваются. •  » » 4 года назад, # ^ | 0 Уже высвечиваются :)  » 4 года назад, # | +1 Подскажите, пожалуйста, почему мое решение (http://codeforces.ru/contest/463/submission/7638490) словило ТЛ? •  » » 4 года назад, # ^ | ← Rev. 2 → +3 cin'ом считывать долго, напиши в начале main'на ios_base::sync_with_stdio(0) и получишь accepted. •  » » » 4 года назад, # ^ | +1 Да что ж за лажа такая... Не думал, что настолько долго. Все понял, спасибо.  » 4 года назад, # | 0 Please, could you tell how to count the sum that gives the black bishop using dynamic programming •  » » 4 года назад, # ^ | +9 The better solution is to use array sum[2][N*2]. sum[0] — sums of LT-RB diagonals, sum[1] — sum of LB-RT diagonals. To calculate such array you need only two formulas: sum[0][i+n-j-1] += a[i][j] sum[1][i+j] += a[i][j] Then the answer for (i,j) is sum[0][i+n-j-1] + sum[1][i+j] - a[i][j]. That's all. •  » » 4 года назад, # ^ | 0 Just like Prefix sum  » 4 года назад, # | ← Rev. 3 → 0 cin/cout gets TLE for problem C and scanf/printf AC ? Seriously ? Nice... •  » » 4 года назад, # ^ | 0 Me too!I want explanation! •  » » » 4 года назад, # ^ | +3 cin is like a turtle. Very slow turtle. •  » » » 4 года назад, # ^ | 0 I agree !! I knew this happens on some OJs, but it never happened to me on CodeForces. Maybe the authors are inexperienced and missed that, maybe they should reeval. •  » » 4 года назад, # ^ | +4 Use ios::sync_with_stdio(0); In case cin/cout is too slow, this line speeds them up  » 4 года назад, # | +9 Did anyone else too misread problem C as placing bishops such that they do not attack each other, rather than placing bishops such that they do not attack any common cell. I wasted an hour on this before realizing I had misread the problem. •  » » 4 года назад, # ^ | +1 I wasted half an hour because i thought that they were rocks and i don't know how :D then i wasted another half thinking that they mustn't attack each other :Dstrange contest time leads to weird results :D •  » » 4 года назад, # ^ | 0 Exactly I even coded that to realise at 1:42 the insane thing i did. •  » » 4 года назад, # ^ | 0 I calculated that max cost is 4n-4, only to realize that weights of the cells were input based. (i assumed 1!) •  » » 4 года назад, # ^ | 0 Same here. The problem becomes much harder with this "new" statement.  » 4 года назад, # | 0 Please publish a complete editorial and update ratings fast :)Thanks  » 4 года назад, # | 0 in problem B wouldn't it be sufficient to find the maximum pylon and print it out ? •  » » 4 года назад, # ^ | 0 Yes it would be. Printing the maximum of the numbers would do.  » 4 года назад, # | ← Rev. 3 → +7 For Prob A, if the input is 1 6 2 80 then, he can either buy just one for 2$ 80cents, and get 20 candies in return or, he can buy 2 worth 5\$ 60cents, and get 40 candies in return. So, the answer should be 40 candies, and not 20.I interpreted the problem in the above mentioned way. It was mentioned that he can purchase only one type of sugar, but it was not mentioned that he can purchase only one quantity of that type. I ended up wasting over an hour over this ambiguity.Am I correct?
•  » » 4 года назад, # ^ |   0 Same with me,I think for 1 10 0 70, answer should be 90 (because 3 times of same type can be taken) but for all the AC solutions, the answer gives 30...WTH?!?!?
•  » » 4 года назад, # ^ | ← Rev. 2 →   0 I made the same mistake and cost me 2 WAs. however, maybe the problem setter wrote this line there are n types of sugar in the supermarket, maybe he able to buy one. to inform us that he can buy only one pocket of sugar.I think the problem statement should've been clearer .
•  » » 4 года назад, # ^ |   0 Same here. The problem statement was not clear. I did the same and ultimately was not able to solve this. I do think due to ambiguity of problem A . More people solved problem B.
•  » » 4 года назад, # ^ |   0 Same with me! He can buy several kilos of sugar and get more candies for some cases. Problem has incorrect description I think.
 » 4 года назад, # |   +11 Weak test cases for problem E. Even brutes are accepted.TLE by cin and AC using scanf.very upset by the contest.
•  » » 4 года назад, # ^ |   0 Maybe test cases for problem E were generated randomly.
 » 4 года назад, # |   0 :( Just changed cin to scanf on problem C an got AC, it's ok to get TLE because of reading method or the most important part is the algorithm and it complexity ??
•  » » 4 года назад, # ^ |   +3 Si eu la fel :))
•  » » » 4 года назад, # ^ |   0 problem B is very very easy :D
 » 4 года назад, # |   0 As a Chinese I do not think there's no difference between "type" and "number".
 » 4 года назад, # | ← Rev. 2 →   +6 Походу через 2-3 контеста, worse станет белым) (Там видна белая полоса))
•  » » 4 года назад, # ^ |   0 Старается изо всех сил!
•  » » 4 года назад, # ^ |   0 Нет, это асимптота =)
•  » » 4 года назад, # ^ |   +9 Уже скоро, совсем скоро...
 » 4 года назад, # |   0 Problem C got TLE just because of cin\cout.Without it I can become candidate master.Such a bad contest
•  » » 4 года назад, # ^ |   +2 Me too
•  » » 4 года назад, # ^ |   0 Same
 » 4 года назад, # |   0 Why this solution is wrong? I used DP over bitmaks of set of sequences and looked for the longest common subsequence.
 » 4 года назад, # |   +1 can anyone tell me why i am getting TLE in problem C my complexity is O(n*n) solution code LINK.
•  » » 4 года назад, # ^ |   0 Maybe because cin is very slow
•  » » 4 года назад, # ^ |   +1 You use cin. It's too slow. I made the same mistake
 » 4 года назад, # |   +4 Nice Round!
•  » » 4 года назад, # ^ |   0 it isn't surprising
 » 4 года назад, # | ← Rev. 5 →   +15 Stop ZLD! Why you create so many accounts for div.2!
 » 4 года назад, # | ← Rev. 2 →   +2 Difference is only a cin function :( too much pathetic :'(
•  » » 4 года назад, # ^ |   0 Same here
•  » » » 4 года назад, # ^ |   0 Usually this n't happen in CF :( TLE for cin instead of scanf :(
•  » » » 4 года назад, # ^ |   0 Same here
 » 4 года назад, # |   0 nice round! +169 expert again! hoho!
•  » » 4 года назад, # ^ |   0 congrats IvanJobs :)
 » 4 года назад, # |   0 Впервые во время раунда решил 4 задачи... Впервые во время раунда решил задачу D... и как назло упала С...
 » 4 года назад, # |   0 Where is tutorial?!!
•  » » 4 года назад, # ^ |   0 you can play clash of clans . IT's best.
 » 4 года назад, # | ← Rev. 2 →   +2 Country Wise Standings has been updated.
 » 4 года назад, # | ← Rev. 2 →   +6 The E's system test may be too weak.If the tree is a long link with all nodes is 2 with the deepest node is 3. And I query the last node every time. There seems many AC solutions cannot pass this case.The data maker by python: n = 100000 print n, n for i in range(n - 1): print 2, print 3 for i in range(n - 1): print i + 1, i + 2 for i in range(n): print 1, n Maybe I am wrong. Please reply to point it out.
 » 4 года назад, # |   +8 Stats about hacks can be found here.
 » 4 года назад, # |   0 how can i solve C in O(n^2)? the number of black and white cells can be up to (n^2)/2so.. for white_x for white_y for black_x for black_yi thought O(n^4) but it seems wrong.. sorry for dumb question and bad english
•  » » 4 года назад, # ^ | ← Rev. 2 →   0 Compute the value for each rightwards diagonal and leftwards diagonal . Now iterate through the whole 2D array , Find the value for that particular cell as (leftDiagVal(cell) + rightDiagVal(cell) — X[cell] ) and greedily update the answer for Odd(i+j) and Even(i+j) . //X[cell] is the value input in that cell Answer = Answer_Odd + Answer_Even
•  » » » 4 года назад, # ^ |   0 Just got AC, Thanks
•  » » » 4 года назад, # ^ |   0 How about the following algorithm for C -- (I have not implemented or submitted it because I am way too sleepy and I just can't think, but I would be glad if someone validated this)1) Pre-compute the sum of all diagonals. 2) For every diagonal, there will be exactly at most 2 diagonals where you cannot place another bishop. Except for these (potentially 2 diagonals) calculate the diagonal which will give you the maximum sum by iterating through all the favourable diagonals.3) After doing this, simply iterate through all diagonals, and find sum(diagonal) + sum(max_diagonal_calculated_in_(2))`. Output the maximum sum found here.This is O(n^2). Will this work?
 » 4 года назад, # |   +3 Не подскажите как Е решать? Никак разбора не дождусь.
•  » » 4 года назад, # ^ |   0 Это шутка?Разбор
•  » » » 4 года назад, # ^ | ← Rev. 2 →   +9 Разбор к задачам не прикреплен просто...
 » 4 года назад, # |   +9 The data of Problem E is too weak 7644499 The time complexity of his algorithm is O(q*height) Why can he accept?
•  » » 4 года назад, # ^ |   +11 I found it so... Test is too weak.
 » 4 года назад, # |   0 У вас есть Да! У вас +128 к рейтингу! символично)
 » 4 года назад, # | ← Rev. 2 →   0 Задачи очень понравились, спасибо авторам!(хотя и вчитываться в задачи пришлось больше, чем обычно, что, вообще говоря, странно :)
 » 4 года назад, # |   +1 In problem A Div 2, i got wrong answer because i do not see anywhere written that you cannot buy more that one unit of same sugar. I still do not see that, can someone please point out where it is mentioned in the problem A Div 2.
•  » » 4 года назад, # ^ |   0 "maybe he able to buy one" in the second paragraph?I am not really sure either.
 » 4 года назад, # | ← Rev. 2 →   0 I really appreciated with fast turtorial bcz some problem seems hard for me to understand. After understanding the div2(ABCD) problems, I wrote the why and how here.wrote in chinese. Hope useful for the guys like me^_^
 » 11 месяцев назад, # |   0 In the Div2. C question, I get a TLE when I use cin to scan numbers which is understandable. But when I use fast io for cin, cout; precisely this :ios_base::sync_with_stdio(false);cin.tie(NULL); I get a WA on test1, which runs correctly on my shell though. However, using scanf my answer gets accepted. I have always ignored such fumble. Can anybody please explain me how I can use cin, cout in this case and still not get a tle?TIA.
•  » » 11 месяцев назад, # ^ | ← Rev. 2 →   +1 Here you can find information about sync_with_stdio function. The reason, why you are getting WA is you unsync your streams, so if you are using scanf and cin in one program (as you're using in yours), then you will get undefined result.To use cin/cout with sync_with_stdio, you should not use scanf/printf. In this case it will work properly.