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

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

UPD: Отдельное спасибо Михаилу PikMike Пикляеву за помощь с переводами и обсуждение задач, Максиму Ne0n25 Мещерякову за обсуждение задач, Артему Rox Плоткину, Дарье ZeroAmbition Степановой и Tommy STommydx Li за тестирование раунда!

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

<almost-copy-pasted-part>

Привет! В 01.10.2019 17:35 (Московское время) начнётся Codeforces Round #590 (Div. 3) — очередной Codeforces раунд для третьего дивизиона. В этом раунде будет 6 или 7 задач (или 8), которые подобраны по сложности так, чтобы составить интересное соревнование для участников с рейтингами до 1600. Однако все желающие, чей рейтинг 1600 и выше могут зарегистрироваться на раунд вне конкурса.

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

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

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

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

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

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

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

Удачи!

Также хочу сказать, что участники, намеренно отправляющие неверные решения и взламывающие их после окончания соревнования (пример), не будут показаны в таблице лидеров по взломам.

</almost-copy-pasted-part>

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

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

I can’t register for the contest unofficially. Is something wrong? Edit: Can now.

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

rtd?

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

Vovuh проводит отличные соревнования по div 3

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

what factor decides the number of problems ? Planetory motion?

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

    We increase the number of problems by adding some new problems or subtasks of existing problems to smooth some gaps in difficulty.

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

Don't give up, Learn from your mistake

I've made some mistake on Vovuh's previous contest Educational Codeforces Round 73 (Rated for Div. 2) and Codeforces Round #587 (Div. 3), It's my high time to apply what's I learn from that mistake.

Thanks Vovuh for giving us another chance to improve our skills (and rating ;-) )

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

This contets is 1234 contest in codeforces Good luck to everyone.
Codeforces Round #590 (Div. 3)
https://codeforces.com/contests/1234

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

    Thanks for the billion dollar information. You saved the world.

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

Will Vovuh surpass PikMike

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

    I don't think it becomes true someday :(

    Div.3 are much less useful for most participants so I gain less contribution than this tiny anime girl.

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

      Yes and Educational rounds are also as frequent as div3 rounds. But you are only 2 points behind him. Maybe it will happen some day.

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

      I think they're more useful. Div. 3 taught me a lot of standard tricks and quicker implementation back when I was a beginner. Educational rounds serve a similar purpose, but require a contestant to have a fair amount of familiarity with the aforementioned standard tricks. Since there are many more beginners in competitive programming, Div. 3 contests are far more valuable to introduce people to problem-solving.

      Keep up the good work, man!

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

      TRUE NOW!

      Congrats Vovuh

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

I really like your contests, hope it doesn't get like Codeforces Round #579 (Div. 3) that the judge was so slow. good luck in the future contests Vovuh :)

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

GOOD LUCK!

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

I_love_Vovuh

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

I will AK this contest !!! And I will AK IOI2020 in just 3min with Denverjin !!!

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

I know that it is out of topic, but will the Technocup Elimination Round 1 be rated?!

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

Hope to become blue after this round.

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

Can anyone please tell me which problem has two subtasks? @Vovuh

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

Hopefully problems won't be bad like last contest!

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

QueueForces?

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

What is the reason behind giving ~50 test flies for problem D?

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

Why always this problem -> Queue

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

