LGM's blog

Codeforces Beta Round #57 (Div. 2)
By LGM, 13 years ago, In English
Hello!

I am glad to invite you to participate in Codeforces Beta Round #57 (Div. 2).
Today's Contest was prepared by Amir Goharshady and Me.

We are thankful to Mike Mirzayanov , Artem Rakhov , Gerald Agapov , Mohammad Javad Naderi , Saeed Ilchi and Maria Belova.

Today's contest is dedicated to Khaje Nasir Tusi (Great Persian mathematician) since today is the national day of engineering in Iran.



Today for the first time in Codeforces we have Persian statements available for download.
 You can download PDF version of statement from this link when the contest starts:
Persian

Have a good contest.

Alireza Farhadi and Amir Goharshady

نسخه پارسی این پست را در اینجا ببینید

UPD:

  • Vote: I like it
  • +31
  • Vote: I do not like it

Comments Comments (55)
| Write comment?
13 years ago, # |
  Vote: I like it +9 Vote: I do not like it
Good Luck To All!
→ Reply
13 years ago, # |
  Vote: I like it -14 Vote: I do not like it
Thank you very much.
Is it mean many math problems in contest?
→ Reply
13 years ago, # |
  Vote: I like it +16 Vote: I do not like it
very thanks for you.
از همه شما متشکریم
→ Reply
13 years ago, # |
  Vote: I like it +7 Vote: I do not like it
Continue having problem statements in Persian language. That's great.
→ Reply
13 years ago, # |
  Vote: I like it +8 Vote: I do not like it
nice job!
→ Reply
13 years ago, # |
← Rev. 2   Vote: I like it +1 Vote: I do not like it
i have been trying for 5 minutes to upload , why its not progressing???

Edit: It has become 15 minutes. I am not able to upload . What is the problem?
→ Reply
13 years ago, # |
  Vote: I like it +5 Vote: I do not like it
درود !

تو سوال دوم چرا
test case 4 (‫‪Ira__Persiann__Wonderful‬‬)

غلطه ؟؟؟؟؟
لطفا زود تر جواب بدید !
→ Reply
13 years ago, # |
  Vote: I like it +6 Vote: I do not like it
دمتون گرم!!
→ Reply
13 years ago, # |
  Vote: I like it +1 Vote: I do not like it
بیشتر دمتون گرم !!!!!!!!!!! :D

ولی سخت بود !
→ Reply
13 years ago, # |
  Vote: I like it +5 Vote: I do not like it
!!!ایول اسمه منم گفتی
  :ِD  معروف شدم دیگه 
→ Reply
13 years ago, # |
  Vote: I like it +4 Vote: I do not like it
Thanks for Mike and all friends.
I hope good luck all friends.
از دوستان ایرانی هم تشکر دمتون گرم
واقعا تو این اوضاع خیلی خوب امدید این کارو.
→ Reply
13 years ago, # |
  Vote: I like it +4 Vote: I do not like it
I am facing problem in uploading the source code. I checked at other OJ sites uploading is working there . In gmail also it works fine. I am using Firefox. I reinstalled it.

Please Help!
→ Reply
13 years ago, # |
  Vote: I like it +12 Vote: I do not like it
As an Iranian I request you not to write Persian here! As we don't like others write in languages we don't know.
The contest was awesome! Except for problem C!! Hope to see more Iranian contests!
→ Reply
  • 13 years ago, # ^ |
    ← Rev. 3   Vote: I like it +4 Vote: I do not like it
    We just write Persian in answer to Iranians but I ask everyone to use the Persian post for Persian Discussion
    → Reply
13 years ago, # |
  Vote: I like it 0 Vote: I do not like it
Can anyone suggest a solution for problem no 5 ?
→ Reply
  • 13 years ago, # ^ |
      Vote: I like it +4 Vote: I do not like it
    It can be solved in O(nlgn) using a segment tree or using merge-sort
    → Reply
  • 13 years ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it
    First let's find the number of pairs i < j, ai > aj.
    How many numbers aj are there to the right of i such that ai > aj? To answer this question you should maintain a binary indexed tree / segment tree or a similar data structure: go from right to left, calculate the answer for ai and add ai to the tree.

    Having done this, notice that the problem is pretty much the same for triples: the number of pairs aj, ak to the right of i is equal to the sum of the answers to the previous problem for all aj < ai, j > i.
    → Reply
    • 13 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it
      а можно поподробней "go from right to left, calculate the answer for ai and add ai to the tree."
      как именно мы используем предыдущие полученные значения для нахождения ответа для ai ? 
      мы же не за квадрат делаем? :)
      → Reply
      • 13 years ago, # ^ |
        ← Rev. 2   Vote: I like it 0 Vote: I do not like it
        WLOG ai are numbers from 0 to n - 1.
        where xj is 0 if you haven't yet added j while passing from right to left; otherwise it's 1. Not height, but strength, i.e. the strength of the soldier, I don't know how to edit it now.

        For the second step, xj is either 0 or ans[j].
        → Reply
        • 13 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it
          Alternatively, you can multiply the numbers of pairs i < j, ai > aj and j > k, aj > ak to get the answer for j.
          This requires two passes: one from left to right and one from right to left.
          → Reply
        • 13 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it
          спасибо!
          → Reply
