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

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

Привет!

Окончательно освободившись от большей части летних забот, я снова могу приступить к подготовке Div. 3 раундов! Я решил добавить в этот блог что-то от себя, потому что TryToKnowMe (и, думаю, многие другие) заметили, что я правда копирую эту запись от раунда к раунду, меняя лишь название соревнования и дату проведения. Но кто знает, может, экономя время на написании анонса, я успеваю лучше подготовить задачи к раунду?... Пусть это останется тайной. А теперь приступим.

В 16.07.2018 17:35 (Московское время) начнётся Codeforces Round 498 (Div. 3) — очередной Codeforces раунд для третьего дивизиона. В этом раунде будет 6 задач, которые подобраны по сложности так, чтобы составить интересное соревнование для участников с рейтингами до 1600. Наверное, участникам из первого дивизиона они будут совсем не интересны, а для 1600-1899 покажутся простыми. Однако все желающие, чей рейтинг 1600 и выше могут зарегистрироваться на раунд вне конкурса.

Раунд пройдет по правилам образовательных раундов. Таким образом, во время раунда задачи будут тестироваться на предварительных тестах, а после раунда будет 12-ти часовая фаза открытых взломов. Я постарался сделать приличные тесты — так же как и вы буду расстроен, если у многих попадают решения после окончания контеста.

Вам будет предложено 6 задач и 2 часа на их решение.

Штраф за неверную попытку в этом раунде (и последующих Div. 3 раундах) будет равняться 10 минутам.

Напоминаем, что в таблицу официальных результатов попадут только достоверные участники третьего дивизиона. Как написано по ссылке — это вынужденная мера для борьбы с неспортивным поведением. Для квалификации в качестве достоверного участника третьего дивизиона надо:

  • принять участие не менее чем в двух рейтинговых раундах (и решить в каждом из них хотя бы одну задачу),
  • не иметь в рейтинге точку 1900 или выше.

Независимо от того являетесь вы достоверными участниками третьего дивизиона или нет, если ваш рейтинг менее 1600, то раунд для вас будет рейтинговым.

Спасибо MikeMirzayanov за платформы, помощь с идеями для задач и координацию моей работы. Спасибо моим очень хорошим друзьям Михаилу awoo Пикляеву, Максиму Neon Мещерякову и Ивану BledDest Андросову за помощь в подготовке и тестирование раунда.

Удачи!

UPD: Также большое спасибо тестерам uwi, mareksom и ivan100sic за неоценимую помощь в подготовке раунда!

UPD2: Таблица результатов!

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

Rank Competitor Problems Solved Penalty
1 wendy_virgo 6 236
2 TwentyOneHundredOrBust 6 237
3 zwgtxdy 6 265
4 Syvail 6 273
5 khadgar1998 6 279

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

Rank Competitor Hack Count
1 jhonber 131:-7
2 antguz 9
3 pye 9:-3
4 djm03178 6:-1
5 imlk 4

Всего было сделано 199 успешных взломов и 232 неудачных взлома!

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

Problem Competitor Penalty
A eggmath 0:01
B eggmath 0:06
C vangtrangtan 0:07
D MoreThanANoob 0:23
E Student_of_Husayn 0:07
F NoTrolleNoLife 0:18

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

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

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

hope halyavin the system tester also provides his service this time!!!

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

    I really want to know how does he do that so FAST!

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

      He uses some script.

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

      He should really do a screencast when he is hacking. I mean I don't get a test case for hacking until I have already given a solution which is accepted for the pretests and I have found a test case which is already in the problem statement and not matching my code

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

        The script is used only for testing the test case he feeds into the script on different submissions. The test cases are not generated by the script. He himself thinks of the test cases and then feeds into the script.

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

minimize hacking phase to 6 hours at least try it once if everyone agrees implement it permanently.

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

So it is unrated for 1600-1899?

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

let's hope strong pretests and fast responding server side...

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