More than 5 minutes testing queue :(

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

The queues are annoying.

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

this queue affected me really more than 15 minutes !

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

Look at rank 17 (Alex_____Wei) and rank 18 (AIex_Wei). Are they the same person?

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

Жду когда в А начнут пихать подзадачи

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

    Какая разница, какая из задач содержит в себе подзадачу, если это сглаживает переходы по сложности между ними?

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

      Мне кажется, что если нужно сгладить переход по сложности лучше вставить новую задачу, а не разбивать задачу на две: тупейшую реализацию и собственно задачу.

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

Is F a well-known problem?

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

72150714_3373957409311801_8642731821810843648_n.jpg

:(

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

I tried to solve D using fenwick tree but I failed coding it terribly anyone can tell what's wrong in my solution
link

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

    there are 26 lowercase characters I used bitwise OR segment tree then count the number of bits for the L,R range

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

    Your n is not initialized anywhere in the code.

    int BIT[100002][26], a[1000],t,n;string s;
    void update(int x, char ch)
    {
        int ind=int(ch-'a');
          for(; x <= 100001; x += x&-x)
            BIT[x][ind] ++;//,cout<<ind<<" "<<BIT[x][ind]<<" hh\n";
    }
    void delet(int x,char ch)
    {
          int ind=int(ch-'a');
          for(; x <= n; x += x&-x)
            BIT[x][ind] --;
    }
    
    • »
      »
      »
      2 месяца назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      in update I made the limit to 100001 and forgot to make it in delet but that's not the problem

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

        One more bug

             for(; x > 0; x -= x&-x);
                sum[i] += BIT[x][i];
        

        What's that semicolon doing at the end of for loop

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

          Also you need to re-initialize x again, you are depleting it for a itself

          void query(int x)
          {
          	
               for(int i=0;i<26;i++)sum[i]=0;
               for(int i=0;i<26;i++){
               for(; x > 0; x -= x&-x)
                  sum[i] += BIT[x][i];
           
          }
          

          Fix all these and try

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

    You can solve it easer. Just take a 26 sets of $$$i$$$th character positions ($$$i$$$th set contains positions of $$$i$$$th alphabet char in string). So, when you've got a update query, just delete $$$pos$$$ from $$$lastc$$$th set, and add $$$pos$$$ to $$$c$$$th set. When you've got a count request, for each of 26 charactes find any index in set, where $$$i\geq l$$$ and $$$i\leq r$$$, if it exists, just add one to answer.

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

    I tried to solved D by simply map and string. I thought it will got TLE but I got AC. Here is my code. Can anyone suggest what is complexity for my code?

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

      Its $$$O(Q*N)$$$

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

        So How do I got AC instead of TLE?

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

          Some optimizations in C++ language itself.

          From docs:

          Complexity of substr

          Unspecified, but generally linear in the length of the returned object.

          The unspecified part is interesting, will need to check the source of C++ to know more.

          Same for find.

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

          Pretest is a little bit weak. Some submissions in $$$ O(QN) $$$ can pass the pretest.

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

      i solved D by hashing and string, then i got TLE...after i changed string to char array i got AC

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

Sorry, but don't know the purpose of problem D unless there exist a solution without log(n) factor. C was far better than D. How to solve E?

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

    First of all,if we know p(k) we can answer pos(p(k),x[i]) instantly:

    1)x[i] == k- pos(p(k),x[i]) = 1

    2)x[i] < k — pos(p(k),x[i]) = x[i]+1

    3)x[i] > k — pos(p(k),x[i]) = x[i]

    its true,because p(k) means that in first position k,in 2nd-1,3rd-2,...,k- k-1,k+1 -k+1,...

    (k,1,2,3,...,k-1,k+1,...,n)

    so now we want to answer abs(pos(p(k),x[i])-pos(p(k),x[i+1])),there will be 8 possible cases,like: x[i] > k && x[i+1] < k

    ...

    the main thing what we just go through all the m-1 elements and say which k will increase

    like if x[i] < k && x[i+1] < k than we should increase every k bigger than max(x[i],x[i+1]) to abs(x[i]-x[i+1])

    and we can do it with prefix sums( to add x from l to r we pref[l]+=x and pref[r+1]-=x).

    So now answer for f(p(k)) will be sum from 1 to k,we just go from 1 to n and every time add pref[i]

    Hope it will help,sorry for my english Here is my submissoion 61661243

    P.S I just hope what i wont be hacked after this XD

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

      if u have spare time could u help me to debug my Ecode please? i got a TLE but i dont know how to change it.submission

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

        You get TLE,because its O(n*m) that can be very big(m <= 10^5 and n <= 10^5).

        I cant write anything more to you than i wrote above,your algorithm is just too slow

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

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

