bluemmb's blog

By bluemmb, 8 years ago, In English

Hi.

There are n<=100 customers round a table. i'th of them wants food of type a[i] but waiter has brought food of type b[i] for him! ( note that [b] is a permutation of [a] ).

Now customers want to move foods such that each of them get his favorite food. At each second each of them can perform one of these :

1 : pick one of the foods in front of him and give it to the person on his LEFT side

2 : pick one of the foods in front of him and give it to the person on his RIGHT side

3 : (1 + 2) simultaneously

There is one additional limitation that at each second no one can have more than 5 foods in front of him. We want to know the minimum time needed to do the job. ( each customer get his favorite food )

Sample : ( Squares are customers with their favorite food and Circles are foods on table. )

We need 2 seconds.

Can you help me to solve this problem ? It's kind of you :)

Full text and comments »

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

By bluemmb, 8 years ago, In English

Can you help me solve this problem ? ( original source )

Thanks in advance.

Full text and comments »

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

By bluemmb, 8 years ago, In English

We have N persons numbered from 1 to N. Also there are M identical rooms with infinity capacity.

In how many ways we can distribute persons in rooms such that each room contains at least 1 person ?

Two ways A and B are regarded as the same if for any room in A, there exists a room in B that the persons in these two rooms have the same set of numbers. In other words, rooms are indistinguishable.

for example : 2 rooms , 3 persons , ans = 3 : (1)(2,3) , (2)(1,3) , (3)(1,2)

Full text and comments »

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

By bluemmb, history, 8 years ago, In English

Hi. How to solve this problme ? Link

Problem statement is simple : You are given a table of characters and Q queries. Each query is a cell in table (X=char in that cell) , you must delete all the cells which contain X and are reachable from it by passing over just X's. After each query you must shift the full cells into the empty cells of their left side and then bottom.

For example : query (1,1) step by step :

You must output the table after performing all the queries.

Thanks in advance ...

Full text and comments »

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

By bluemmb, 8 years ago, In English

Hi. I'm stuck with this problem.

Problem : Given set of distinct points and a number A. You have to find maximum number of points in a rectangle with 0 < area <= A.

I have written many different solutions for it but all of them have failed ...

Basic idea is choosing a fixed width and find largest possible height then find maximum number of points in current fixed size rectangle ... I have solved latest problem once by segment tree(Wrong Answer) and once simply by two pointers(Wrong Answer) ...

Can someone help me ? thanks in advance ...

UPDATE

The problem was that LiveArchieve didn't work correctly ...

I got accepted in POJ with modifying and optimizing above solutions : SegmentTree , TwoPointer( I couldn't compute it's complexity but I think it can be huge , however , It got accepted !!! )

Full text and comments »

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

By bluemmb, history, 8 years ago, In English

It's about 3 days that I can't access vjudge. Is there any news or information about it ?

Full text and comments »

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

By bluemmb, history, 8 years ago, In English

Hi. After 4 years in college, I felt that I really need to have some more fun and also knew that my English skill is a serious problem. Finally i come up with this solution , I have been writing a blog in English since a week ago.

