NALP's blog

Codeforces Round #147 (Div. 2)
By NALP, 12 years ago, translation, In English

Hi!

A few hours later you're lucky to participate in Codeforces Round #147 for Div.2 participants, but traditionally the others can take part out of the competition. It has been prepared by me (NALP), Igor Kudryashov (Igor_Kudryashov), Pavlik Holkin (HolkinPV), Gerald Agapov (Gerald), Mary Belova (Delinur) and Mike Mirzayanov (MikeMirzayanov).

Traditionally I wish good luck, accepted solutions and successful hacking attempts for you!

The standart scoring system will be used: 500-1000-1500-2000-2500

UPD: The contest has ended, congratulations to the winners:

  1. try_skycn

  2. AntiKismet

  3. dianbei_03

  4. Uncia

  5. Bigsophie

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

Comments Comments (81)
| Write comment?
»
12 years ago, # |
  Vote: I like it -16 Vote: I do not like it

:-W

→ Reply
»
12 years ago, # |
← Rev. 3   Vote: I like it +3 Vote: I do not like it

Gerald always gives a hand to prepare the problems in recent contests :D

→ Reply
»
12 years ago, # |
← Rev. 3   Vote: I like it +60 Vote: I do not like it

sorry for posting here but,My contribution is -69,I do not know what to do :(

→ Reply
»
12 years ago, # |
  Vote: I like it +4 Vote: I do not like it

Have a good contest everyone! :)

→ Reply
»
12 years ago, # |
  Vote: I like it +5 Vote: I do not like it

What advantages does the stardand scoring system have over the dynamic one?

→ Reply
  • »
    »
    12 years ago, # ^ |
      Vote: I like it +8 Vote: I do not like it

    I prefer dynamic one :D

    → Reply
»
12 years ago, # |
← Rev. 2   Vote: I like it +9 Vote: I do not like it

seems, there is huge change for me to be hacked today.... :P

→ Reply
  • »
    »
    12 years ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    I want to be in your room in this case.

    → Reply
    • »
      »
      »
      12 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      yes..... after a long time.... none of my solution (A, C) hacked.... :D

      → Reply
  • »
    »
    12 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Me too, so we can hack each other :) Let hack and find who is the better =]]

    → Reply
»
12 years ago, # |
  Vote: I like it +11 Vote: I do not like it

Thanks for the good contest

→ Reply
»
12 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

check out my output here http://ideone.com/aCIGH7

when i run it as a custom test here i get this output instead

6
2 2 1 1
3 1 1 2
1 2 1 3
1 1 2 1
1 3 2 2
2 1 3 1

if I change the 2d arrays to maps instead i get the desired output. Any idea why this happens?

→ Reply
  • »
    »
    12 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    array nums is very small. we can have up to 2500 numbers.

    → Reply
»
12 years ago, # |
  Vote: I like it +22 Vote: I do not like it

Wow , very fast judging :D

→ Reply
»
12 years ago, # |
  Vote: I like it +12 Vote: I do not like it

System test is really fast !!!

→ Reply
»
12 years ago, # |
  Vote: I like it +13 Vote: I do not like it

Wow, what a fast judge!

→ Reply
»
12 years ago, # |
  Vote: I like it +35 Vote: I do not like it

Really enjoyed the contest. And it also helped me identify a bug in our ACM team's notebook. Many thanks to the author :D

→ Reply
»
12 years ago, # |
  Vote: I like it +8 Vote: I do not like it

i am from China i am sorry i can't use English well i only wrote A problem and C problem The B problem can make a right answer and check with read by computer i don‘t know how to do D AND E who can help me

→ Reply
  • »
    »
    12 years ago, # ^ |
      Vote: I like it +4 Vote: I do not like it

    Problem D was difficult to understand even for those who know English. Can someone explain Problem D with an example.

    → Reply
    • »
      »
      »
      12 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      I think the question had it well explained. The reason for not putting a bit complicated example is that it would be too easy to guess the answer, rather than getting the information from the problem itself :)

      → Reply
      • »
        »
        »
        »
        12 years ago, # ^ |
          Vote: I like it +4 Vote: I do not like it

        Yes, the description was quite clear. The main thing here to understand is the the minimum weight will always be 2. Now just try to think of a way to connect the nodes.

        Problem E is Standard Min Cost Max Flow problem.

        → Reply
»
12 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Today is my unlucky day I save my solution for problem C in file B.cpp but I upload C.cpp to judge