How to solve C?

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

    There is one way from $$$(1,1)$$$ to $$$(2,n)$$$ in any dataset, for which answer is "YES", only .

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

    I have used the simulation strategy to solve this problem:

    start from column 1 and row 1 :

    if(pipe of type 1 or 2): you have to just move to next column with the same row else if(pipe of type 3,4,5 or 6): ... check the other row with the same column should have pipes(3,4,5 or 6), if(check = true): just change the value of row i.e from row=1 to row 2 or from row=2 to row 1 else if(check = false): you should print no as final answer

    at last if row == 1: you should print 'NO' else The final result remains as it is what you get from the previous steps

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

    You can understand better with my code: q=int(input())

    for _ in range(q):

    n=int(input())
    
    s1=input() #column 1
    s2=input() #column 2
    
    r=1  #value of row
    ch=1 #variable to check the results during simulation
    
    
    for i in range(n):
    
        if(r==1):
            if(s1[i]=='1' or s1[i]=='2'):
                ch=ch
                r=1
            else:
                r=2
                if(s2[i]=='1' or s2[i]=='2'):
                    ch=0
    
        else:
            if(s2[i]=='1' or s2[i]=='2'):
                ch=ch
                r=2
            else:
                r=1
                if(s1[i]=='1' or s1[i]=='2'):
                    ch=0
    
    
    
    if(ch==0 or r==1):
        print("NO")
    else:
        print("YES")
    • »
      »
      »
      2 месяца назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      I used the same logic but there was a small mistake which I could fix only now :((

      while(q--){
              int n; cin >> n;
              int arr[2][200002];
      
              string s; cin >> s;
              for(int i = 0; i < n; ++i) arr[0][i] = (s[i]-'0');
              cin >> s;
              for(int i = 0; i < n; ++i) arr[1][i] = (s[i]-'0');
      
              int row = 0;// 0th row;
              bool done = false;
              for(int i = 0; i < n; ++i){
                      if((arr[row][i] == 3) || (arr[row][i] == 4) || (arr[row][i] == 5) || (arr[row][i] == 6) ){
                          if((arr[1-row][i] == 1) || (arr[1-row][i] == 2) ){
                              cout << "NO\n";
                              done = true;
                              break;
                          }
                          row = 1-row;
                      }
              }
      
              if(row == 1 && !done){
                  cout << "YES\n";
              }
              else if(row == 0 && !done){
                  cout << "NO\n";
              }
      
  • »
    »
    2 месяца назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    I solved C using recursion, but was able to submit after 20 min of contest(my bad was not able to figure out one error)

    Usually during contest, i coded with comments so i don't get lost for what i need to do.You can check my submission here: https://codeforces.com/contest/1234/submission/61665005

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

Can anybody tell me test case 4th in problem E?

EDIT Forgot to take long long :(

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

Why unordered_map fails for Problem B2? I got TLE using unordered_map, but I got AC using map.

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

    lol same wasted 2 hours over this. All solution on B2 should be rejudged everyone knows unordered_map is faster than map . It costed me almost 1000 rank due to this shitty issue.

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

      SAME HERE BROTHER

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

      Well ordered_map is always LogN Unordered_map isn't always O(1). It's usually O(k) where k is the size of buckets. Since in many cases k is small we take it as O(1). However when there is alot of collisions then it is O(n)

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

    me too.o(╥﹏╥)o .So I didn't solve B2 in the contest .And I want to know why the unordered_map is less efficient than map this time.

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

      unordered_map has a biiiig constant. sometimes, it doesn't works better, than map. And use there deque, not maps.

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

        I used map (to save # of displaying ids) AND deque (to save displaying ids and their order). Can we use deque instead of map?

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

    Even I wasted almost 30 min on this to recall that the worst case complexity of unordered map or hashmap is O(n) i.e. linear time...

    Kudos to B2 problem to refresh my basics. But unfortunately I'll be afraid of using it in future

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

      Can you tell me why unordered_map was going to the complexity of O(n) ? In a past contest I was getting TlE because I used map and got AC after changing it to unordered_map . Now I am just confused what to use because of this .

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

        It's linear because of collision. I suggest you to read about hashing and collision.

        And when you got AC earlier with unordered_map, it must be because the test cases were such that the collision was minimum

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

          I have no idea how you managed to get TLE just because of the unordered_set. For me it is faster than the set on the given test data...

          unordered_set:61684841

          set:61666722

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

      I used unordered set in D and got TLE. I'll also be afraid of using it in future :(

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

    unordered_map has worst case complexity of O(N^2). For map it's O(logN). read here — https://codeforces.com/blog/entry/62393

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

Hi all I tried to solve problem D using segment tree , but gets TLE at test 4. What's wrong with my submission ?

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

Can anyone please tell me the difference between these 2 codes for problem B2 — https://codeforces.com/contest/1234/submission/61663199 (AC code)

https://codeforces.com/contest/1234/submission/61657941 (TLE code)

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

    dont use unordered map without custom hash or else you'll get tle.

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

      Yes my mistake I should have read about custom hash earlier didn't know unordered_map could got to O(n^2).

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

something wrong with the problem tags

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

I registered but didn't manage to enter the contest in time. Is my rating going to get affected ?

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

In Problem A, those who used ceil() function directly in cout, got WA.. Could you please explain why??

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

Can Anyone tell me what's wrong with my code for D. I'm getting TLE for this Sol link — https://codeforces.com/contest/1234/submission/61662523

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

haha, this div3 was more educational for me than all educational rounds.

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

Admin please rejudge the solutions of problem B2 for those who get TLE for using unordered_map and got AC by changing it to map . It wasted valuable time trying to figuring this out and I thought it was problem with my logic.

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

I did D by using a segment tree where I used ith bit to represent ith character is present or not in subarray. For Query I took 'OR' of left and right interval and then the popcount for unique. For Update first reset the previous value then set the new value. But I got WA on test 8. Can anyone find bug in my code or give small case where I am failing. Submission

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

is there any way we can use binary search on TreeSet In Java. In problem D was adding all the indexes of every character in TreeSet but don't know how to use binary search on TreeSet.

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

    Few useful functions of TreeSet that resembles binary search: tree.floor(int), tree.ceil(int), tree.higher(int), tree.lower(int)

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

How to solve F??

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

Why do I get TLE here? It is simple segment tree working in q * 26 * LOGN https://codeforces.com/contest/1234/submission/61659331

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

I came up with the ideal of problem C early but I can't implement it quickly. It took me more than 1 hour to implement C. So, I have about 30 min left for problem D, I also came up with the solution but I can't debug on time. Now I solved D, very funny experiment =)))

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

I used segment tree, stored set in each node, i think the complexity should be O(q*log(n)*27). And i got TLE, Any idea why?

CODE: https://ideone.com/D2AmFn

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

Pathetic Contest

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

the best hacker link

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

Can anyone explain why unordered_map solution is getting TLE and map solution is getting accepted for problem B2. Is there any specific case where unordered_map is slower than map.

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

    dependent on data type, umap is faster than map when you can sort large arr

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

    Yeah when there is alot of collisons then unordered_map isn't O(1). However ordered_map is always o(1)

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

      I think ordered map is O(logn) in general case... Also I think there is a very similar and famous problem like problem B2 presented today where unordered map can give TLE, it's on codeforces only, — Molly's Chemicals, if anyone want to try it out...

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

how to solve C??

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

    First you can start with the idea that there is only a single path that can allow flow of water from (1,1) to (2,n+1),because if you receive water from one side of pipe, another end can only face a fixed direction if you are getting water from fixed and unique direction (except for the case when you have tilted pipe and receive water from left side to that pipe, so it could continue flow in up or down direction ). So simulate that flow till either an out of bounds occur, otherwise if you reach (2,n+1) before, your answer is "YES", otherwise "NO". Hope it helps

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

    There is an easier way: if both squares in the same column are one of the four states 3, 4, 5, and 6, then water can flow from the current line to another line. Otherwise, you can only let the water continue to flow on the current line. Finally, judge whether the water can flow to the second line of the Nth column.

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

I see people complaining that unordered_map gets TLE, then why didn't I get TLE during contest, even I didn't get it after the contest. (Just submitted 2 min ago)

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

    It's because you are erasing the elements. AC with erase: https://codeforces.com/contest/1234/submission/61669672 TLE without erase: https://codeforces.com/contest/1234/submission/61648570

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

      But still if someone set k = n and throws distinct numbers , wouldn't the first and second be same ? , what makes unordered_map TLE ? (More elements or same elements frequently ? )

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

        Not sure, This might help : https://codeforces.com/blog/entry/62393

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

        what makes it go O(n) is that the numbers entered get hashed to the same hash value, i.e. if internally a poor hash function is being implemented;Generally it has no effect but here I think the test cases were such that unordered_map could not hold good.

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

          Not quite "same hash value" (though that is a factor when dealing with things like strings); the more pertinent issue is bucket collisions. For example, even if there are $$$2^{32}$$$ possible hashes, the actual number of buckets in the map is often much less (stepping up as more values get added based on something called the "load factor"), so if the hash modulo bucket-size is equal you'd get a bucket collision. In such cases C++ unordered_maps would store a linked list in each bucket, making access potentially $$$O(n)$$$ time for adversarial cases.

          Java's HashMaps handles this problem better since Java 8, as if too many items are put into the same bucket, the internal linked list gets converted into a tree, thus worst case access is $$$O(\log n)$$$ time.

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

    Well, you must hack this submission then. He used unordered_set and still got AC

    link

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

    Just submitted 2 min ago

    Hacks are not added yet..

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

My question might be stupid but I gotta ask. What's the point of having a hacking phase in Div3 and Edu rounds if hacks aren't counted in the score?

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

    The point is to let others find the error of your program, improves yourself on a certain level, to reduce unnecessary errors.

    (Or it's just for fun?)

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

I tried to solve D using sqrt decomposition but didn't manage to implement it right, can someone spot the error in my code?

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

    There is also the issue of time limit, it runs in $$$O(Q* nlog(n))$$$ due to sorting all the time. So, sqrt decomposition did not help much.

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

After quiting codeforce contest for about 3 years, I participated in 590 and 589.
It seems the problems have become harder than that of 3 years ago, problem E and F of 590 div3 has similar difficulty of typical div2 E 3 years ago.

I thought I had been more skilled, but the problems have been harder...

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

For Problem F ; You can use SOS DP. Question Statement changed : We need to find out 2 substrings such that they contain different letters and are non overlapping.

If we were to consider the strings as integers, where each character represents a bit ( where in set bit means that, the character is present ). For eg : binary for ac would be 101. Now you need to form all such numbers(strings which cannot have length more than 20, as then it would for sure contain a repeat).So insert all the strings starting at one position without having any repeated character. And then you need to check for each number whether it has a subset of its complement. We will consider the subset having the maximum number of set bits, which can be found out by simple SOS DP. Link to the solution : Using long long int (not required) : it may give tle as this solution : https://codeforces.com/contest/1234/submission/61652445 Using int : https://codeforces.com/contest/1234/submission/61743609

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

Can anyone please tell me what's wrong with my code for B2? 61673618

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

    I believe this part

    freq[arr[st]]=0;
    st++;
    

    is wrong, what you want to do is freq[brr[st]]=0 because you need to remove the start of brr not the start of arr.

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

WTF!!!!

How the Editorial published before end of the hacked phase?!!

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

The long queue really spoiled the contest to be honest With B2 not working for unordered_map i had to make three wrong submission(equivalent to 45 min long queue wait) to finally realize the error. :\ Could have solved c and d had the queue not been so long :(

Changed my dp cause the contest has really spoiled my rating

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

how to solve C problem?I have no idea.

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

    If both squares in the same column are one of the four states 3, 4, 5, and 6, then water can flow from the current line to another line. Otherwise, you can only let the water continue to flow on the current line. Finally, judge whether the water can flow to the second line of the Nth column.

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

My code for B2 got hacked (time limit exceeded) and i really can't understand why. I made a simple solution with a set and a deque. I have seen this kind of solution at everybody and they still got accepted. 61660949. What can be the problem?

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

A moment of silence for my fallen brothers and sisters who got TLEd/hacked in B2 because they were innocent enough to trust the default hash in unordered_map and unordered_set instead of using a custom hash. You were too pure for this cruel world filled with hackers.

You shall be honoured, your sacrifice shall not be in vain. Fear not, you shall rise stronger than ever, and ascend to your rightful place in this world !

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

    I'm one of those brothers. But i still can't fully understand what is the problem with unordered set/map in this problem.

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

      Worst case complexity for default hash is $$$O(n)$$$. So in everyday cases using it might be okay, but if an adversary knows your hashing scheme they might design a hack that will take linear time, causing hack/TLE. Either use set or use a custom, randomized hash.

      Check out this post.

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

        Oh, this is really, really painful :))))). Thank you a lot. From now on, i will be really skeptical when using unordered sets/maps. :)))

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

      You can check out this entry. You can always use unordered_set or unordered_map but with a custom hash function. Read the article, and you will understand.

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

