Автор awoo, история, 5 лет назад, По-русски

Привет, Codeforces!

В 12.02.2020 17:35 (Московское время) состоится Educational Codeforces Round 82 (рейтинговый для Див. 2).

Продолжается серия образовательных раундов в рамках инициативы Harbour.Space University! Подробности о сотрудничестве Harbour.Space University и Codeforces можно прочитать в посте.

Этот раунд будет рейтинговым для участников с рейтингом менее 2100. Соревнование будет проводиться по немного расширенным правилам ICPC. Штраф за каждую неверную посылку до посылки, являющейся полным решением, равен 10 минутам. После окончания раунда будет период времени длительностью в 12 часов, в течение которого вы можете попробовать взломать абсолютно любое решение (в том числе свое). Причем исходный код будет предоставлен не только для чтения, но и для копирования.

Вам будет предложено 7 задач на 2 часа. Мы надеемся, что вам они покажутся интересными.

Задачи вместе со мной придумывали и готовили Роман Roms Глазов, Адилбек adedalic Далабаев, Владимир vovuh Петров, Иван BledDest Андросов и Максим Neon Мещеряков. Также большое спасибо Михаилу MikeMirzayanov Мирзаянову за системы Polygon и Codeforces.

Удачи в раунде! Успешных решений!

Так же от наших друзей и партнёров из Harbour.Space есть сообщение для вас:

Hello Muscat

Привет Codeforces!

Мы продлили срок скидки за раннюю регистрацию в Hello Muscat ICPC Programming Bootcamp до этого воскресенья, 16 февраля. Так же помните, что вы можете запросить сопроводительное письмо для представления вашему университету, работодателю или местным компаниям, чтобы они могли спонсировать ваше участие и поездку в тренировочный лагерь.

Зарегистрироваться

А еще мы хотели бы напомнить вам, что если ваша команда отправится на Финал ICPC в Москве в июне этого года, вы можете заполнить форму ниже, чтобы узнать, имеете ли вы право на полную стипендию для нашего учебного лагеря (перелеты не включены), и мы свяжемся с вами в течение трех дней, чтобы сообщить вам о результатах.

Заполнить форму

UPD: В раунде будет 7 задач

Поздравляем победителей:

Место Участник Задач решено Штраф
1 tmwilliamlin168 7 294
2 Egor 6 173
3 ivan100sic 6 174
4 neal 6 175
5 244mhq 6 179

Было сделано 39 успешных и 147 неудачных взломов.

И, наконец, поздравляем людей, отправивших первое полное решение по задаче:

Задача Участник Штраф
A Mprimus 0:01
B icecuber 0:04
C MylnikovNikolay 0:09
D waynetuinfor 0:11
E Mehrdad_Sohrabi 0:17
F wucstdio 1:10
G arknave 0:49

UPD: Разбор опубликован

  • Проголосовать: нравится
  • +167
  • Проголосовать: не нравится

»
5 лет назад, # |
  Проголосовать: нравится +15 Проголосовать: не нравится

Good luck to all participants!!!

»
5 лет назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

second

»
5 лет назад, # |
  Проголосовать: нравится -21 Проголосовать: не нравится

OK, is it possible to achieve 1900 for me?

»
5 лет назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

Auto comment: topic has been updated by awoo (previous revision, new revision, compare).

»
5 лет назад, # |
  Проголосовать: нравится +2 Проголосовать: не нравится

It's time for me to become pupil. Goodbye, my specialist.

»
5 лет назад, # |
  Проголосовать: нравится +25 Проголосовать: не нравится

Codeforces Rounds are very good recently. All the best everyone.

»
5 лет назад, # |
  Проголосовать: нравится +98 Проголосовать: не нравится

Dear author of statement of problem B. Please learn what's the difference between weather and climate.

»
5 лет назад, # |
  Проголосовать: нравится +49 Проголосовать: не нравится

Would be better if D statement said "Your goal is to fill the bag with boxes completely."

It took me some time to understand how the bag and the boxes are related at all.

»
5 лет назад, # |
  Проголосовать: нравится +10 Проголосовать: не нравится