→ Reply
  • »
    »
    12 years ago, # ^ |
      Vote: I like it -7 Vote: I do not like it

    i did the same mistake in a round last month..... :(

    → Reply
  • »
    »
    12 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I always use the same file to code, after pass the pretest I clear the code and only use my macro.

    → Reply
»
12 years ago, # |
  Vote: I like it +3 Vote: I do not like it

I don't knw why I am getting "Idleness limit exceeded on test 8"....... for Problem B. Seems mysterious for me..... plz help...

http://www.codeforces.com/contest/237/submission/2434517

→ Reply
  • »
    »
    12 years ago, # ^ |
    ← Rev. 2   Vote: I like it +5 Vote: I do not like it

    Maybe its because the declaration co place[mo]; where mo is only 101. But it should be 100² + 1 because the number s can be at most 100²

    → Reply
    • »
      »
      »
      12 years ago, # ^ |
      ← Rev. 5   Vote: I like it 0 Vote: I do not like it

      Oh thx..... now it is accepted...... I thought I would get RTE for these.... anyway good experience without any penalties...... thx again....

      → Reply
    • »
      »
      »
      12 years ago, # ^ |
      ← Rev. 4   Vote: I like it +5 Vote: I do not like it

      There is no reason to vote negative at this comment, he has the good answer. place[i] is used for store the position on the array of the cell who has number i on it. So, 1<=i<=s, 1<=s<=n*max(ci), 1<=n<=50 and 1<=ci<=50.

      Edit: oups, too late: the comment has received new positives votes before I post my comment

      → Reply
      • »
        »
        »
        »
        12 years ago, # ^ |
        ← Rev. 2   Vote: I like it -6 Vote: I do not like it

        You are right cup_of_tea....... this definately help me in future contest.... Thx god it was not rated for me... gdisastery really deserves positive feedback... But I cannot vote twice... maybe I have to try from different ID..... :D

        → Reply
»
12 years ago, # |
  Vote: I like it +1 Vote: I do not like it

Omg, really fast judge!

→ Reply
»
12 years ago, # |
  Vote: I like it +1 Vote: I do not like it

I am facing a strange problem in the practice session . My solution for problem C is returning -1 for the first test case when i submit my .cpp file but it returns the correct value ( 3 ) when running in my pc.

→ Reply
»
12 years ago, # |
  Vote: I like it -21 Vote: I do not like it

I'm looking to be on top10 contributors, could you help me ? =/

→ Reply
  • »
    »
    12 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Post funny comments with memes (or not) will not suffice for become top contributor. If you really want to progress, you should make interesting posts on your blog, or give interesting answers.

    Anyway, Good Luck!

    → Reply
    • »
      »
      »
      12 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      I'm kidding man.

      → Reply
      • »
        »
        »
        »
        12 years ago, # ^ |
          Vote: I like it +5 Vote: I do not like it

        No one could find it out, even when looking at kiddy-kiddy Po on your ava:)

        → Reply
»
12 years ago, # |
  Vote: I like it -12 Vote: I do not like it

Is it rated?

→ Reply
»
12 years ago, # |
← Rev. 2   Vote: I like it +7 Vote: I do not like it

Testing is fast — very good.

Rating update is slow — not very good.

Just joking

→ Reply
»
12 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Sucks that I kept getting WA on C because I put == as opposed to >=. On the bright side, you can do C in linear time as opposed to using a binary search.

→ Reply
  • »
    »
    12 years ago, # ^ |
      Vote: I like it +8 Vote: I do not like it

    Really? Remember that the sieve of Eratosthenes is O(n log log n) ;)

    → Reply
    • »
      »
      »
      12 years ago, # ^ |
        Vote: I like it +9 Vote: I do not like it

      In fact sieve of Eratosthenes can be done in O(n) Linear_sieve

      → Reply
    • »
      »
      »
      12 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Yeah I wasn't taking into account the sieve at the beginning.

      I saw a lot of binary searches and I thought maybe my algorithm wrong. Good thing that wasn't the case.

      → Reply
»
12 years ago, # |
  Vote: I like it +2 Vote: I do not like it

Judging was too fast but rating dont provide yet...I thing something is going WA...:D

→ Reply
»
12 years ago, # |
  Vote: I like it +4 Vote: I do not like it

Here is a screencast of me solving this round: youtube To watch comfortably (and see clear text), choose 1080p and watch full-screen on a 1920x1080 resolution or higher. I will also provide a file in 1680x1050 for download later if you prefer.

→ Reply
  • »
    »
    12 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Good, very useful video! thanks

    → Reply
  • »
    »
    12 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Can you upload your "Hightail" program? It may be useful

    → Reply
    • »
      »
      »
      12 years ago, # ^ |
        Vote: I like it +15 Vote: I do not like it

      It's not yet ready to be called even pre-alpha or something (most of the buttons just outright don't work), but if you're interested: github IF you want to help with development, that would be very very welcome. There is a ready list of tasks (issues) on the github page.

      → Reply
  • »
    »
    12 years ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    And the file download is ready.

    → Reply
  • »
    »
    12 years ago, # ^ |
      Vote: I like it +8 Vote: I do not like it

    Dude, just keep doing it! I think it would be great to have some alternative on Egor Youtube channel.

    → Reply
