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

Автор PikMike, история, 2 месяца назад, По-русски,

Привет, Codeforces!

12 октября в 17:05 по Москве начнётся Educational Codeforces Round 30.

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

Раунд будет нерейтинговый. Соревнование будет проводиться по немного расширенным правилам ACM ICPC. После окончания раунда будет период времени длительностью в один день, в течение которого вы можете попробовать взломать абсолютно любое решение (в том числе свое). Причем исходный код будет предоставлен не только для чтения, но и для копирования.

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

Задачи вместе со мной придумывали и готовили Иван BledDest Андросов, Владимир 0n25 Петров и Михаил MikeMirzayanov Мирзаянов.

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

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

Rank Competitor Problems Solved Penalty
1 irkstepanov 6 141
2 SPFA_THE_BEST_ALGORITHM 6 169
3 KrK 6 199
4 chemthan 6 200
5 Shik 6 214

Поздравляем лучших взломщиков:

Rank Competitor Hack Count
1 jhonber 75:-6
2 halyavin 31:-8
3 Zaher 6:-2
4 Khaled_Mohamed 4:-1
5 silicon_lover 2

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

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

Problem Competitor Penalty
A I_love_Maria_Ivanova 0:01
B gritukan 0:04
C eddy1021 0:08
D unused 0:14
E irkstepanov 0:44
F xjlinyueru 0:23

UPD: Разбор доступен по ссылке

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

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

Why isn't it on the main page?

UPD: Now it is on the main page.

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

Don't HACK ME, uwi!

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

Why there are so many people talk about uwi[user:uwi] when an educational round begin? I DONT think you will get an ACCEPTED just because of no hacks from others.Is it a joke?

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

Great!

»
2 месяца назад, # |
  Проголосовать: нравится -14 Проголосовать: не нравится

Is all educational round is unrated??

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

    Yes, the goal of Educational round is rather to practice than to compete

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

    The round will be unrated for all users and will be held on extented ACM ICPC rules.

    All Educational Round held on ACM ICPC rules.

    UPD:Educatonal Round for educating your mind. F**c logic!

»
2 месяца назад, # |
  Проголосовать: нравится -34 Проголосовать: не нравится

what is the subject of this round?graph?greedy???what?

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