Next contest starts after 10 days. MikeMirzayanov are you going somewhere?

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

Good luck everyone <3

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

Expecting more and more mathematical problems.

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

vovuh i think you have to add this

penalte is 10 minutes so people who ask for it get downVote haha

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

I always feel comfortable to solve div 3 problems.

So I love it very much.

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

I always feel comfortable with div 3 problems. So I love it very much.

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

Sad that I may have to miss the round for my final year project work :(

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

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

Just mark the changes

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

For a long time, I am still in Cyan. :) Div 3, the road to changing color.

Many thanks about Div 3 idea.

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

Don't worry buddy, we know you didn't copy pasted. Who need that when you have scripts lol

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

Why topcoders hide their faces behind anime profile pics?

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

Hope that this will be my last div3 contest from next time I can participate out of contest.

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

Strong pretest :)

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

    Have you read this?

    You may edit your comment only for fixing grammar mistakes or small changes. Do not change the main idea of your comment. All previous revisions are available for others. Are you sure you want to edit comment?

    Main idea of Hope that this will be my last div3 contest from next time I can participate out of competition in div3. Never had that feeling :( and Strong pretest :) is not the same.

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

Upvote for ivan100sic and good luck!

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

Probably, participants from the first division will not be at all interested by this problems.

I am always interested in Div.3 problem sets. :D

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

Easy offline solution for E using cartesian tree (treap). 40444978

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

How to go faster than O(n2 * k) in B?

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

    Use k largest values for maximums of these segments, and then extend them.

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

    sort the values in reverse and find the index of top k values. then one loop would give you the size of each segment

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

      Can you explain more on how to get size of each segment?

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

        suppose I have [101,3,5,6,10,100]. So, I take a temp array and sort this in desc order. The temp[] = [101,100,10,6,5,3]. Now suppose we want to get the top 3, get the index of 101, 100 and 10 from original array and save it somewhere. idx[] = [0,4,5] (0 based indexing) . The size is 1, 4 and 1. You need to take care of duplicates. For that once you visit save the index and remove the element from original. I am very bad in explaining stuff. Submission: 40426181 .Please let me know if something is not clear. will try to explain more clearly.

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

    answer would be sum of k- maximum elements in array and keep these k maximum elements in a multiset then just traverse form 1 to n and if a[i] is element in multiset remove it and print number of elements from previous partition.

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

Can anybody explain problems D and F please?

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

    For D you just can see that changes makes cycles i -> n — i + 1. For every cycle find min changes.

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

    The key observation to solve problem D is that each letter in string A has 3 counterparts (except when n is odd and you consider the middle letter). These counterparts are the letter at the opposite position in string A, the same position in string B, and the opposite position in string B. You can think of these 4 letters as a group. Each group, after preprocessing modifications, must contain two pairs of letters. Once this observation is made, a bit of case-bashing can determine the number of modifications necessary.

    My solution for problem F was meet-in-the-middle. If you start from the bottom right corner, you can determine the possible values for any grid square which can result in a final XOR-value of k. I calculated these values along with the number of paths which resulted in these values up to the 'middle' of the grid (where Manhattan distance to either corner was equal to (n+m)/2-1). Then, the process was repeated starting from the upper left of the grid.

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