Is it fair that a single person hacks 50 B2 questions with the same test case? The lack of test cases and the long queues made the contest worse!

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

    wrong submissions will anyway fail system tests.... even if he sits silent and doesn't hack anyonee....the final result will be same

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

      These were Accepted submissions.

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

        no they just passed pretests that doesn't mean they are right hacking is done before system test so if a solution is hacked...it would have failed system tests as well

        if we write a correct solution then nobody can touch it .... if we write a wrong solution nobody can save us

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

Getting aged by waiting for system testing.

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

When will the ratings be updated for this contest ?

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

i have given the div-3 contest no-590 my rating has not updated yet...Although its not showing that contest in my recent contest history.I had also given div-3 contest earlier but it also not shown.What is the problem can anybody help

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

Hello, EZZZZZZZZZZ Contest AC in one go.

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

System testing is taking more time than the actual contest.

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

Round was cool, especially problem D and E. Hope in future will be rounds like this!

Thanks for Vovuh for the nice div3 round.

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

Hello all! How can I find my position after a contest? (if I haven't a history)

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

unordered_set let me down on B2 :(

Nice tests!

This post helps, in case anyone who used unordered_map or unordered_set needs it.

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

My Solution to Problem D was skipped . According to the rules , there is no problem to use third party code if it was published before the contest. The problem is a reduced version of the problem DISTNUM . So , i used this as template and changed accordingly , This is my solution . I guess this solution also did something like that . It is a coincidence that both used the same source . So , can you please put me back to the contest ? MikeMirzayanov

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

контест офигенный удачи экспертом

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

I used segment trees for problem D. Each node of the tree was an unordered map of type < long long int, bool >. I am not able to understand how it is showing TLE for test 4. Any help would be highly appreciated. Down below is my code


#include <bits/stdc++.h> using namespace std; #define ll long long int #define rep(i,n) for(i=0;i<(n);i++) #define pb push_back #define mp make_pair #define ff first #define ss second #define all(c) c.begin(),c.end() #define endl "\n" typedef pair< ll, ll > lpair; string s; vector< unordered_map< ll, bool > > tree; void combine(unordered_map< ll, bool >& fin,unordered_map< ll, bool >& s1, unordered_map< ll, bool >& s2) { fin.clear(); unordered_map< ll, bool > :: iterator it; for(it = s1.begin(); it!=s1.end();it++) fin[it->first] = true; for(it = s2.begin(); it!=s2.end();it++) fin[it->first] = true; } void build(ll v, ll t1, ll t2) { if(t1 == t2) { tree[v].clear(); tree[v][s[t1]] = true; } else { ll mid = t1 + (t2 - t1)/2; build(2*v + 1 ,t1,mid); build(2*v + 2,mid+1,t2); combine(tree[v],tree[2*v+1],tree[2*v+2]); } } unordered_map< ll, bool > query(ll v, ll t1, ll t2, ll left, ll right) { map< ll, bool > ch; if(left > right) return ch; if(left == t1 && right == t2) return tree[v]; ll mid = t1 + (t2 - t1)/2; unordered_map< ll, bool > ans; unordered_map< ll, bool > s1 = query(2*v+1,t1,mid,left,min(right,mid)); unordered_map< ll, bool > s2 = query(v*2+2, mid+1, t2, max(left, mid+1), right); combine(ans,s1,s2); return ans; } void update(ll v, ll t1, ll t2, ll pos, char c) { unordered_map< ll, bool > ch; if(t1 == t2) { tree[v].clear(); tree[v][c] = 1; } else { ll mid = t1 + (t2-t1)/2; if(pos <= mid) update(2*v+1,t1,mid,pos,c); else update(2*v+2,mid+1,t2,pos,c); combine(tree[v],tree[2*v+1],tree[2*v+2]); } } void solve() { cin>>s; tree.clear(); tree.resize(4*s.length()+1); build(0,0,s.length()-1); ll q,type,x,y; ll n = s.length(); cin>>q; while(q--) { cin>>type; if(type == 1) { char temp; cin>>x; cin>>temp; update(0, 0, n-1, x-1, temp); } else { cin>>x>>y; cout<<query(0, 0, n-1, x-1, y-1).size()<<endl; } } } int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); solve(); return 0; }
»
2 месяца назад, # |
  Проголосовать: нравится -8 Проголосовать: не нравится

epic contest for epic programmers i congratulate you!1

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

WHY did you add anti-unordered set tests in B2? I could've become expert in this round https://codeforces.com/contest/1234/standings/participant/28564088# unordered set https://codeforces.com/contest/1234/submission/61718932 usual set