### PrinceOfPersia's blog

By PrinceOfPersia, 7 years ago,

Hey everbody.

Hello 2015 is a Div.1 + Div.2 contest that will be held in gym soon. As I said, there will be 2 divisions and in each divisions, users of that division can participate ( ( - ∞, 1699] and [1700, 9999]). So, anybody who participates in the wrong division will be out of competition (manually).

Duration is 3 hours and there will be 6 problems in each division. Last 4 problems of Div.2 will be same as first 4 problems of Div.1 . Problems are written by me (PrinceOfPersia) and tester's M.Mahdi.

The problems will be sorted according to the estimated order of difficulty according to my opinion but I strongly recommend you to read all of the problems.(sentence from matrix :D).

Problems are more Olympiad style than ACM. I hope you enjoy them.

It takes a while to prepare all problems. So, this contest is not in the gym contests list yet.

Oh, I almost forgot this : the main character of all problems will be my friend, De Prezer :)

UPD: Problems are designed for single participant (as mathlover said), so teams will participate out of competition too.

UPD2: It's in the gym contests list now.

UPD3: For making the contest more interesting, the winner of each division, gets a kiss ;)

UPD4: Round was delayed by 10 minutes for some technical reasons.

UPD5: Contest is over.

Congratulation to all winers specially sankear who solved all Div.1 problems.

Div.1 winners :

1.sankear

2.ikbal

4.tourist

Div.2 winners :

1.cthbst

2.peterpan

3.que_roin

Now it's time to sankear and cthbst kiss each other ;)

See you in next rounds, good luck and have fun.

UPD6: Well, recently I'm a little busy and I'll just post some keywords and tags but maybe I'll write an editorial some time.

Div.2 A : Binary search, B : Partial sum

Div.1 A : Binary search, B : Dijkstra, C : DP,Two pointers,queue, D : 2-sat, E: Hash, Segment tree, F : Divide and Conquer.

UPD7: You can find the editorial here.

Announcement of Hello 2015 (Div.1)

• +157

 » 7 years ago, # |   0 Will this round be rated?Also,7th January isn't so soon :-)
•  » » 7 years ago, # ^ |   0 None of gym contest are rated.
•  » » » 7 years ago, # ^ | ← Rev. 2 →   +5 And also you can join in all of the Gym's contests as a team...So can i ask why this contests is like this?
•  » » » 7 years ago, # ^ |   0 Not yet
•  » » 7 years ago, # ^ |   +5 seriously dude? Did you even read the announcement? It's said that its in the Gym so NO its not rated.
•  » » » 7 years ago, # ^ |   +5 One thing,many cometitons moved from Gym to official contest.I think maybe that is plan.Second why we have 2 division when the rating isn't important? I love contests and I certainly take part in this,but many people want rating.We have problems,platform,why we don't have rating?
•  » » » » 7 years ago, # ^ |   0 Firstly, this is in 2 divisions because at first I wrote 6 problems and then realized that they are hard for Div.2 users, then I wrote div.2 A and B and separated Div.1 and Div.2 users.Secondly, it's not an official contest because Zlobober and codeforces team are busy for Goodbye 2014 and other contests in beginning of 2015 and also I should waste too much time talking too them and my school main exams has begun so, I don't have that time.
•  » » » » » 7 years ago, # ^ |   +174 In my opinion, you will waste your problems publishing them in Gym. Better wait until you pass exams, talk to Codeforces team and prepare real Div1+Div2 contest — it will attract much more people and will be much more fun.
•  » » » » » » 7 years ago, # ^ |   -12 How do you define "wasting" ?
•  » » » » » » » 7 years ago, # ^ |   +117 You put some efforts into preparing problems but there will be few people who will appreciate this — you should admit that real Codeforces round attract several times more people than Gym contests and there's a reason for that — they're usually better prepared, contain less errors, have more balanced and various problem set, have possiblity to hack solutions and the most important — they are OFFICIAL. I like solving problems but I also care about rating — so contests without rating are less interesting for me as well as for many people.
•  » » » » » » » 7 years ago, # ^ | ← Rev. 2 →   +31 And don't forget that people might easily miss your contest because there will be no 'Next contest' sign on the main page, I think most of the people do not track gym contests, so your audience is limited to those who seen this blog post or those who use some contest aggregating site which shows Gym contests as well. Another point is that your contest being unrated also won't help in getting more people involved. Third point is that being prepared by you and put in Gym you probably won't bother translating it to Russian, even less people will participate. So I would agree that it some just another way of wasting your time, I liked your Crypto contest in the gym, and it seems that you spend a good amount of time preparing it, but I really doubt there will be a big crowd joining gym contest and it's usually more fun to solve problems when there are more people participating, assuming CF can handle that number of people :) . If the only reason you put it in gym is that you can't spend your time now communicating with CF team, then I would encourage you to wait a bit a longer but prepare an official round instead of the gym one.
•  » » » » » » » » 7 years ago, # ^ | ← Rev. 2 →   0 But this blog will be on the home page before the round starts, and anybody who pays attention to the home page, will see this.Besides, I'm already preparing an official one and I just wanted to prepare an unofficial one.And in other hands, this contest's problems are in such a way that are not like problems of usual rounds (you will see). So, if I even wanted to, I couldn't.
•  » » » » » 7 years ago, # ^ |   -18 Then, why didn't you fix it later?Couldn't you just host the round 2 months later when Zloober would be available for helping you?The idea of a good contest sounds better than the idea of a "Hello 2015", not so nice contest.a
 » 7 years ago, # |   0 It is team participate or single participate or both? I remember the contests in gym can be participated by team of three users