»
12 years ago, # |
  Vote: I like it +17 Vote: I do not like it

Here are the cheaters! wangyedong CHFB_oXbT 389804652 jionghehe Their E Codes are the same!

→ Reply
  • »
    »
    12 years ago, # ^ |
      Vote: I like it +28 Vote: I do not like it

    Registered: 22 minutes ago And you're registered just to say that they're cheaters ?

    → Reply
  • »
    »
    12 years ago, # ^ |
    ← Rev. 2   Vote: I like it +28 Vote: I do not like it

    They pretend to be Japanese, But their function names are in Chinese :(.

    → Reply
»
12 years ago, # |
  Vote: I like it +8 Vote: I do not like it

waiting for editorial! thanks already

→ Reply
»
12 years ago, # |
  Vote: I like it 0 Vote: I do not like it

in problem E. Build String , we should write min cost flow algorithm , but what will be in the role of nodes ? From which node to which are we finding flow ?

→ Reply
  • »
    »
    12 years ago, # ^ |
    ← Rev. 3   Vote: I like it +7 Vote: I do not like it

    As I see it, you need n+26+2 nodes: a node for each given string, a node for each distinct letter in t and source and sink. The edges will be:

    a) source -> string i, with capacity ai and cost i (no more than ai characters can be erased from the i-th string and each operation costs i).

    b) string i -> letter c, with capacity [the number of times c occurs in the i-th string] and cost 0 (to erase at most as many letters as there are in the i-th string).

    c) letter c -> sink, with capacity [the number of times c occurs in t] and cost 0 (we shouldn't erase more c-s than there are in t overall).

    → Reply
    • »
      »
      »
      12 years ago, # ^ |
      ← Rev. 2   Vote: I like it 0 Vote: I do not like it

      thanks , i found out now . Firstly i thought flow was going from each string to the main source. :)

      → Reply
»
12 years ago, # |
  Vote: I like it -6 Vote: I do not like it

Problem E is Standard Min Cost Max Flow problem. China's NOIP don't test it, I think i need not do it now; i also want to know what the problem 4 mear

→ Reply
»
12 years ago, # |
  Vote: I like it 0 Vote: I do not like it

We are waiting for the editorial.

→ Reply
»
12 years ago, # |
  Vote: I like it 0 Vote: I do not like it

In the problem C I am using binary search to find the minimum value of l.prime[i] stores the number of prime numbers upto i.I am using the following code to return true or false.

bool check(int l) { for(int x=a;x<=b-l+1;x++) { if(prime[x+l-1]-prime[x-1]>=k) return true; }

return false; } and I am getting the wrong answer. Please tell what is wrong in my approach.

→ Reply
  • »
    »
    12 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    It should be this : bool check(int l) { for(int x=a;x<=b-l+1;x++) { if(prime[x+l-1]-prime[x-1]<k) return false; } return true; }

    → Reply
»
12 years ago, # |
  Vote: I like it 0 Vote: I do not like it

@problem setter : Editorial ??

→ Reply
»
12 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

Hi NALP,is there any editorial for this round?

UPD:Could anyone tell me how to solve prob D T-decomposition?

→ Reply
»
12 years ago, # |
  Vote: I like it -15 Vote: I do not like it

can anbody plzz tell me wats wrong with the following code..its giving wrong ans on pretext 10

include

using namespace std;

define MAX 11111

int a[MAX][2]; int main() { int t; cin>>t; for(int i=0;i<t;i++) cin>>a[i][0]>>a[i][1]; int cash=1; int maxcash=1; for(int i=0;i<(t-1);i++) { if(a[i+1][0]==a[i][0]) { if(a[i+1][1]==a[i][1]) cash++; else { if(maxcash<cash) maxcash=cash; cash=1; } } else { if(maxcash<cash) maxcash=cash; cash=1; } } if(maxcash<cash) maxcash=cash; cout<<maxcash<<endl; return 0; }

plz reply

→ Reply
  • »
    »
    12 years ago, # ^ |
    ← Rev. 2   Vote: I like it +3 Vote: I do not like it

    You are not getting Wrong Answer but Run Time Error. Increase the size of your array : change #define MAX 11111 to #define MAX 111111.

    → Reply
»
12 years ago, # |
  Vote: I like it 0 Vote: I do not like it

will we have an editorial for this round?I am not able to solve the young table problem,could someone give a hint?

→ Reply
  • »
    »
    12 years ago, # ^ |
    ← Rev. 4   Vote: I like it 0 Vote: I do not like it

    My approach:sorting

    for any young table,like

    a1 a2 a3 a4 a5 a6

    a7 a8 a9 a10

    a11 a12 a13 a14

    a15 a16

    the following satisified: a(i)>a(i+1)

    → Reply