Блог пользователя PrinceOfPersia

Автор PrinceOfPersia, 10 лет назад, По-английски

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.

Анонс Hello 2015 (Div.1)
  • Проголосовать: нравится
  • +157
  • Проголосовать: не нравится

»
10 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

  • »
    »
    10 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    None of gym contest are rated.

    • »
      »
      »
      10 лет назад, # ^ |
      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?

  • »
    »
    10 лет назад, # ^ |
      Проголосовать: нравится +5 Проголосовать: не нравится

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

    • »
      »
      »
      10 лет назад, # ^ |
        Проголосовать: нравится +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?

      • »
        »
        »
        »
        10 лет назад, # ^ |
          Проголосовать: нравится 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.

        • »
          »
          »
          »
          »
          10 лет назад, # ^ |
            Проголосовать: нравится +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.

          • »
            »
            »
            »
            »
            »
            10 лет назад, # ^ |
              Проголосовать: нравится -12 Проголосовать: не нравится

            How do you define "wasting" ?

            • »
              »
              »
              »
              »
              »
              »
              10 лет назад, # ^ |
                Проголосовать: нравится +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.

            • »
              »
              »
              »
              »
              »
              »
              10 лет назад, # ^ |
              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.

              • »
                »
                »
                »
                »
                »
                »
                »
                10 лет назад, # ^ |
                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.

        • »
          »
          »
          »
          »
          10 лет назад, # ^ |
            Проголосовать: нравится -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

»
10 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
10 лет назад, # |
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. :D

P/s: You are the author of Crypto cup. Are this contest's problems crypto-style? :D

»
10 лет назад, # |
  Проголосовать: нравится -7 Проголосовать: не нравится

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

»
10 лет назад, # |
  Проголосовать: нравится +34 Проголосовать: не нравится

Why you don't make an official CF round?

»
10 лет назад, # |
  Проголосовать: нравится +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.

»
10 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
10 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Will it be held according to Codeforces or ICPC rules?

»
10 лет назад, # |
  Проголосовать: нравится +5 Проголосовать: не нравится

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

»
10 лет назад, # |
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... :=|

»
10 лет назад, # |
  Проголосовать: нравится +16 Проголосовать: не нравится

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

»
10 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
10 лет назад, # |
  Проголосовать: нравится +72 Проголосовать: не нравится

hi

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

»
10 лет назад, # |
  Проголосовать: нравится -7 Проголосовать: не нравится

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

»
10 лет назад, # |
  Проголосовать: нравится -13 Проголосовать: не нравится

Hey your back to GM now!

»
10 лет назад, # |
  Проголосовать: нравится +7 Проголосовать: не нравится

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

At least show a picture :D

»
10 лет назад, # |
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???

»
10 лет назад, # |
  Проголосовать: нравится +4 Проголосовать: не нравится

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

»
10 лет назад, # |
Rev. 3   Проголосовать: нравится -27 Проголосовать: не нравится

Can we hack other code ?

»
10 лет назад, # |
Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится

deleted

»
10 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
10 лет назад, # |
Rev. 4   Проголосовать: нравится -23 Проголосовать: не нравится

what's this?

»
10 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Как отрегатся ?Я хочу как индивидуальный участник участвовать

»
10 лет назад, # |
  Проголосовать: нравится 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 ?

»
10 лет назад, # |
  Проголосовать: нравится +4 Проголосовать: не нравится

Чувствую если бы раунд был рейтинговым, народ бунтовал бы)

»
10 лет назад, # |
  Проголосовать: нравится +6 Проголосовать: не нравится

Задачи неадекватные в див2 :) Зачем их делать шесть, если уже вторая — гроб? :D

»
10 лет назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

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

»
10 лет назад, # |
  Проголосовать: нравится +8 Проголосовать: не нравится

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

»
10 лет назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

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

»
10 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

What was the desired complexity in Div1 A problem?

»
10 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Who can share the solutions?

  • »
    »
    10 лет назад, # ^ |
      Проголосовать: нравится +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.

    • »
      »
      »
      10 лет назад, # ^ |
        Проголосовать: нравится 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.

    • »
      »
      »
      10 лет назад, # ^ |
      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).

    • »
      »
      »
      10 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

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

      • »
        »
        »
        »
        10 лет назад, # ^ |
          Проголосовать: нравится +3 Проголосовать: не нравится

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

    • »
      »
      »
      10 лет назад, # ^ |
        Проголосовать: нравится 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.

  • »
    »
    10 лет назад, # ^ |
      Проголосовать: нравится +9 Проголосовать: не нравится

    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

    • »
      »
      »
      10 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

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

      • »
        »
        »
        »
        10 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        May you please explain your idea?

        • »
          »
          »
          »
          »
          10 лет назад, # ^ |
          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!

  • »
    »
    10 лет назад, # ^ |
      Проголосовать: нравится +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

»
10 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

wait the solutions :'(

»
10 лет назад, # |
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?

»
10 лет назад, # |
  Проголосовать: нравится -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?

  • »
    »
    10 лет назад, # ^ |
      Проголосовать: нравится +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.

»
10 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Hoping to see the editorials soon.

»
10 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

What is the complexity of this solution? 9382172

»
10 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

problemset was nice :D

»
10 лет назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

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

»
10 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Any hint for problem Div2 B.Troynacci Query.

  • »
    »
    10 лет назад, # ^ |
    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.

»
10 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

  • »
    »
    10 лет назад, # ^ |
      Проголосовать: нравится 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

»
10 лет назад, # |
  Проголосовать: нравится +5 Проголосовать: не нравится

Editorial??

»
10 лет назад, # |
  Проголосовать: нравится +2 Проголосовать: не нравится

Why we don't have contest now?

»
10 лет назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

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

»
10 лет назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

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

»
10 лет назад, # |
  Проголосовать: нравится 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.

Link my code.

I hope PrinceOfPersia will post tutorial soon because these problems are very interesting and difficult. Sorry for my bad English !

»
10 лет назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

/