•  » » 7 years ago, # ^ | ← Rev. 2 →   0 Read UPD .
•  » » » 7 years ago, # ^ |   +5 OK. That is to say, the problems are designed for single participant. What an excellent to begin a year by participate a contest! I hope I have no exams on that day.
 » 7 years ago, # | ← Rev. 2 →   -13 This contest takes place on Jan 7th, and on Jan 8th my country's national olympiad of informatics will be held. Hmmm. I'm thinking about I should participate on this contest or not. :DP/s: You are the author of Crypto cup. Are this contest's problems crypto-style? :D
•  » » 7 years ago, # ^ |   0 No, no. Crypto cup was just a fun contest. This is a serious one :)
•  » » » 7 years ago, # ^ |   0 Not yet
 » 7 years ago, # |   -7 Did you even ask CD stuff to hold it as a regular contest? That would be really perfect :)
•  » » 7 years ago, # ^ |   +1 Yes this would be nice.. please ask if you haven't.
•  » » 7 years ago, # ^ |   0 What is CD ?
•  » » » 7 years ago, # ^ |   +10 I think he means "codeforces staff".
•  » » » 7 years ago, # ^ |   0 Typo, meant CF
 » 7 years ago, # |   +34 Why you don't make an official CF round?
•  » » 7 years ago, # ^ |   0 Yes. I think so. It could be better if you have made it official.
 » 7 years ago, # |   +4 In my opinion, I think this contest should be rated to attract more participant.If it can do, it is very helpful for me to prepare VO-contest will be held in my country on the following day.
 » 7 years ago, # |   0 Cool if i think i won't fail the exams at that time, i will participate XD
 » 7 years ago, # |   0 Will it be held according to Codeforces or ICPC rules?
•  » » 7 years ago, # ^ |   +16 ICPC
 » 7 years ago, # |   +5 I really hope that you consider the possibility of making it an official contest instead of a gym's one.
•  » » 7 years ago, # ^ |   +6 I've talked to the admins, it's impossible.Alright ?
 » 7 years ago, # | ← Rev. 2 →   0 Why you decided to make this contest unrated?You could have made us happier by make this rated...And also i just missed the Good Bye 2014 contest :(I need this contest now... :=|
