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.
Will this round be rated?Also,7th January isn't so soon :-)
None of gym contest are rated.
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?
seriously dude? Did you even read the announcement? It's said that its in the Gym so NO its not rated.
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?
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.
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.
How do you define "wasting" ?
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.
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.
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.
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
It is team participate or single participate or both? I remember the contests in gym can be participated by team of three users
Read UPD .
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.
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. :D
P/s: You are the author of Crypto cup. Are this contest's problems crypto-style? :D
No, no. Crypto cup was just a fun contest. This is a serious one :)
Did you even ask CD stuff to hold it as a regular contest? That would be really perfect :)
Yes this would be nice.. please ask if you haven't.
What is CD ?
I think he means "codeforces staff".
Typo, meant CF
Why you don't make an official CF round?
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.
Cool if i think i won't fail the exams at that time, i will participate XD
Will it be held according to Codeforces or ICPC rules?
ICPC
I really hope that you consider the possibility of making it an official contest instead of a gym's one.
I've talked to the admins, it's impossible.Alright ?
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... :=|
I think it is good idea to make contest rated
I'm not sure; is a newbie qualified to write a Div1 + Div2 contest?
Oh man...
It's just Magic
Newbies (M.Mahdi,PrinceOfPersia) made a Contest :)
hi
i am new to programming contests. will problems be easy so that i can solve something? thx
XDDD +1
Oh ! You're too low rated. I don't think you can :)
Please try to convert this round to an official round. It is actually more interesting, I must say. :)
Hey your back to GM now!
It's so important that we will get kiss from who...
At least show a picture :D
Do you like Taylor HosseinYousefi ? :)
I rather you. :x
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???
Order by rating
But it doesn't work properly, because in Div.2, I should delete teams (in top) and high rated users (in bottom).
Why you don't close registration 5 minutes before contest?
Can we choose where (s)he will have to kiss?
Can we hack other code ?
i think u should improve ur grammer :)
Grammar*
And you need to improve your spelling :D
and of course ur = your ?! :\
deleted
It's Not a bug Its a feature !! :DD
You will be out of competition there.
I was in the register list but i am not now how come? at least add me as an alone participant please
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
Thank You XDD Sorry for the trouble
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?
I don't know, I never tested that before.
register me and Majid in div.2 too please
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.
tnx :D
what's this?
Как отрегатся ?Я хочу как индивидуальный участник участвовать
deleted.
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 ?
Чувствую если бы раунд был рейтинговым, народ бунтовал бы)
Задачи неадекватные в див2 :) Зачем их делать шесть, если уже вторая — гроб? :D
Problem A (Div 2) was really great and fun (for Iranian Computer Olympiad) :)
I need solution of problems B,C,D,E,F Div.2 ? Those are really interesting problems but so hard with me!
Will an editorial be released ? and If it is can you include your solution in it ? It will be really helpful :)
What was the desired complexity in Div1 A problem?
Who can share the solutions?
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.
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.
Here it is. But I think, it's really hard to understand this code.
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).
here is my solution to div1 A/div2 C
I think its complexity is O(N^2) but it is TLE.
can you please upload your solution for this problem ? thanks in advance :)
lcm(a, b) ≠ lcm(a(modP), b(modP)) where P = 109 + 7
Thank you ikbal for your note.
Now I know that it is not only the complexity but also the algorithm is wrong XD
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.
Problem C
Let'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 case
Code
Well i would suggest monotone queues rather than 2D sparse table.
May you please explain your idea?
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!
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
wait the solutions :'(
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?
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?
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.
Hoping to see the editorials soon.
What is the complexity of this solution? 9382172
Why you have my code ?
problemset was nice :D
you wrote that cthbst got first and second place, please fix that.
Any hint for problem Div2 B.Troynacci Query.
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.
I am new to code forces. why solutions are not public?
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
Not any yellow, you should be red or be yellow with 30+ contests.
Editorial??
Why we don't have contest now?
task F looks very intresting im wondering how it's done
You need to know Centroid Decomposition to solve F.
Problems were very interesting, but some difficult... Thanks PrinceOfPersia for you haven't spent it as a contest!
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.
Link my code.
I hope PrinceOfPersia will post tutorial soon because these problems are very interesting and difficult. Sorry for my bad English !
/