how to solve F?

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

    hmm

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

    Notice that 20C10 is only < 200k, so we can use meet in the middle to get the answer -> DFS all possible routes from (1,1) until middle of grid and insert it into map, then DFS from (n,m) until middle of grid

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

      What about paths that don't go through the middle of the grid? I assume that middle is point (n/2, m/2).

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

        Middle of the grid can simply mean a certain Manhattan distance from the upper left of the grid (i.e. y+x==(N+M-2)/2), indexing at 0).

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

          Great solution! What will be the time complexity in this case? Thanks in advance!

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

            should be 2^20 * 20, i believe

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

              Since we are traversing just half the graph, once from (1,1) and once from (n,m), cant we just say it will be 2*(2^10)*(2^10) = 2^21?

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

                no, you don't multiply both halves when you traverse the graph. But each half individually is 2^20 ways, because 20 is only the halfway distance, and you have to choose either to go right or down. Last 20 is for the log factor in the maps.

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

                  Oh ok. Might sound noob but since one half takes 2^20 moves, and we traverse half the graph twice, shouldn't the complexity then become 2*2^20 = 2^21? And if we use unordered map which is essentially a hash table,can't we ignore the log factor coz of the maps?

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

                  unordered_map has test cases to counter against its usage, so I never use it anymore.

                  Yes, it will take 2^21, but the point is the complexity is n * 2^n still

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

                  Can you explain any case for breaking unordered map I couldn't find any for that.

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

                  Couldn't find the original. This is pretty solid proof though:

                  https://codeforces.com/blog/entry/21853?#comment-322392

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

      Can you please suggest any good resources/problems with editorials for bidirectional DFS/ meet in the middle? It is a new topic for me. Thanks!

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

    Bidirectional bfs

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

there is no hacking in Div3?

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

Great contest, Problem set was so balanced and covered all topics perfectly. Ideal contest for div 3 participants. Dude make one div 2 as well, I would really like to attempt it officially :P

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

YogayoG hacked all his solutions!!

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