How to solve D ...?

  • »
    »
    5 лет назад, # ^ |
      Проголосовать: нравится +2 Проголосовать: не нравится
    1. Process the exponent (i) from 0 to 62 (actually 60, but it doesn't matter)

    2. If the i-th bit of n is set, then find the smallest existing box that is at least 2**i, then divide it by 2 until it is 2**i, creating two other boxes in each division. Then use a box of size 2**i.

    3. Then use all k boxes of size 2**i to create k/2 boxes of size 2**(i+1)

  • »
    »
    5 лет назад, # ^ |
      Проголосовать: нравится +1 Проголосовать: не нравится

    SUM = sum of all Ai. So if SUM < n answer is 0. else SUM = n + reminder. now go from big powers to small. a = 2^k. if reminder>=a so reminder-=a else if n>=a so n-=a else cnt[k-1]+=2 and start iterate on k-1.

  • »
    »
    5 лет назад, # ^ |
      Проголосовать: нравится +4 Проголосовать: не нравится

    Greedy. First for each power of 2 count how many boxes with this number we have. Then start looking at the bits of n, starting from the lowest one. If this bit is 0, we just go to the next bit, and in the meanwhile try to merge the boxes with corresponding size (2^i) to "create" boxes with a higher power of 2. If current bit is 1, we use the box of size 2^i, if possible. If it is not possible, we take the "nearest" box with bigger size and divide it until we get a box of the right size.

  • »
    »
    5 лет назад, # ^ |
    Rev. 4   Проголосовать: нравится +7 Проголосовать: не нравится

    You just need to construct all of the bits of number 'n' . Start from constructing lowest bit .for constructing ith bit first check if it can be constructed by numbers smaller than or equal to 2^i . Else you need to divide some number 2^j , j>i and j should be closest to i , see if this is possible .if no for some bit then -1 else answer is sum of number of divisions .

    of course above is just rough idea but you can go through the submission and ask if you have some doubt .

    submission 70903270

»
5 лет назад, # |
Rev. 2   Проголосовать: нравится +4 Проголосовать: не нравится

What's pretest 2 of prob/C

»
5 лет назад, # |
  Проголосовать: нравится +18 Проголосовать: не нравится

The memory limit on problem F is unnecessarily tight. There's no reason to MLE a solution that uses $$$\mathcal{O}(nmc)$$$ memory.

  • »
    »
    5 лет назад, # ^ |
      Проголосовать: нравится +3 Проголосовать: не нравится

    Unfortunately, we had to put tight memory limits to disallow solutions with dynamic connectivity offline approach.

    By the way, which approach uses $$$O(nmc)$$$ memory and cannot be modified to use $$$O(nm)$$$ memory?

    • »
      »
      »
      5 лет назад, # ^ |
      Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

      It is possible to optimize the memory, but depending on the implementation it can be quite tricky. Currently I'm repeatedly running into either MLE from initializing too many hash tables or TLE from using map.

      I'm surprised offline dynamic connectivity is a concern. Shouldn't that just TLE with 2e6 since it's a $$$\log^2$$$ algorithm?

    • »
      »
      »
      5 лет назад, # ^ |
        Проголосовать: нравится +16 Проголосовать: не нравится

      Why did you want to disallow dynamic connectivity? It's harder to implement than the solution that uses the constraints on $$$c_i$$$ and it's nicer imo.

      I tried implementing dynamic connectivity during the contest and indeed it got MLE. I'm not sure if it would have passed time limit since it was really close tho.

»
5 лет назад, # |
  Проголосовать: нравится +5 Проголосовать: не нравится

Can Anyone Please Tell me what the mistake in my ....code... of problem D..

»
5 лет назад, # |
  Проголосовать: нравится +8 Проголосовать: не нравится

How to solve problem E?

»
5 лет назад, # |
  Проголосовать: нравится -11 Проголосовать: не нравится

Edu Round 81: copy ApIO 16
Edu Round 82: copy ApIO 17
Lets revise ApIO 18 for Edu Round 83.

»
5 лет назад, # |
Rev. 3   Проголосовать: нравится +27 Проголосовать: не нравится

How to solve G? I tried something like centroid decomposition + convex hull trick, but I guess it's too slow.

  • »
    »
    5 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    not slow

  • »
    »
    5 лет назад, # ^ |
      Проголосовать: нравится +16 Проголосовать: не нравится

    It's centroid decomposition with convex hull trick. As TL is 6 seconds, it should pass.

  • »
    »
    5 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

    I tried too, but I had an error in my code during contest that I couldn't fix in time. However, after fixing it it gave me WA, i think I'm bad implementing the dynamic convex hull trick.

»
5 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

What is the dp state of problem E?

  • »
    »
    5 лет назад, # ^ |
      Проголосовать: нравится +15 Проголосовать: не нравится

    For each possible split t1 + t2 of the string t, dp[i][j] = "minimum prefix of s such that it contains non-intersecting i-th prefix of t1 and j-th prefix of t2"

  • »
    »
    5 лет назад, # ^ |
      Проголосовать: нравится +6 Проголосовать: не нравится

    First try every split of the string t and then dp[Position of current symbol in the string s][length of the first subsequence] — maximum number of symbols in the second subsequence.

  • »
    »
    5 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    (Mine is kind of weird, maybe there is a better one)

    Assume the first subsequence is of fixed length N. Then dp[i][j] = after taking the first j characters of string s, it is the largest length of second subsequence, given first subsequence has length i. If dp[|s|][N]=|s|-N, then we output YES. Now repeat for all possible N. If no such answer is found, output NO.

    Submission: https://codeforces.me/contest/1303/submission/70902911

»
5 лет назад, # |
  Проголосовать: нравится +13 Проголосовать: не нравится

F is so cool, thanks!)

