xander7b's blog

By xander7b, 11 years ago, In English

The problem is ACPC 2012 problem, called "No Name". http://mirror.codeforces.com/gym/100155/problem/B

The solution is to use a binary indexed tree/fenwick. A sample solution I found was here: http://ahmed-aly.com/f.jsp?i=p2lxbV2O&h

I understood what the solution is doing. Basically creating the final string first, and then sort of "hiding" everything, and then revealing them one-by-one as insertions are being made, so when asked to print, can print only from those who are "visible". I convinced myself that the second stage of printing the answers is correct, because assuming I got the final string correctly, none of the insertions change the order of the characters of each word, or the words relative to each other, so "hiding" later inserted words and printing from ones currently inserted should be okay.

However, I tried and couldn't formulate a solid argument regarding why the idea of inserting backwards in that way in the first stage of creating the final string is "correct". I could simulate it on some examples and see that it works, but can't reach to a firm decision like I did with the second phase of the solution when it prints and answers.

Can someone help me and provide more rigid argument for the correctness of the given solution ? (or other solution if possible)

Full text and comments »

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

By xander7b, 11 years ago, In English

http://mirror.codeforces.com/gym/100155

When I try to view any problem it states that:

"Can't download contest descriptor from external storage. Are you sure you have at least one contest release?"

Full text and comments »

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