•  » » 7 years ago, # ^ |   0 I think it is good idea to make contest rated
 » 7 years ago, # |   +16 I'm not sure; is a newbie qualified to write a Div1 + Div2 contest?
•  » » 7 years ago, # ^ |   +14 Oh man...It's just Magic
 » 7 years ago, # |   0 Newbies (M.Mahdi,PrinceOfPersia) made a Contest :)
 » 7 years ago, # |   +72 hii am new to programming contests. will problems be easy so that i can solve something? thx
•  » » 7 years ago, # ^ |   -8 XDDD +1
•  » » 7 years ago, # ^ |   +18 Oh ! You're too low rated. I don't think you can :)
 » 7 years ago, # |   -7 Please try to convert this round to an official round. It is actually more interesting, I must say. :)
 » 7 years ago, # |   -13 Hey your back to GM now!
 » 7 years ago, # |   +7 It's so important that we will get kiss from who...At least show a picture :D
•  » » 7 years ago, # ^ |   +7 Do you like Taylor HosseinYousefi ? :)
•  » » » 7 years ago, # ^ |   +22 I rather you. :x
 » 7 years ago, # | ← Rev. 2 →   0 I have a question...By this fake colors how do you understand a person under 1700 joined in div.1?? or Conversely...You will check all of ratings???
•  » » 7 years ago, # ^ |   0
•  » » » 7 years ago, # ^ |   0 But it doesn't work properly, because in Div.2, I should delete teams (in top) and high rated users (in bottom).
•  » » » » 7 years ago, # ^ |   0 Why you don't close registration 5 minutes before contest?
 » 7 years ago, # |   +4 Can we choose where (s)he will have to kiss?
 » 7 years ago, # | ← Rev. 3 →   -27 Can we hack other code ?
•  » » 7 years ago, # ^ |   -21 i think u should improve ur grammer :)
•  » » » 7 years ago, # ^ |   +22 Grammar*
•  » » » 7 years ago, # ^ |   +4 And you need to improve your spelling :D
•  » » » » 7 years ago, # ^ |   0 and of course ur = your ?! :\
 » 7 years ago, # | ← Rev. 3 →   0 deleted
•  » » 7 years ago, # ^ |   +16 It's Not a bug Its a feature !! :DD
•  » » 7 years ago, # ^ |   0 You will be out of competition there.
 » 7 years ago, # |   0 I was in the register list but i am not now how come? at least add me as an alone participant please
•  » » 7 years ago, # ^ | ← Rev. 2 →   +8 If you knew you can't participate as a team officially and you wanted to participate officially, you shouldn't register as a team, but I registered you and your friend ArrayAdvance :D
•  » » » 7 years ago, # ^ |   0 Thank You XDD Sorry for the trouble
•  » » » » 7 years ago, # ^ |   0 I want be out of the competition,will my name be on div 2 list if I solve some problem?Will I have some symbol beside my nick like is only div 2 competitions?
•  » » » » » 7 years ago, # ^ |   0 I don't know, I never tested that before.
•  » » » 7 years ago, # ^ |   0 register me and Majid in div.2 too please
•  » » » » 7 years ago, # ^ |   0 Alright, but this is the last time I do this. Read the comments and don't register as a team if you want to participate officially.
•  » » » » » 7 years ago, # ^ |   0 tnx :D
 » 7 years ago, # | ← Rev. 4 →   -23 what's this?
 » 7 years ago, # |   0 A team including me is registered but when I try to submit it says: "You should be registered". I know that teams are out of competition but shouldn't we be able to submit ?
 » 7 years ago, # | ← Rev. 2 →   0 Problem A (Div 2) was really great and fun (for Iranian Computer Olympiad) :)
 » 7 years ago, # |   +8 I need solution of problems B,C,D,E,F Div.2 ? Those are really interesting problems but so hard with me!
 » 7 years ago, # |   +1 Will an editorial be released ? and If it is can you include your solution in it ? It will be really helpful :)
 » 7 years ago, # |   0 What was the desired complexity in Div1 A problem?
 » 7 years ago, # |   0 Who can share the solutions?