Realized the importance of time today !! :( But it was a great round.

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

why in Problem D my code get WA on test 3 -_-

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

my code is giving correct output for problem E in Sublime editor but wrong answer on the codeforces editor.How it is?

include<bits/stdc++.h>

using namespace std;
#define ll long long
vector<ll>v[200010];
vector<ll>vis(200010,0);
map<ll,ll>mp,mm;
vector<ll>gr;

ll dfs(ll s)
{
    mp[s]=gr.size();
    gr.push_back(s);

    vis[s]=1;
    ll a=0;
    for(auto aa:v[s])
    {
       if(!vis[aa])
       {   
         a+=dfs(aa);
       }
    }
    mm[s]=a+1;

}

int main()
{
    ll i=0,j=0,k=0,l=0,m,n,s=0,x=0,y=0,d;
    cin>>n>>m;

    for(i=2;i<=n;i++)
    {
       cin>>x;
       v[x].push_back(i);

    }
   dfs(1);

   // for(auto aa:gr)
   //   cout<<aa<<" ";

   for(i=0;i<m;i++)
   {
      cin>>x>>y;
      j=mp[x];

      if(j+y-1<=mm[x])
        cout<<gr[j+y-1]<<"\n";
      else
        cout<<"-1\n";
   }





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

Found some serious cheating going on here-

deact Copied F from Roundgod --

40438080 Copied from — 40428801

Sad thing is that in order to hide it, five minutes later, this guy submits another code, with all the headers removed thinking he will not get caught.

Here is the second submission — 40438951

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

    What?How?I'm pretty sure that I didn't give my code to anybody...

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

    Finally found out what happened here... It turned out that I uploaded my code to my github after solving F... Have just made the repository private. My apologies.

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

      XD The guy wa 31 use the same idea and change your code a little bit But he got a wa So he submit your code directly to make sure that your code is right

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

      a master mistake costs 1000x times newbie mistake ..

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

      So he basically had your github repo open on one tab.google doesn't index so fast.

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

    This can done easily with the help of Second id first he solves a problem and then he lock its problem and then see the code of any other guy and then he submits it with a different id.

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

      In div 3, he can't do that because it doesn't have "hack" and "lock", everyone can't see other's code until the contest ends.

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

" halve the grid diagonally not vertically nor horizontally you idiot! "

thats what test 22 on problem F would have said to me if it could speak.

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

    I went DP but full brute on bitmasks and got MLE at test 47. Hmm how come I passed that?

    My failed submission.

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

      the memory is 20*20*AllPossible xors

      All possible different numbers from taking the xor is a big number, thats why you Got memory limit exceeded

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

        Yeah, I meant, even bruting like that, how would I passed test 22 and dozens of tests following until that, while yours stucked at it? Just curious.

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

          Check the first tests they are meant for TLE detection.

          numbers are small thus their xor is also small and dp on these constrains work but when numbers are big dp will get you TLE or MLE whatever comes first.

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

    How is diagonal better than vertical/horizontal ?

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

      If you go full brute, the maximum amount of bitmasks you have to handle is nCr(38, 19).

      Cutting vertical/horizontal decreases half the steps for one dimension, therefore the maximum bitmasks count lowers to about nCr(28, 9) or something similar — still insanely high and might not fit in TL/ML.

      Cutting diagonal decreases steps in both dimensions, therefore further lowering the bitmasks count, to about nCr(18, 9).

      (I'm not actually that certain in those combinatorics — those are estimated. Still you might get my points ;) ).

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

Hmm... is this normal??

image

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

    Check his solutions, he is using an if condition to hack it. for eg. In problem A, he used if(x==210400)return 0;

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

      Oops, that's bad, I see cheaters coming in waves :S

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

      How he knew that there was no value of (x==210400) ????

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

        Well, you can choose any random number and you'll have a very low probability of coincidence against pretests.

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

          and he succeed for all his 6 problems.

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

            Yes, for the same reason above. It's very feasible. You can calculate the probability for that to happen ;)

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

can someone help me to find the logical error for Problem D 40443887

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

    Fixed it: http://codeforces.com/contest/1006/submission/40452847

    The only change was: "if(ans[3]!=ans[2]) {...}" should be "if(ans[1]!=ans[2]) continue". ans[1] != ans[2] iff we have letters of type 'a a b b' and we shouldn't make changes in that case.

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

      but, in case of 'a a b b' , (ans[3]==ans[2]) ,so it wont increment the sum to sum+1.. So ,why is it getting wrong ljupche98

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

        You shouldn't check ans[2] and and[3] because they can be equal for case 'a b b b' (where the answer is 1) and 'a a b b' (where the answer is 0). What you should do, is check whether the groups have equal number of elements and that is, by checking ans[1] and ans[2].

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

Can anybody tell , why this 40450609 gives a runtime error on test case 2; Whereas it runs fine on removing the for loop for calculating subordinates O(n)

for(ll i=n-1;i>0;i--)
    {
        child[i+1]+=(child[i+1]==0);
        child[i]+=child[i+1];
    }

and calculating it when using dfs 40450928.

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

    In Example 1, your code has child [2] = 6, but this is obviously a mistake. In general, the value of child [i] is not determined by the value of child [i + 1].

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

      Thanks, for the help, That was a very stupid conclusion i made :(

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

When will the rating be updated ?

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

When will the ranting be updated?

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

Problem D :

7 abacaba bacabaa

  1. Replace a1 with b
  2. Swap a5 and b5
  3. Swap b3 and b5
  4. Replace a4 with a
  5. Replace a5 with c

Answer should be 3. Please correct if I'm wrong

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

another contest saying an array can be a birthday present, how boring you guys are!

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

Where's editorial ?

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

why sysem testing didn't start

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

I seemed to have used the right logic for B but my solution got hacked. It seems I didn't factor in some edge cases. Can someone help out?. My solution is here. Thanks in advance :)

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

    You should tell your logic too instead of expecting someone to figure it out and tell you whats wrong with your code.

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

      I am sorry. Will take care from next time. My logic was to find the k maximum elements of the array and then find those k elements in the array and mark them as -1. And then print the sum of those maximum k elements to get the first line of output. To get the second line of output I would count the number of elements till I encounter -1 and set counter as 0 again whenever I encounter -1. Further to take care of the test case of the encountering the last -1, I will simply add the rest of the elements left in the array to the counter. Hope that explains my approach :).

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

    you always ask very dumb questions

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

      I appreciate your criticism. Just that codeforces community has been the only bunch of people who seem to cater my dumb doubts. :)

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

    Your in-mind logic was correct, but you made a mistake in your invector function: after finding the desired element, you must terminate the function immediately (otherwise it will keep marking other elements with the same value).

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

      Thanks, I got it now. For multiple occurrences my code was simply making them -1 in all of the positions. :)

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

where is the rating changes??

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

vovuh it was a good round :)

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