»
5 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Can anyone explain what was wrong in my code? At my Codeblocks give my code correct output. But after submitted it gets WA. Why? I got 6 times WA on the contest, also 14 minutes have lost :(.

https://codeforces.me/contest/1303/submission/70855140 https://codeforces.me/contest/1303/submission/70857302 https://codeforces.me/contest/1303/submission/70858601 https://codeforces.me/contest/1303/submission/70859156 https://codeforces.me/contest/1303/submission/70860530

»
5 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Can anyone tell me error in my soln of B. 70896681

  • »
    »
    5 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится
            if(g>=b)
                cout<<n<<"\n";
    

    i cant understands this, you can see my code

  • »
    »
    5 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится
    else if((temp%g)!=0)
    {  
                    cout<<(tp*b)+temp<<"\n";
    }
    

    You need to check if the answer is no less than n, as in the following "else" statements. (Input: 10 3 4, Output 9, Answer 10)

»
5 лет назад, # |
  Проголосовать: нравится +25 Проголосовать: не нравится

Finally!!! i AC 4 problems on Div2!!! (LOL it's 1:00AM here, im going to sleep...

  • »
    »
    5 лет назад, # ^ |
      Проголосовать: нравится +6 Проголосовать: не нравится

    Imagine waking up and half of them had been hacked, just kidding :P
    Good night.

»
5 лет назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

my submission for c

please help why this is not working

conditions checked

if size =1 ans is abcd.....

if anyone has more than 2 neighbours answer doesn't exist

if there is no element with 1 neighbours then also answer doesn't exist

please help

»
5 лет назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

Hack my D solution. 70893301 Please!!!

»
5 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

WA on pretest 5 for B

»
5 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

can someone find a bug in my code for C 70902882 what im trying to do is create a graph of the given password where to nodes are connected if they are adjacent in the password. then i search for a position to start from(a node that has only one edge going out of it) and do a dfs from there to find if there are loops in the graph. If there aren't I have a found a possible keyboard, if there are their are no possible keyboards

  • »
    »
    5 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    if(a.size()!=2){cout<<"NO\n";continue;} But it can be string like this "abcbdbeba", in set a will be 'a','c','d','e'

  • »
    »
    5 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    ignore previous post, sorry if(a.size()!=2){cout<<"NO\n";continue;} if your input just one char like "e" so size of set a will be zero, but you output NO.

  • »
    »
    5 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    size of of vector a can be 4 if there are two connected component in graph with more than 1 vertices. it can be any even number.

»
5 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Can anyone explain how to approach problem C?

  • »
    »
    5 лет назад, # ^ |
      Проголосовать: нравится +4 Проголосовать: не нравится

    Represent the keyboard as a graph: letters are vertices and edge between vertices 'a' and 'b' means that 'a' and 'b' should stand next to each other in the keyboard. You can create this graph simply by iterating through the input string and adding an edge between each pair of adjacent letters.

    The trick here is that the keyboard can satisfy the conditions iff it is a linear graph (maybe with some vertices with degree 0). The only thing you have to do is to check if the graph you have built is linear. The simplest way to do so is to make sure that, if all isolated vertices are removed, it is either empty or contains exactly two vertices with degree 1 (these will be the first and the last letters of the keyboard), and the rest of the vertices have degree two. If the graph is indeed such, you can output the keyboard by doing a dfs from one of the ends of this graph and then append all isolated vertices in the end.

    • »
      »
      »
      5 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      You could also print the BFS tour instead of using DFS, I think it's an easier solution, though I also did yours.

      • »
        »
        »
        »
        5 лет назад, # ^ |
          Проголосовать: нравится +1 Проголосовать: не нравится

        Well, it does not matter as there is only one next generation vertex every time. In fact, I just did it manually in this case :)

    • »
      »
      »
      5 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      What do you mean by "remove all isolated vertices?" Thanks

»
5 лет назад, # |
  Проголосовать: нравится +4 Проголосовать: не нравится

I have a $$$O(\frac{448}{bitset}\sum n^3)$$$ way to solve E. First if we split $$$t$$$ into to parts, there is an easy way (DP) to solve the problem in $$$O(n^3)$$$ for each test case with a fixed midlle position $$$k$$$ in $$$t$$$. As there are $$$O(n)$$$ middle positoins, the approach above is $$$O(n^4)$$$.

To optimise, let std::bitset<448> be the type of $$$dp[i][j]$$$. If $$$dp[i][j][k]=1$$$, then it means that it is possible to get two subsequences from $$$s$$$ where $$$s_1=t[0-i]$$$ and $$$s_2=t[k-j]$$$. We iterate all characters in string $$$s$$$. If $$$s_i=t_i$$$, then we can update $$$dp[i+1][j]$$$ by $$$dp[i][j]$$$. If $$$s_j=t_j$$$, then we can update $$$dp[i][j+1]$$$ by $$$dp[i][j]$$$. To check the answer, just check if there exist a $$$i$$$ such that $$$dp[i][n][i]=1$$$.

code here

»
5 лет назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

I don't understand the calculation for the 3rd example in problem B test case 1. Each cycle of weather takes 1000001 days, of which 1 day is good. As such one can repair 2 units on each cycle. The last two units can be repaired in 2 days, since we don't have to wait for the last cycle of weather to finish. This gives: 1000001 * ((1000000-2)/2) + 2 = 1000001 * 499999 + 2 = 499999499999 + 2 = 499999500001

The answer given in the problem statement is 499999500000 which is 1 less. How can one save a day without ending up with more bad pavement than good pavement?

  • »
    »
    5 лет назад, # ^ |
      Проголосовать: нравится +19 Проголосовать: не нравится

    You can have more bad pavements than good pavements during the days, it's only at the end that you can't.

    • »
      »
      »
      5 лет назад, # ^ |
        Проголосовать: нравится +8 Проголосовать: не нравится

      In other words, one can lay an extra section of bad pavement in some earlier cycle, so avoiding having to lay it at the end. That makes sense, thanks.

  • »
    »
    5 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

    it takes 500000 good days and 499999 period of bad days 1*500000 + 499999*1000000=499999500000

»
5 лет назад, # |
  Проголосовать: нравится +67 Проголосовать: не нравится
»
5 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

What is the binary search approach of problem B?

»
5 лет назад, # |
  Проголосовать: нравится -45 Проголосовать: не нравится

Previous contests of codeforces used to be much better. But these days contests have just become a waste of time. Most of the people are unable to reach the questions which are really interesting and actually need to be solved.Easy dp and graph problems need to be included in the contests.

»
5 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Can anyone please tell me the mistake in my solution for D? 70923522

»
5 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Please help me on problem C, I don't know why my code runs into error in the test 2 ,I think the logic of the code is right. I use a pointer to record the position, and put ajacent keys into an array called res. Then I print the res and the other keys. Can anyone help me figure out the reason? Thank you very much! https://codeforces.me/contest/1303/submission/70923842

»
5 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

I am unable to understand the solution to problem D, can someone point me to some article(tutorial/video) where i can understand how this bit wise solution solves?. Thanks a lot in advance.

  • »
    »
    5 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Let $$$C[2^k]$$$ be the number of boxes with a size $$$2^k$$$. Let $$$Small[2^k]$$$ be the sum of box sizes smaller than or same to $$$2^k$$$ (i.e., $$$\sum_{i=1}^k 2^i \cdot C[2^i]$$$.) Iterate $$$i = 1$$$ to $$$maxbit$$$ of long long signed integer. If the $$$i$$$th bit of $$$N$$$(the bag size) is $$$1$$$, then we have to fill bags with boxes using their sizes are smaller than or same to $$$2^i$$$. It is possible when $$$Small[i] \geq 2^i$$$. But if not(i.e., $$$Small[i] < 2^i$$$), we have to divide a bigger box into the size $$$2^i$$$. Dividing procedure is quite implementive. I hope my submission would be helpful. 70933987

»
5 лет назад, # |
  Проголосовать: нравится +24 Проголосовать: не нравится

Problem G is exactly the same as a problem I set months ago,TSUM2Is it a coincidence?

»
5 лет назад, # |
  Проголосовать: нравится +11 Проголосовать: не нравится

The fastest system test ever

»
5 лет назад, # |
  Проголосовать: нравится +14 Проголосовать: не нравится

So is there a tutorial?

»
5 лет назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

So...is there a tutorial?

My friends told me how to solve F and G but I can't understand them :C,I think I need the tutorial to help me :C

»
5 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Can someone please explain to me why my code runs differently on codeforces from all other ides that I've tried. My code fails the first test case but if you run the code on any ide,It gives the correct output. Here's the link:https://codeforces.me/contest/1303/submission/70891793

  • »
    »
    5 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    It gets wrong answer on my computer, too. :(

  • »
    »
    5 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    The problem said that you shouldn't minus one on d.size(), the data type of d.size() is unsigned integer, which means you can't get a negative number by doing any calculation. You'd better put it as pt+1 == d.size(), which is equal to your original expression.

»
5 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Attention!

Your solution 70857539 for the problem 1303A significantly coincides with solutions hinatahentai69/70857303, 1412neerujjain/70857539. Such a coincidence is a clear rules violation. Note that unintentional leakage is also a violation. For example, do not use ideone.com with the default settings (public access to your code). If you have conclusive evidence that a coincidence has occurred due to the use of a common source published before the competition, write a comment to post about the round with all the details. More information can be found at http://codeforces.me/blog/entry/8790. Such violation of the rules may be the reason for blocking your account or other penalties. In case of repeated violations, your account may be blocked.

I received this message 3hr ago. I want to apologize about the submission as both of them were mine. I used 2 accounts to submit it. I wasn't aware of the consequences it could hold. I am really very sorry about the wrong doing and wont repeat the same thing again. Please don't block my account :(

  • »
    »
    5 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    If it's the first time you used two account to check your answer, I think it won't get your account banned . As it says in statement, 'In case of repeated violations, your account may be blocked.'.

    However, you should trust the cheat detection system and don't do that again.

»
5 лет назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

Give us the tutorial, plz!

»
5 лет назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

waiting for the tutorial

»
5 лет назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

Please Release the editorial.

»
5 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Auto comment: topic has been updated by awoo (previous revision, new revision, compare).

»
5 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Auto comment: topic has been updated by awoo (previous revision, new revision, compare).