•  » » 7 years ago, # ^ |   +20 Problem B (div1)It's solvable using Dijkstra's algorithm. For each vertex just keep two minimum-length paths p1 and p2, such as the color of the last edge in p1 is different from the color of the last edge in p2.Problem E(div1)Problem is solvable using hashes. Let's call our input string s1. Let s2 be equal to reverse(s1). Consider we don't have operation of the first type. In this case we can calculate the hashes of all prefixes of s1 and s2. For each query we can run binary search by the answer and just compare, if our original substring is equal to it's reverse version. But unfortunately we have queries of the first type. To handle those queries we should keep our hashes in the BIT/segment tree/etc.Problem A(div1)My solution has complexity O(N^2). I calculated all the LCM's, but with a lot of optimizations. I can upload my code somewhere if you want me to.
•  » » » 7 years ago, # ^ |   0 It would be great if you could upload your code somewhere. I had O(n^2 *P), where P is number of prime numbers <=max A_i (here P=17), but got TLE all the time.
•  » » » » 7 years ago, # ^ |   +5 Here it is. But I think, it's really hard to understand this code.
•  » » » 7 years ago, # ^ | ← Rev. 4 →   +8 In the problem A, it is rather easy to make it 60 * 60 * N(or even N * 60 * log 60) instead of O(N^2). Let's fix the first element. Let's imagine that we are iterating over the tail of the array. LCM can change only when a new number appears. There are at most 60 different numbers in the array. If we precompute the next occurrence of each number for each position, we can jump to the next "interesting" number quickly(doing about 60(or log 60) operations). LCM is recalculated at most 60 * N times, so this solution easily gets AC(even with BigInteger in Java).
•  » » » 7 years ago, # ^ |   0 here is my solution to div1 A/div2 CI think its complexity is O(N^2) but it is TLE.can you please upload your solution for this problem ? thanks in advance :)
•  » » » » 7 years ago, # ^ |   +3 lcm(a, b) ≠ lcm(a(modP), b(modP)) where P = 109 + 7
•  » » » » » 7 years ago, # ^ |   0 Thank you ikbal for your note.Now I know that it is not only the complexity but also the algorithm is wrong XD
•  » » » 7 years ago, # ^ |   0 In Problem A(div1), we can optimize O(n^2) solution to O(60*n*logn) solution by segment tree. Because in O(n^2) solution, when we search from each position to the last, we only need to search at most 60 positions but not n positions.
•  » » 7 years ago, # ^ |   +9 Problem CLet's fix the the top left vertex of the rectangle (some cell i;j). Now let's iterate through it's possible left sides. Suppose the for some index of the left side (let's call it l) we know, that all rectangles with down sides from i to d, inclusive are good rectangles (with the property, that difference between it's maximum and minimum values is less than or equal to k). It's easy to see, that when l increases, d decreases or stays the same. So we can use two pointers. The last step — we must be able to quickly find the maximum and minimum in the subrectangle. This task is solvable using 2D sparse table. The complexity is O(N * M * (N + M)) per test caseCode
•  » » » 7 years ago, # ^ |   0 Well i would suggest monotone queues rather than 2D sparse table.
•  » » » » 7 years ago, # ^ |   0 May you please explain your idea?
•  » » » » » 7 years ago, # ^ | ← Rev. 3 →   0 Choose two columns L and R. Then calculate rectangles which has L as left column and R as right column. Then use two pointers while sweeping over rows. It's obvious that max-min is always increasing while our set is extending. To calculate min and max, only two monotone queues are enough!
•  » » 7 years ago, # ^ |   +8 Problem D (div1)Let's denote by Ci the operation of changing row i, and Cj the operation of changing row j.When we get new information, if the numbers of matrices differ, we must either change the value of that column or that row (but not both), and if they are equal, we must change both column and row or change none.For the first we have (Ci or Cj) and ¬(Ci and Cj) (Ci or Cj) and (¬ Ci or ¬ Cj) (using De Morgan's law )For the second we have (Ci and Cj) and (¬ Ci or ¬ Cj), but this is equivalent to Ci Cj which is equivalent to (Ci Cj) and (Cj Ci).Also, any implication can be turned into a disjunction, so we end up with a 2-CNF, given two matrices we have to respect these constraints for the answer to be Yes. We can check whether a 2-sat instance is satisfiable in linear time (check here)Finally, let's observe that if at any moment the answer is No, from that point on the answer will always be No (as we are dealing with a subset of matrices whose answer to the problem is No). So we'll try to binary search the first No, print Yes before that and No afterwards.Overral complexity is O(nlogn)lousy implementation here
 » 7 years ago, # |   0 wait the solutions :'(
 » 7 years ago, # | ← Rev. 2 →   0 B, Div2 (Sorry for bad English) How I tried to solve it? Firstly I precalculated F. Then built segment tree, and in each query I wrote the interval in vertex. And then for each i calculated Ai. I Have WA2 because I forgot % operation (826 ms). But when I added it, I've got TLE. How it possible, that 10^5 mod operations perfomed for > 174 ms?
 » 7 years ago, # |   -8 I think hardness of Div.2 problems was more than usual. How ever participating in an unrated is not motivating enough. I did know how to solve Div.2 B but I wasn't in the mood of coding it.As I can see, there is another contest of yours in a few weeks which gonna be held in gym. Don't you think it's gonna be a better contest if it'll be rated?