what the C question Saying?? i don't get it....!!

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

    "that is, if the current column is j, then he will find minimum i such that ai, j = 1"

    see if we take the current value of i and calculate the score for current j it may happen that we can do better if we escape this 'i' and move to another 'i' and start at this (suppose that at some position we have continuous 1's and so, that position will be better for our answer).

    so, to move at that position we have to escape some i's which have 1 (i.e. we need to invert them).

    Now, it may happen that various i's may give same contribution to our answer and fro all those we have to choose that i for which we can minimize inversion ! Clearly greedy solution works here!

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

    It can be solved using precount for each column and greedy algorithm. The main difficulty in this task is to carefully check when you meet 1. You can see my solution for reference.

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

does anybody know how does the 5th test look like at problem E? L.E:i thought that is 2 have the same score,they should recive the same grade,but i was wrong

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

My best round ever! Shame that it was educational and unrated(( (also toughest b ever)

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

Why my idea is wrong on test 24?

my wrong code is here

The idea is using binary search to get the answer

  • »
    »
    2 месяца назад, # ^ |
      Проголосовать: нравится -10 Проголосовать: не нравится

    you don't need binary search dude

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

    You can't use binary search for this problem because the objective function (the length of the substring in your case) is not monotonic. Consider the example: 00111100. You can make balanced strings of lengths 2, 4, 8 but not 6.

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

      so are data weak?

    • »
      »
      »
      2 месяца назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      // 1 2 3 4 5 6 7 8  // id
      // 0 0 1 1 1 1 0 0  // string s from you
      // 1 2 2 2 2 2 3 4  // the sum of zeros from substring( 1 , i );
      // 0 0 1 2 3 4 4 4  // the sum of ones from substring( 1 , i );
      
      int left=0,right=n/2;
      
      while(left<right)
      {
           mid = (l+r)>>1;
           if(this length of substring can be found in string s )
                left = mid+1;
      }
      
      

      so I just find out the answer "4" that is right I think.

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

    I also had wrong answer in test 24. I realized this after the contest finished :/. you can't do binary search. try this case 10 1110000011

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

will there be any editorial?

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

How to solve B ?

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

I couldn't AC my O(n*sqrt(n)) approach for problem F.
Test cases were very strong!

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

How to solve D ??

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

    If k is even, then no solution because you always make 1 (main call)  + 2·m calls where m is the number of times you pass from condition 1. If k is odd, then there exists a solution if k is less than the maximum number of calls.

    You can solve the problem recursively by calling a function that takes the current subarray endpoints and k and the integer to starting filling the array with in this subarray (if the integer is x and the subarray size is L, then you will fill it with the integers x, x + 1, ..., x + L - 1. These integers are the subarray values. The main call will be f(0, n, k, 1).

    If k = 0, then put all the numbers sorted in the subarray so you do not make any mergeSort() call. Otherwise, split the subarray according to the rules. The left part will take the largest subarray values and the right part will take the smallest values. In this case, we guarantee that we will make 2 mergeSort() calls. Then you call f() for the left part giving it k - 2 to be maximum number of mergeSort() calls it can use and it will return the remainder of k - 2 (the unused calls). Then you call f() for the right part giving it this remainder. Finally, you return what the right part returns back. For a solution to exist, the returned value of the main call must be equal to 0

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

How to solve F?

  • »
    »
    2 месяца назад, # ^ |
    Rev. 3   Проголосовать: нравится +6 Проголосовать: не нравится

    Let's reverse string and build suffix array. Since we have sorted suffixes, string 'a' will be a LCP of some consecutive suffixes in suffix array, next we should get LCP array (lcp[i] = lcp of suffix[i] and suffix[i + 1] when i and i + 1 indexes in sorted order). If we represent LCP array as columns along axis, our task transformed to 'find rectangle with maximum area', and it can be solved with two stacks: for each lcp[i] find nearest left and right index j, that lcp[j] < lcp[i], after that we should relax the answer with lcp[i] * (rightJ — leftJ), because there are (rightJ — leftJ) strings, that have lcp[i]. So the last question is how to handle forbidden cells? we should merge all lcp (in lcp array) into one between each two consecutive non-forbidden cells.

    PS. If you not familiar with suffix structures, I hope it can be solved with the same aproach with replacing suffix array by hashing+binary search for sorting suffixes.

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

Can Someone Explain me how rajat1603 solved B ?

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

    logic is same as my sol just implemented in easier way....

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

    You just need prefix sum to solve this question and realize the following : initially sum = 0

    add 1 to sum if you encounter a '1' subtract 1 from sum if you encounter a '0'

    Suppose you are at current index 'i' and your Current sum is S. You are encountering this sum S for the first time. you map i to S. i.e, map[S] = i... Now suppose for some later index J you encounter S you just update ans as max(ans, j — map[S]) because if you observe carefully you need the best possible sum to be 0.

    if you have current sum as 0 at index 'i' then you keep updating the answer with 'i' + 1

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

Where are editorials?

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

Could you please look into unknown verdicts for hacks 360797 and 360798?

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

How to solve E?

I tried with a DP approach but it didn't work.

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

    Good day to you,

    Well hope it won't be wrong, since it is not "proved yet" :)

    Firstly, sort all "heights" (yet still remember their original position to be able to reconstruct at the end). Now, it is pretty easy to assign a value to each position (it is the height on the position minus the height on previous position [potentionaly 0]).

    So not lets consider how would "brute-force" solution work? Well kinda simple.. just try EVERY triple in the array (check whether the x*2>=y is fine) and then take MAXIMUM from these (what is maximum is written in the "rules" — note tht the rightmost is always best diploma :) ). Now as you can see, it will obviously TLE, anyway as you can also see, it is just O(N3) which is not bad.

    So now we can "simply" focus on reducing of the third cycle. As the other two iterations are fixed, we know pretty well, where the segment (if any) for the third cycle might be. EXAMPLE: N==10, i=7,j=9, we know the length of first segment is 2 and of second is 1, so the length of third segment must be between 1 and 2 (which begins on position 5 or 6). We are interested in the biggest number there so we can use some "RMQ" structure, which could get it. One way is for-example Sparse Table which can get maximum in O(1) making the total complexity O(N2).

    So in short: Iterate with two (the best) diplomas and find the third by RMQ.

    Good Luck And have Georgeous Day ^_^

    Hope it was a little bit undestandable and hope I didn't lead you wrong way ^_^

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

      "it will obviously TLE" — not so obviously, I got AC with brute force only suitable indices in third cycle (Code) And this solution can be optimized more if brute force only suitable indices in second cycle also.

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

        Good day to you ^-^

        Well seems you are right (yet I would still be a little bit afraid). Seems taking only "interesting" seps makes it "766 149 050", which might be suitable (not sure what (whether) are your other optimalisations)

        So well thank you, seems it is a little bit easier approach ^_^

        GL & Have Nice Day

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

Can someone explain to me how does hacking work?

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

can anyone please explain how to solve E?

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

When will the editorial be published?

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

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