PrinceOfPersia's blog

Hello 2015 Contest
By PrinceOfPersia, 9 years ago, In English

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

3.kraskevich

4.tourist

5.dreamoon_love_AA

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)
  • Vote: I like it
  • +157
  • Vote: I do not like it

Comments Comments (104)
| Write comment?
»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Will this round be rated?Also,7th January isn't so soon :-)

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

    None of gym contest are rated.

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

      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?

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

    seriously dude? Did you even read the announcement? It's said that its in the Gym so NO its not rated.

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

      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?

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

        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.

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

          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.

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

            How do you define "wasting" ?

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

              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.

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

              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.

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

                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.

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

          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

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

It is team participate or single participate or both? I remember the contests in gym can be participated by team of three users

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

    Read UPD .

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

      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.

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

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

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

Did you even ask CD stuff to hold it as a regular contest? That would be really perfect :)

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

Why you don't make an official CF round?

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

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.

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

Cool if i think i won't fail the exams at that time, i will participate XD

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

Will it be held according to Codeforces or ICPC rules?

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

I really hope that you consider the possibility of making it an official contest instead of a gym's one.

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

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... :=|

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

I'm not sure; is a newbie qualified to write a Div1 + Div2 contest?

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

Newbies (M.Mahdi,PrinceOfPersia) made a Contest :)

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

hi

i am new to programming contests. will problems be easy so that i can solve something? thx

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

Please try to convert this round to an official round. It is actually more interesting, I must say. :)

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

Hey your back to GM now!

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

It's so important that we will get kiss from who...

At least show a picture :D

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

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???

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

Can we choose where (s)he will have to kiss?

→ Reply
»
9 years ago, # |
← Rev. 3   Vote: I like it -27 Vote: I do not like it

Can we hack other code ?

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

deleted

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

I was in the register list but i am not now how come? at least add me as an alone participant please

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

    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

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

      Thank You XDD Sorry for the trouble

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

        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?

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

      register me and Majid in div.2 too please

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

        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.

        → Reply
»
9 years ago, # |
← Rev. 4   Vote: I like it -23 Vote: I do not like it

what's this?

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

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 ?

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

Problem A (Div 2) was really great and fun (for Iranian Computer Olympiad) :)

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

I need solution of problems B,C,D,E,F Div.2 ? Those are really interesting problems but so hard with me!

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

Will an editorial be released ? and If it is can you include your solution in it ? It will be really helpful :)

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

What was the desired complexity in Div1 A problem?

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

Who can share the solutions?

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

    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.

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

      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.

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

      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).

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

      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 :)

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

        lcm(a, b) ≠ lcm(a(modP), b(modP)) where P = 109 + 7

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

          Thank you ikbal for your note.

          Now I know that it is not only the complexity but also the algorithm is wrong XD

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

      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.

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

    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

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

      Well i would suggest monotone queues rather than 2D sparse table.

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

        May you please explain your idea?

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

          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!

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

    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

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

wait the solutions :'(

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

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?

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

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?

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

    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.

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

Hoping to see the editorials soon.

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

What is the complexity of this solution? 9382172

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

problemset was nice :D

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

you wrote that cthbst got first and second place, please fix that.

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

Any hint for problem Div2 B.Troynacci Query.

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

    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.

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

I am new to code forces. why solutions are not public?

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

    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

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

      Not any yellow, you should be red or be yellow with 30+ contests.

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

Editorial??

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

Why we don't have contest now?

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

task F looks very intresting im wondering how it's done

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

    You need to know Centroid Decomposition to solve F.

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

Problems were very interesting, but some difficult... Thanks PrinceOfPersia for you haven't spent it as a contest!

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

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 !

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

/

→ Reply