Very late in rating update.

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

wow, You forget to make deact unrated... 40438080 is a directly copy from 40428801. Why this guy still rated? vovuh

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

    After searching through past blogs, it seems like cf admins don't care about cheating instances like these. http://codeforces.com/blog/entry/60377#comment-442301 and http://codeforces.com/blog/entry/60573 were pointed out but the cheaters have not been disqualified :(

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

      Cheating on your girlfriend is a far more egregious crime than cheating on Codeforces, because Codeforces will forgive you but your girlfriend will not.

      Therefore I propose that anyone who participates in Codeforces contests must have a girlfriend, so no cheating will occur. #ProblemSolved (This implies that eggmath will not be able to compete, SAD!)

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

        hmm

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

          My theory is that eggmath is actually a monkey who works at Facebook; hear me out.

          First, we see that YouTube's error message mentions "a group of highly trained monkeys" who are working to fix the error. YouTube's HQ is located in San Bruno, which is in Northern California. Guess what? eggmath lives in Northern California. This is the first clue that we are given.

          The other two clues are given in Facebook Hacker Cup. In the qualification round, Ethan is searching for a string. Do any animals actively search for strings? Yes. Cats and monkeys. Based off this knowledge, eggmath can be either a cat or a monkey.

          However, the next clue is pretty damning evidence: Ethan traverses a tree. Hear me out, I know cats can traverse trees too, but which other mammal traverses a tree better than a cat? That's right, a monkey. There is no other animal in the jungle that has such an agile and nimble body to traverse trees. If this evidence isn't clear enough, I don't know what is.

          Therefore, I believe that eggmath is indeed a monkey.

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

    Sorry, we will fix it soon. Thanks for the notification!

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

Maybe I have misunderstood something but...

It is told only the trusted participants of the third division will be included in the official standings table, but in результаты there are many untrusted participants. And trusted participants ratings are affected by them. For example I am on 169th place in COMMON STANDINGS, but in RATING CHANGES and MY RATING HISTORY I am on 220th place, so my rating has been changed as I am on 220th place, vovuh, MikeMirzayanov.

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

    In COMMON STANDINGS untrusted participants show up and then again disappear all the time.

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

    Sorry, it was my bug in the standings parser, the winners table may be wrong also in the some previous Div. 3 rounds. Now it is fixed (i hope) because i extracted the results manually.

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

      I am not so good in English Ой, извините, только что вспомнил.

      Кажется ничего не изменилось :( Видно проблема более глубокая и время MikeMirzayanov? Да ладно, не проблема. Спасибо, мне(и думаю почти всем) очень понравился ваш contest, а эту проблему можно решить, да?

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

    Also Mike knows about the bug with the standings table and it will be fixed soon i hope (really hope).

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

OMG, i was in the best hackers list. :))

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

How do you mathematically compute the number of possible paths for problem F? I see many different combinatoric formulae here, but none of them are explained.

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

    Misunderstood your question.

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

      The number of paths for corner to corner can be seen as a permutation with repetition with formula (m + n)!/(m!*n!).

      The number of paths from a corner to the diagonal is 2^20 at most. When n = m = 20 each path is 20 steps and each step either down or right.

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

can someone explain how to divide matrix in problem f clearly.. UPD:GOT IT..clear and short codes are sometimes helpful;

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

Первый раз такая проблема.. не знаю куда писать.. Что надо сделать? http://codeforces.com/contest/192/submission/40535392