13 years ago, # |
  Vote: I like it 0 Vote: I do not like it
Well, it was a bit frustrating to get 100 points for the fact that despite sys.setrecursionlimit (100000), Python is unable to handle recursion beyond few thousands... It just silently breaks (instead of the "maximum recursion depth exceeded" message if the recursion limit is the default, 1000).
→ Reply
  • 13 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    У меня было такое же. На форуме страшные вещи написали: http://python.su/forum/viewtopic.php?id=8804
    → Reply
    • 13 years ago, # ^ |
        Vote: I like it +1 Vote: I do not like it
      Ах вот оно что! Как и "%I64d" vs. "%lld" на MinGW C++, это — тлетворное влияние Microsoft!

      За ссылку спасибо. Предлагаю админам CodeForces ею воспользоваться :) . Но — если так сделать, будут ли эти мегабайты на стек всегда задействованы, то есть не будет ли необоснованных Memory Limit?
      → Reply
  • 13 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    Ещё немного frustrating, что решение за O(n*log(n)) на Python к задаче E не проходит по времени. Моё решение на тесте с n = 1000000 работает 45 секунд!
    → Reply
    • 13 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it
      Да это-то уже привычно, что несколько миллионов операций на Питоне в две секунды уже не укладываются...
      → Reply
  • 13 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    Нет, я это прекрасно знал. И даже знаю, как это обходить ;)
    Просто люблю писать всякую глупость и давать возможность людям почувствовать, какие они умные))
    → Reply
    • 13 years ago, # ^ |
        Vote: I like it +2 Vote: I do not like it
      И как это обходить, кроме того, чтобы не использовать встроенный стек?
      → Reply
      • 13 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it
        Не пойму, почему мое решение не упало из-за ограниченного стека? 
        → Reply
        • 13 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it
          Потому что не было системного теста с такой рекурсией. Я перепослал взломанное решение gurovic и оно взяло AC
          → Reply
13 years ago, # |
  Vote: I like it 0 Vote: I do not like it
In this contest, after my code for problem A passed all the pretests, there is NO LOCK option, while in #56 it did have. Anyone knows why?
→ Reply
13 years ago, # |
  Vote: I like it 0 Vote: I do not like it
Was cin too slow for problem E?
→ Reply
  • 13 years ago, # ^ |
      Vote: I like it +5 Vote: I do not like it
    Yes
    You needed scanf
    → Reply
    • 13 years ago, # ^ |
      ← Rev. 3   Vote: I like it 0 Vote: I do not like it
      well, I resubmit the same solution (TLE case 41 in system test) and it passed...
      why?
      "I think was lucky... I wish I won't need this lucky for the next contests =)"
      → Reply
      • 13 years ago, # ^ |
          Vote: I like it +5 Vote: I do not like it
        Try calling ios::sync_with_stdio(false). It makes cin faster. Check if your initial solution passes.
        → Reply
        • 13 years ago, # ^ |
          ← Rev. 2   Vote: I like it 0 Vote: I do not like it
          but it already passed, the same code.
          (I just saying because I think is discouraging the same solution gives TLE and ACC xD)
          → Reply
  • 13 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    yes!
    → Reply
13 years ago, # |
  Vote: I like it +1 Vote: I do not like it
we are very surprised by this contest.
It has very good design (thanks a lot!).
Plz put persian translate of every problem in every future contest too.
Thnx.
→ Reply
13 years ago, # |
  Vote: I like it +9 Vote: I do not like it
By the way, it is 1337 post.
→ Reply
13 years ago, # |
  Vote: I like it 0 Vote: I do not like it

If any one have time plz tell...why the difference in output ?

http://ideone.com/GSqVs

Here it gives 3. and there at ideone it gives 7.

This was Q4.

→ Reply
  • 13 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it
    remove this line :
    maxx = vec[s][i].second;
    change this visited = vector<int> (n ,0);
    to visited = vector<int> (n + 1,0);
    → Reply
13 years ago, # |
  Vote: I like it 0 Vote: I do not like it
please can any one explain to me the idea behind problem E ? Thanks in advance.
→ Reply
13 years ago, # |
  Vote: I like it +9 Vote: I do not like it
I'm looking forward to the similar international contests. It's a good opportunity to improve the programming skills and learn something about foreign culture simultaneously. Well done :)
→ Reply
13 years ago, # |
  Vote: I like it +3 Vote: I do not like it
Thanks a lot it was a nice contest :)
→ Reply