•  » » 7 years ago, # ^ |   +1 No, because that's really a different contest (like Crypto cup or surprise language rounds) and you should work with the language I'll say(for each problem). I'll post a blog about it soon.
 » 7 years ago, # |   0 Hoping to see the editorials soon.
 » 7 years ago, # |   0 What is the complexity of this solution? 9382172
•  » » 7 years ago, # ^ |   +4 Why you have my code ?
 » 7 years ago, # |   0 problemset was nice :D
 » 7 years ago, # |   +1 you wrote that cthbst got first and second place, please fix that.
 » 7 years ago, # |   0 Any hint for problem Div2 B.Troynacci Query.
•  » » 7 years ago, # ^ | ← Rev. 4 →   0 Look the problem E and editorial from DIV2 Codeforces Round FF. The editorial didn't help me as much as the explanation by Xellos in the comments. Look how he solved it with matrices.EDIT: I'm sorry. There's an easier solution (doesn't uses segment tree) i'm trying to understand now.
 » 7 years ago, # |   0 I am new to code forces. why solutions are not public?
•  » » 7 years ago, # ^ |   0 In Gym contests you can't see the solutions for any problem you haven't solve yet but if you have high rating like master("Yellow") or more you can see the solutions :D
•  » » » 7 years ago, # ^ |   +6 Not any yellow, you should be red or be yellow with 30+ contests.
 » 7 years ago, # |   +5 Editorial??
 » 7 years ago, # |   +2 Why we don't have contest now?
 » 7 years ago, # |   +1 task F looks very intresting im wondering how it's done
•  » » 7 years ago, # ^ |   +1 You need to know Centroid Decomposition to solve F.
 » 7 years ago, # |   +1 Problems were very interesting, but some difficult... Thanks PrinceOfPersia for you haven't spent it as a contest!
 » 7 years ago, # |   0 Problem D. Div 2 , I use Dijkstra to find the shortest path from s to n vertices, but I don't AC. I use priority_queue in C++; d[u] is the shortest path from s to u. When update d[u], I check the color is different. If d[u] = oo then d[u] = -1. I checked some tests but it run ok. I hope PrinceOfPersia will post tutorial soon because these problems are very interesting and difficult. Sorry for my bad English !
 » 7 years ago, # |   0 thanks
 » 7 years ago, # | ← Rev. 2 →   0 /