I try to update it every day or two days with new post consisting of two sections ( from 4'th post ) :

  • Second part is about one of the attractive problems that I have solved that day with little explanation about it's solution.
  • First part is funny things that I had during the day ( maybe was boring for you because i write it to my friends )

I am trying to make the Algorithmic part better , I wish it become useful for some of the users and for improving my English.

Blog Link

Full text and comments »

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

By bluemmb, history, 8 years ago, In English

I had been solving Bad Luck Island and I wrote this formula for calculating the probability of meeting for example Rock and Paper :

rsp = r + s + p;
rs = r + s;
rp = r + p;
sp = s + p;

P_rp = (r/rsp) * (p/sp) + (p/rsp) * (r/rs);

I figured out that it is wrong, but I want to know why and What am i calculating here ?!

because when i use this formula for all 3 possible meetings , and sum up them , it equals to 1! and I don't know what is the meaning of this formula !!!

( sorry if it is a stupid question! )

Full text and comments »

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

By bluemmb, 8 years ago, In English

this problem says that : we have an array of size n. we must choose k range of size m from these numbers that sum of their numbers will be maximum .

DP Solution with complexity of O(N*K) is obvious. I wonder can we do better ?

Full text and comments »

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

By bluemmb, history, 8 years ago, In English

in creating mashup contest , codeforces says "Can't find problem descriptor" for all problems even for problems that we used in previous contests . what is the problem ??? we have contest about 30 min form now.

Full text and comments »

Tags gym
  • Vote: I like it
  • -10
  • Vote: I do not like it

By bluemmb, history, 8 years ago, In English

I know that we can add problems with their link from polygon to mashup contest and use that contest in group. But how we can add a Contest from polygon to mashup or group ? I couldn't find link like problems for contests. shall we add problems one by one !?

Full text and comments »

  • Vote: I like it
  • 0
  • Vote: I do not like it

By bluemmb, history, 8 years ago, In English

Hi , obviously this problem can be solved in O(N*M) with help of an array for counting, because numbers are <=1000 . but what is the best algorithm for solving this problem when numbers are <=1e9 ?

I wrote this code that works in O( N*M*log(N*M) ) but it got TimeLimit ( in 1second ) . How can we reduce this complexity ?

UPD : sorry , I linked to wrong source code. fixed.

Full text and comments »

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

By bluemmb, history, 9 years ago, In English

Last year we saw a contest in gym that all the problems was about Statistics and Probabilities and we didn't solve them.Now we want to try it again but I can't find it now.

Do someone know which is ? tanks

Full text and comments »

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

By bluemmb, 9 years ago, In English

Hello .

I tried to solve this problem but my submission got SIGSEGV for one of tests and I can't find reason!

I used huge random and clever inputs many times for my solution and test them with online judge compile options but it pass all of them without problem.

Can someone help me ?

Little Details : I wrote comment for codes and I used ...

for solving problem >> Dfs Order + Segment Tree , actually I found path from root to all nodes and updated them with help of segment tree on range that are under related node in dfs order.

So Answer is : ans(u) + ans(v) — 2*ans( lca(u,v) );

for finding LCA >> EulerTour + SparseTable

Full text and comments »

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

By bluemmb, history, 9 years ago, In English

I got this email some hours ago :

Title : Codeforces , From : Penny Zhang pzhang9191@gmail.com

Hello all, __ If you're interested in exchanging solutions to Codeforces (and maybe even TopCoder) problems in-contest, reply to let me know and I'll explain the system in more detail. The main goal of the system is to prevent leeching (receiving solutions, but not giving), and to prevent detection (altering code). I'm expecting a final ring of size 4-8. I suggest you make a new email account for this to maintain anonymity; use a proxy if you want to take it a step farther. Ideally, no one in the ring should know a single other person. __ Quick note: This setup will not be ready by the next contest, which is in less than 12 hours. I hope to be ready for round 321 (in several days), though. __ Again, reply with "I'm interested" using an alternate email account (preferably), and I'll include you in a group email. __ Thank you all, pzhang

....................................

ok, I am Aboslutely Secure :D . be sure nobody will not know ...

UPD : new email address = plaviajvar3@yandex.com ( gepardo , Thanks for report )

Full text and comments »

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

By bluemmb, history, 9 years ago, In English

Hi , this is my today tough story and pictorial editorial for problem 389D/388B. ( first of all sorry for my english )

After lunch I decided to solve a hard problem ( compared to my skills ) Fox and Minimal path.

Problem wants a graph that total number of shortest paths between nodes 1,2 will be k (1<=k<=1e9). but I didn't know a simple condition will kill me today ... you can use at most 1000 nodes.

first time I decided to decompose k to prime factors and create paths like this :

I couldn't find any solution for big primes! but because I thought my solution is true so they will not be in test cases !!! After coding , submitting and getting WA on test 11 , and having no idea for another solution , I decided to read the editorial .

After reading the editorial I found that I am so stupid , why I forgot binary representation !!! anyway I start to reading his solution for know how to create graph. but it was terrible to understand! so I spend many time to know how this create the graph but ... :( ( a simple picture help people to understand what you said and wrote, please! )

I started hard to thinking on create the tree and found this solution :

but it uses about 2000 nodes and certainly it will get WA.

Again started to thinking about reducing the number of nodes and yeaaaa , i find it !!!

I did a mistake in my calculation and after coding and print last id ... O NOOOOOO !!! extra 50 nodes exist :((( ( later I figure it out that maybe with deleting some nodes can reduce it to <=1000 )

damn it :( give up and watch next section of Breaking Bad serial ...

but ... suddenly I compressed the simple roads of last graph in my imagination and it seems good!

rapidly , started to proving that this graph can't have extra nodes and can't create extra shortest paths and it was so simple to proof. it was like this :

Again clean whole last code and write from zero ... Run ... OOKKKKK : last id = 185 !!! It seems ok, but because of big output , I couldn't check it and decided to entrust it to codeforces checker. I was tired and scared that it will wrong again, so I was watching the numbers ... test 10 ... test 13 ... test 29 ... OK ... Accepted :) :) :)

It was like a Refresh for my Head CPU. so i decided to reduce number of nodes again ... after some minutes, again I compressed some of paths and nodes and it was like this :

This time changing a bit in creator function was sufficient and again I am waiting for watch last id ... OH MY GOD : 94 nodes. And Solution ACCEPTED again.

I was so excited ... first time I thought that isn't solution for some numbers and I must be careful about using so efficient from nodes ... and after hard working whole necessary node is 94 :D

So Again, I learnt give up is not solution.

Full text and comments »

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

By bluemmb, history, 9 years ago, In English

Maybe this problem 570D - Деревянные запросы have weak testcases!

Imagine this tree :

and these queries :

1 250001

2 250001

...

250000 250001

Now How 12519227 got ACCEPTED ! In function run , for(ans1..ans2) can be O(n). So this solution is O(n^2).

I checked it in polygon and it get TimeLimit even with 4 second.

I want to know, Is it OR I am wrong ??

Full text and comments »

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

By bluemmb, history, 9 years ago, In English

Maybe this is so strange and negligible but I have problem with this :

In many IDEs and Editors TAB character is equal to 4 spaces but in codeforces submission views it is equal to 8 spaces.

It isn't matter when you use it just for Indenting codes. but for more readability I keep comments in a vertical line with tab and sometimes use comments for visualize something in code and because of this problem they will be ruin in submission page so I must copy code in my editor again and view it.

VisualStudio and some other use of exactly 4 space characters instead of tab so this is ok also. but Notepad++ , Sublime , ... use of tab character itself.

Can you consider this? thanks for great works.

Full text and comments »

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

By bluemmb, history, 9 years ago, In English

why some members haven't Group tab? I invited my friend [user:http://mirror.codeforces.com/profile/araz] to group , when he click on invitation link, GROUPS page showed but table of his groups are empty and nothing happened!

This happened before for my other friend. What he can do ?

Full text and comments »

  • Vote: I like it
  • -1
  • Vote: I do not like it

By bluemmb, 9 years ago, In English

Hello. When i try to use testlib with c++11 , arise this error :

In file included from test.cpp:7:0:
testlib.h: In function 'void __testlib_set_binary(FILE*)':
testlib.h:346:20: error: 'fileno' was not declared in this scope
 setmode(fileno(file), O_BINARY);
                    ^

Is compatible version released (couldn't find)? or Problem is removable easily ?

Full text and comments »

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

By bluemmb, 9 years ago, In English

After create contest in Mashups , we can edit that and in edit form exist a field with "Contest Type" title .

I want to know what is the difference between this field values ? what influences they have on contest scores , ... ? I want to set different scores for problems , how i can do it ?

Contest Type available values :

  • Official ACM-ICPC Contest

  • Official School Contest

  • Opencup Contest

  • School/University/City/Region Championship

  • Training Camp Contest

  • Official International Personal Contest

  • Training Contest

Sorry for my poor English .

Full text and comments »

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

By bluemmb, 10 years ago, In English

Hello.

I want to know, Is that REALLY necessary to be Professional in 10Fingers Typing for get Good place in the competitions ? How much that is impressive ?

Sorry for my poor English .

Full text and comments »

  • Vote: I like it
  • 0
  • Vote: I do not like it