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

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

Hello, Codeforces!

I would like to invite you all to the International Coding Marathon 2017, under the banner of Technex'17, which will take place on Thursday 23rd February 2017, 20:05 IST. The contest will be held as a combined Div.1+Div.2 round which will be rated for participants from both divisions. The prizes for the event have been sponsored by D. E. Shaw & Co..

The Indian Institute of Technology (BHU) Varanasi, India is proud to present the 78th edition of its widely renowned techno-management festival, Technex'17, to be held from 24th to 26th February 2017. Offering a myriad of diverse events across fields such as programming, robotics, and aero-modelling, it witnesses enthusiastic participation from all across India and abroad.

The problemset has been prepared by me(DeshiBasara), vikhs_96, Prateek1996 and ishankarora. We would like to express our heartiest thanks to KAN for his constant help in preparing the contest and MikeMirzayanov for the amazing Codeforces and Polygon platforms. We also thank ashmelev and winger for their invaluable help in testing the problems.

UPD1: The start time of the contest has been delayed by 10 minutes.

UPD2: The scoring is 500-1000-1500-2000-2250-3000-3250.

UPD3: Thanks to all those who participated and heartiest congratulations to all the winners. The winners, who are eligible for prizes, will soon be contacted regarding the same.

Overall top 10:
1. ainta
2. tourist
3. LHiC
4. halyavin
5. jcvb
6. mnbvmar
7. uwi
8. jqdai0815
9. Syloviaely
10. Radewoosh

Indian top 5:
1. rajat1603
2. Baba
3. akulsareen
4. sampriti
5. PrashantM

Some of the problems were not up to the expectations. There were some issues with the site too. We deeply regret the inconvenience caused.

UPD4: The editorial for the round has been uploaded.

Prizes

Prizes worth INR 100,000 up for grabs!

Overall 1st place: INR 35,000. Overall 2nd place: INR 25,000. Overall 3rd place: INR 15,000.

1st place in India: INR 10,000. 2nd place in India: INR 6,000. 3rd place in India: INR 4,000.

1st place in IIT (BHU) Varanasi: INR 4,000. 1st place among IIT (BHU) Varanasi freshmen: INR 1,000

Participants will have 2 hours to solve 7 problems. The scoring distribution will be announced soon.

Good luck everyone! Hope to see you on the leaderboard.

  • Проголосовать: нравится
  • +201
  • Проголосовать: не нравится

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

Congratulations everyone on the 4th century of contests here on Codeforces :) :)

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

I thought "What is INTERNAT? Is it a typo of INTERNET?" and it took me a while to understand that it is actually "INTERNATIONAL".

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

7 problems 2 hours! Hope A B will be for all.

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

Wish ALL high rating.

:)

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

Lately there are to many contests from India. Soon codeforces will become an Indian contest webcite :)

Anyway, I hope all the red and yellow coders rating increases. All the dumb ones may suck.

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

What happens if the 1st place in India get top 3 overall? Does he get both of the prize?

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

    In such a situation, he will get the prize for top 3 overall. The India topper prize will be given to the next Indian in the ranklist.

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

Еще одна соточка) Ждем 500

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

Am I the only one who didn't know what this currency is??? And how much is it in Dollars :D

I know I won't get any prize, but I was just wondering :3

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

    The currency mentioned is INR (Indian Rupee). 1 USD = 66.98 INR (As of today) INR 35000 = 522 USD, INR 25000 = 373 USD, INR 15000 = 223 USD

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

I hope that this time we will see at least two tasks with level >=Div1C and that there will be no tasks worth 2000 points that are a good fit for Div1A :P (yes, I am regarding to last contest).

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

    IMHO problem D,E,F in last contest are good fit for div1B and are much harder than usual div1A. Maybe div1B is just as easy as div1A to red coders :D

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

    I'm a simple man. I'll be happy if the round won't become unrated because of the issues with the server.

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

    G says "do some complicated digit DP". F says "do centroid decomposition". E looked nice at first, but after you find g(n) = n it's pure implementation. Stopped reading problems here. I think the problems are fine, but it suits better for a d2-only round. I don't say the problems are too easy — F and G are time-consuming and it's hard to solve everything in 2 hours. But there should be problems that require non-trivial idea.

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

      Well, for me it is the first time when I wrote centroid decomposition. Now it is not just crazy idea that is only needed for problems that I can't solve anyway.

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

        Yes, I didn't say the problems are easy. If the purpose of this problem is to introduce centroid decomposition, shouldn't it be used in educational rounds?

      • »
        »
        »
        »
        8 лет назад, # ^ |
        Rev. 2   Проголосовать: нравится +11 Проголосовать: не нравится

        You don't need to break down by finding centroid of trees. Just the center of diameter will work as well I guess.

        Edit: Something like this: 23787939

      • »
        »
        »
        »
        8 лет назад, # ^ |
        Rev. 2   Проголосовать: нравится +13 Проголосовать: не нравится

        The centroid decomposition part of F is just Round 190 C (link: http://codeforces.me/problemset/problem/321/C)

        BTW, I don't think "center of diameter" algorithm is correct for arbitrary graph, but maybe it's correct for problem F because the polygon partition graph is somehow special.

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

      Absolutely agree, and you haven't seen D, it's the worst today, I guess (I've seen it hundreds of times).

      Actually I suddenly find these contests very useful for my training to the finals but it was definitely not interesting to solve most of the last rounds.

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

Is it Rated?

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

    The contest will be held as a combined Div.1+Div.2 round which will be rated for participants from both divisions.

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

Is this just a single event? If so, why is it called a marathon when it's just 2 hours?

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

Does anyone has GATEWAY TIMEOUT errors?

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

I hate postponing :D

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

Кфик не болей. Посылка уже тестируется минут десять.

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

I am doing contest from office , now you guys postponed it i have to go late by then :/

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

Waiting for a long time, but it is postponed. :( :(

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

Any writer's girlfriend missed the registration?

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

I have short.

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

Rating prediction for this contest could be found here (after contest begins)

Extensions:

About CF-Predictor

Good luck & high rating to everyone!

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

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

      This happened because I use free (low performance) server to calculate rating changes. Once a few minutes it does "standings request" to codeforces and then calculate prediction. So prediction always late for couple minutes. Yesterday, delay was up to 7 minutes.

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

    Gives me a wrong rank

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

Queue :(

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

Seems like Unrated Contest :(
15 minutes still no verdict! should I leave this problem or not?! Not sure it will pass :( Please Make this Unrated. So many suffered from this —

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

never ending loading...

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

Is it just me or this contest is too lag to do any hacking?

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

Is Codeforces server on AWS ? If not, then I think it's time to move on AWS.

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

I am getting long loading times as well. not sure if there is a problem with my browser or with Codeforces.

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

Can't access ɔopǝɟoɹɔǝs˙ɔoɯ

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

It has been more than 20 minutes that I cannot open any of the contest pages...

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

If You are reading my comment,i have jumped off the roof (Connection TimeOut)

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

Endless loading drove me to play hearthstone in order to keep a good mind.

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

THIS TIME WE DON'T even NEED ANY REASON TO DO CONTEST UNRATED.

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

I think after such an incident there should be a announcement clearly stating further action like extending contest time/contest being unrated/no changes . Although, its done in most cases, not yet in this one though. EDIT: It seems they heard me.xD

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

ямар аймар гацдаг юм бэ хха болилоо нтр

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

My grandma runs faster than CF.

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

They said in a clarification "It was down for only a few minutes"
Is it only me who couldn't able to access the site whole time?

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

"Extended by 10 minutes"? I had to wait more than 40 minutes to send C again, it means 250 points lost... Codeforces is a great platform but please fix that high availability.

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

The website was down for more than 20 minutes and earlier the queue was big..I submitted B for 700 but got only 500....please make this ****unrated****

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

Why is my 3rd hacking attempt still waiting while my 5th attempt has been judged? And someone else hacked that solution later and succeeded, while mine, which was earlier is still waiting.

my hack attempt: 303111

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

How come I submit for 700+ and get 600+? I suppose I'm not the only one encountering this.

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

Codeforces servers were slow for the contest.Lost lot of time because of this.

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

What a weak PP of problem C.So sad:(

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

Can anyone give a hint on how to solve D?

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

    use DSU

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

      How? I first thought DSU, but couldn't see how even and odds can be handled

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

        Of course if we only care a switch need to be toggled odd number of times or even number of times.

        If a door is locked,it means one of the switches which control it need to be toggled odd number of times while the other even.The situation that a door is unlocked is similar.

        We can check if it's ok using weighted DSU

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

          I still don't get it. We don't know which switch will be toggled how many times. For example, if door A has switch B and C, such that door A is initially closed, then B+C is odd, but we don't know whether B is odd or C is odd. How did you handle this?

          Sorry if my question is stupid, I don't know how to apply this concept with weighted dsu very well.

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

            Maybe that's because my English is really bad.

            It means when we use DSU we record the relationship of a point with its father.I don't know its name in English exactly.

            We needn't know exactly whether A or B is odd.We only need to know the sum of them is odd or even.If we need the sum is odd while we need the sum is even,the answer is NO.At any other situation,we can always get a solution to make all the door unlocked.

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

      Why does DSU work? If we're doing regular 2-SAT we have to build directed edges from >y and >x right (this is the case that the doors are locked)? But in this case DSU makes these bidirectional edges, which I assume is incorrect? It code it and it actually works for some reason, but I have no idea why.

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

    I think that it is 2sat problem. I solved it using DSU.

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

    for each room , let its 2 switches be a , b. Now if that room is off then a and b must be different else they must be same. So just make a graph and check for bipartite.

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

    If all rooms are opened then answer is YES. Else, there must be at least one room that is locked, try first switch and second switch to make this opened with something like dfs.

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

      isn't this 2^n?

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

        You should just try first room that is closed.

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

          I don't get it. so for each room that is closed, you have 2 choice. so you recursively do this. How is this not 2^n?

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

            Notice that if I have a valid solution, I can toggle all switches and the solution remains valid. So set Switch 1 to 0. This will decide the values of all switches which are connected to 1. (Using the doors as 'edges' of the graph).

            Do this for each connected component once. Complexity O(N)

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

            nvm, it is wrong. There can be multiple connected compunds:(

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

    I think 2-SAT

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

    Its basically a slightly modified version of this problem

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

Asking for answer modulo 1e9+7 when it's quite small is evil. :(

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

    Actually I didn't even check if I passed the pretest because the internet is too slow. Then I found I didn't modulo 1e9+7 when I submitted F. I left the bug there for half an hour :P

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

      Well, at least it was in the pretests

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

      I did the exactly same thing. Fortunately, I saw the line asking for modulo in less than 10 minutes after submitting (of course I couldn't see that the solution actually got WA, because 10 minutes is way to fast for one to get the score)

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

    Actually, I also was a victim of that, but I think it was necessary. Otherwise it would be strong suggestion that result is small which was probably a big hint in this problem.

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

B hack?

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

Lol ! I was hacked twice in problem C one hack for K = 1. and one hack for K = — 1 :D

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

codeforces really needs to scale up to handle more users.

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

What was pretest 4 problem D?

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

Could someone give me a hint for problem C please?

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

Steps to solve problem E:

1.f(n) = φ(n),it it obvious.

2.Open aops.com ,search for g(n) and find that g(n) = n.

3.It is obvious that φ(...φ(n)) is quickly decreasing.

That's all,find Fk(n).

Very original to combine all 3 steps, like.

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

Попробовал в D написать dsu. Объявил 4 переменные (f1, f2, g1, g2), осталось написать union(f1, g1), union(f2, g2).

Пишу union(f1, f2), union(g1, g2), блокирую. Ах да, оно проходит претесты.

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

Ужасно перевели задачу B на русский: кто бы мог подумать, что простой делитель — это делитель, являющийся простым числом, а не делитель, отличный от 1 и самого числа. Уверен, большинство русскоязычных об это споткнулись.

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

Great round, very nice problems!

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

Wanted to submit C in last 2 minutes but nevermind codeforces servers didn't wanted me to gain ratings :/

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

I was waiting for submitting B more than 30 minutes. The server was totally down. Please make it unrated. MikeMirzayanov

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

Is there any nice way to solve F?

I could see that the dual graph of the planar graph described would be a tree and that we should do centroid decomposition on it but I had no clue as to how to actually implement anything.

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

    I can probably help with implementation after converting polygon to graph. You can decompose tree using center instead of centroid using BFS-like idea (and DFS to find center). I've done something similar here: 23787939

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

    IMO, the most challenging part of this problem was building the graph (tree ;) The idea I used was:

    The most important fact I used to build this tree clean was that the id of each region is determined by the two nodes with bigger id on the border of the region.

    Put the nodes of the polygon in a line in order 1, 2, ..., n Then put the diagonals as segments on this line (u, v) (where u < v) Notice that if two segments have non zero intersection, one is completely inside the other. If we include the segment (1,n) we can say that each diagonal denotes the region that is inmediatly above it. The DIRECT including relation might be interpreted as a parent-child in a tree, Order this segments by start in increasing in order and break ties by length (in decreasing order). This order is the preorder of the tree, so you only need to rebuild the original tree from the preorder.

    The rest of the problem, is using centroid decomposition, similar problem where the tree is given can be found here on codeforces.

    My solution. 24937275

    Good luck

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

I want to hack someone in the last minute, but CF lags and forbids me to do so :( (Quite sure his solution is wrong)

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

**15 MINUTES LONG QUEUE ANF AFTER THAT 45 MINUTES OF SERVER DOWN **

** I JUST REMEMBERED PRINCIPLE OF MUTUAL EXCLUSION**

** 1 HOUR SITE RELATED PROBLEM EXISTED AND IN RETURN WE GOT 10 MINUTES._wOWO_

I JUST REMEMBERED LAW OF EQUIPARTITION OF ENERGY **
»
8 лет назад, # |
  Проголосовать: нравится -41 Проголосовать: не нравится

Let's vote: Strawpoll.

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

    Those polls always get biased results. People who are fine with the status quo will scroll past the poll while those who want the round to be unrated will vote.

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

When you missed E because of slow Internet connection... I would have a sleepless night if that solution got AC...

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

Is it just me or will unordered_map TLE on C? Somehow when I test my solution on a large case for C it doesn't seem to be able to close to running in time whereas changing it to map makes it work almost instantly. Not sure why this is happening (I didn't try to construct cases to fail unordered_map solution)

24923074 (n = 100000, k =  - 2, ai = 229)

  • »
    »
    8 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    ans+=ma[a[j]-tmp];
    

    I think first checking whether an item exists in the map could speed up as it won't store anything in map incase no such value exists.

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

    I tried to construct cases to fail unordered_map.

    Generator

    It takes about 4 seconds.

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

    That can give MLE, but I am not sure. If you want to get some element from the map, better to do if (map.find(element) != map.end()) instead of just taking map[element]

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

Ty CF. If you didn't crash I could have had F. :'(

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

It would be nice, if problemset could be loaded as pdf by clicking just one button near the button "Complete problemset". When contest lagged today, I already solved E and sent it(although forgot to make %MOD operation and knew verdict only after 20mins) and wanted to open F, but I couldn't do this for the next 20 minutes. If problemset was downloaded at the start, problem could be read during this hard laggs.

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

    You can click on Complete Problemset and then print the file to pdf.

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

I hacked one person with this test 5 8 0 0 0 0 0

He calculates all power till 50,then push them to set and forget about overflow. And i found that 8^21 = 0.

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

I accidentally resubmitted C twice instead of once due to network issue 24941488 24941490 What can I do? This is really sad.

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

Any hints on how to solve F? The only solution I thought of is build a tree and then find center of the tree, color it, remove it from the graph and recursively color the remaining set of trees but that doesn't look like an easy solution to implement.

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

    Not the center but the centroid. The other part is correct.

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

    It's F. It doesn't need to be easy to implement.

    Most of the solution is unfortunately copypasting. First, you should divide a planar graph into "walls" and then you perform centroid decomposition on it. Both functions can be copypasted from a library, if you have one. I didn't have :c

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

    My approach: Sort the walls based on their "length". Now the wall with minimum length and the boundary between two endpoints form a region. Let W denote the wall and R1 denote the region. Remove R1 and now W is a new boundary edge. Then mark R1 on W. When you finally remove some region R2 containing boundary edge W, build an edge between R1 and R2.

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

Has anyone this bug? I hope that this submission will be taken into account.

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

The problems take time but the ideas were straightforward. Maybe only E wasn't since you needed to write something down before conclusions, unlike F which was screaming "build this fkin tree and run CD".

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

There were some serious technical problems with the website in this contest.

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

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

Предлагаю сделать раунд нерейтинговым. Очень долго(час) не грузилась вкладка "отослать"

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

Why do I get TL 13 in C? (code)

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

    I've wasted more than an hour trying to pass test 13. In the end I got to know that set/hashset count works in linear time.

    Used map and everything will be fine :(

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

E — let's add a random function which is well known to be an identity function

F = http://codeforces.me/contest/321/problem/C + duality on planar graphs

great problemset...

  • »
    »
    8 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится +1 Проголосовать: не нравится

    I've finished the code for F 3 minutes after the contest ended. However, I had some trouble in building the graph (well the tree), especially because it was hard for my to determine the polygons. How did you do this part? I've hardly managed to come up with some strange recursive function and some strange disjoint data set to find out the polygons.

    Ohh and about the fact that F didn't bring anything new, let alone E, I agree. I also hated that most of the scoreboard was decided based on hacks. In my room there were 4 or 5 hacks in total. I found 3 of them by myself and CF was moving so slowly that someone else got them before I could even type the numbers...

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

      My method:

      build initial graph from i to i — 1 as well as from 1 to n

      build additional edges as input, two-wayed

      build the graph from largest valued polygon:

      first, identify the largest element that still has an edge left
      
      choose the closest edge to walk, where the distance is defined as the "non-input" edges needed to walk from u to v, i.e. u,u-1,...,v
      
      delete that edge, mark it too. (when an edge is marked twice you add it into the tree)
      
      define lastdist = dist(first vertex, second vertex)
      
      while we didn't return to largest element
      
           find the furthest vertex from itself, that does not exceed or equal n &mdash; lastdist
      
           delete the edge, do marking

      Ya and this problem is too original and standard... (and boring)

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

      I agree, hacks will play a big role in the standings. It's the sort of thing I always do when finding components in a planar graph. For every node, sort the edges by their angle. In this problem, that's just sorting them by their index.

      Now, let's say we will traverse each component in CCW order. Find a previously unused (directed) edge and then in each step choose the edge that creates the smallest directed angle with the previous one, this can be done with a simple lower_bound. When you return to the starting node, you found a component.

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

Savage of a contest

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

hogloid, I hate your -1 :D

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

I couldn't open the site for over 30 minutes. I think it should be unrated.

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

How to solve C?

  • »
    »
    8 лет назад, # ^ |
      Проголосовать: нравится +1 Проголосовать: не нравится
    let  p[] - unique power of k's ' which absolute value less than 10^15
        k = 1.  p[] = {1}
        k = -1 .  p[] = {-1, 1}
        k = 2  . p[] = {1, 2, 4, 8, ..., 2^60}
      and etc.
    
    now.  sum(i) = a[0] + a[1] + .. + a[i]
        we need number of that intervals which  a[h] + a[h+1] + ... + a[i] = k^x 
       but  a[h] + a[h+1] + ... + a[i] = sum(i) - sum(h-1)
        so  if we know sum(i)  and k^x  --> sum(h-1) = sum(i) - k^x
        need calculate number of h,  0<= h < i and sum(h-1) == sum(i) - k^x
        there assume sum(-1) = 0.
     
    let   freq[ sum(i) ] -- number of  h, where  0<=h < i,  and sum(i) == sum(h).
    
        so ans(i) = freq[ sum(i ) - power(k,x)] ,  where x >= 0 and k^x < 10^15.
        
         answer = sum(ans(i), i = 0..n-1)
       
    //let coded:
    vector<long long> p;
    if (k == 1) p.push_back(1); 
    else if (k == -1) p.push_back(1), p.push_back(-1);
    else {
       long long ky = 1;
       while( ky < (long long)1.0E+16 && ky > - (long long)1.0E+16 ){
              p.push_back(ky); ky *= k;
       }
    }
    map<long long , int> freq;
    freq[0] = 1;
    long long sum = 0, ans = 0;
    for(int i = 0; i < n; ++i){
         sum += a[i];
        for(int j = 0; j < p.size(); ++j)  ans += freq.count(sum - p[j]) ? freq[sum-p[j]] : 0 ;
    
        ++ p[ sum ] ; 
    }
    
     cout << ans << endl;
    
»
8 лет назад, # |
Rev. 3   Проголосовать: нравится +24 Проголосовать: не нравится

#FIXCF

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

How to understand F?

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

have waited for "codeforces.com/contest/776/submit" for over 30min

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

Couldn't do anything for 20 minutes after I finished F. I hadn't even read G then. Although I'm not sure if I can finish G in contest time, still feel a little bit upset :(

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

I strongly recommend to hold such a kind of contest in Div2 only...

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

My D will fail because I assumed there is only one connected component :(

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

In task C, the current winner mnbvmar has:

int s = 1;
while (abs(s) < 1e16) {
      diffs.push_back(s);
      s *= K;
    }

Looks like it's going to fail?

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

    Seems like a lot of people did miss the k = 1 or k =  - 1 case, so we could probably expect some changes in the leaderboard.

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

    you missed the first part ?

    if (abs(K) == 1) {
        diffs.push_back(K);
        if (K == -1) { diffs.push_back(1); }
      } else {
        int s = 1;
        while (abs(s) < 1e16) {
          diffs.push_back(s);
          s *= K;
        }
      }
    
    • »
      »
      »
      8 лет назад, # ^ |
        Проголосовать: нравится -13 Проголосовать: не нравится

      He is using int and multiplying by K until 1e16.

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

        You forgot this:

        #define LL long long
        #define int LL
        
        • »
          »
          »
          »
          »
          8 лет назад, # ^ |
          Rev. 2   Проголосовать: нравится -35 Проголосовать: не нравится

          This should be considered code obfuscation. Obfuscating the code just for the purpose of reducing other contestants' points for incorrect hacks.

          The reason for this, is that this define is among code which is not considered the actual solution. You should not be reading somebody's template code in order to understand the solution.

          Also if that code is considered the actual part of the solution then all the macros and functions should be used in the program. If they are not used — it means that this is unnecessary code, which makes it harder to read and understand the solution.

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

            Go away. I am sick and tired of explaining why this is huge bullshit.

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

              No it's not. Making solutions unnecessary complicated is a bad practice in general — you should have known that.

              It is also against the rules which says that there can be no more than x% of unused code. That rule is usually violated by some templated code and nobody complains about it as everybody just skips that and reads the "real" solution. If you are required to read the template code in order to understand the solution that rule should apply.

              You are explaining something which can't be explained. Not a big surprise that you are sick and tired of that. If you see the int, it should be an int. If it was some sort of custom type like INT or INT64 etc., it could be justified. Such thing at least indicates, that you should go and check that type. It is not possible to deduce that int is long long, without carefully reading the whole templated code.

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

                I care about getting ACs instead of WAs because of overflow and I don't give a single %^&* about people unsuccessfully hacking my code, I do not have any intention in misleading people (even though it may mislead somebody, but I don't care about it). End of topic.

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

                  Your intentions do not matter. What matters is % of unused code. That rule is usually relaxed by the fact that you put a bunch of templated code, which is not used in your solution.

                  I also said few times already, that changing existing type to something else, requires reading the whole source code — which does mean that your templated stuff, should be considered a core part of it. Because of that, you should reduce your template and includes only to the things which are really used in your solution.

                  Everything which is not used, should be counted against the % of not used code.

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

                  There is no such rule on CF. Haven't you seen codes with 1000 lines of template codes at last pages of sort by solution size submissions. Such a rule exist on TC.

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

            This is not code obfuscation. It is to avoid unnecessary WA caused by overflow.

            When you hack, you're supposed to know the language specific, in this case you should know that #define int lnog long is possible in C++.

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

        oh I didn't read that..

        EDIT : oh turns out it is fine....

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

    Tricky: define int LL

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

RIP solutions of Those who handled k = 1 but not k = -1 case in C.

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

After a long time there comes a contest in which i could do both A and B....Hoping to get rejected in system testing....

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

Codeforces can you please stop allowing contests from Indian Problemsetters? Especially contests with blue problemsetters...

If you really want to have these shitty contests, make them Div 2 only please.

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

    You are kidding, right? The problem was with the servers. Don't target people who were not responsible for making this contest what it was.

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

      I think he meant the problem quality was not good enough for div1 contestants.

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

    Racist...

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

      Last 2 contests have been by indian blue problemsetters, and the problem quality is utter SHIT.

      If you don't believe me go check the comments under the last contest, and you'll see I'm not wrong.

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

        You can't draw such conclusions from 2 contests. Having two shitty contests in a row is in no way justification to ban an entire country from problemsetting.

        Furthermore, I'm willing to bet that the problem has less to do with India and more to do with blue. The way those contests were set up also makes me believe they received less coordination from KAN and the Codeforces team than the average round (since they were created for some sort of festivals, not regular rounds). I might be wrong on this obviously.

        "Utter shit" is also definitely exaggerating. The problem quality was below average, but I've seen way, way worse.

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

What were you missing, people who got WA #3 on F?

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

C was given on geeks for geeks just needed minor changes, and the long queue otherwise the contest was good.

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

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

About 30 minutes I could not do anything on CodeForces :(

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

Problem G:

Why are there no sample case whose digit is more than 4? Sample case should contain "essential" case I think, and in this problem, the main part is DP on digit, but all sample cases don't require that!

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

next time you host a contest for Div1 and Div2 combined, please make sure that the site doesn't get down in the middle of the contest

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

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

Super fast System Testing. Came late but came strong...

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

I have a dream, that one day codeforces will be stable and fast

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

Please add problems to practice section.

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

Is this contest ranked? The site did not work most of the time!!!

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

TLE on test 101 in problem C :(

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

C — unordered_map: TLE. map, set: AC. seriously?

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

    yes, because element accessing complexity is linear and logarithmic respectively.

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

      I think you are not right, because how i know, unordered_map make this for constant, not linear

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

        Then what is the reason behind TLE for using unordered_map ??

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

        In the worst case — linear.

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

        No, paradox1 is correct in the worst case. unordered_map uses a hash function to determine where to store the value. On random data, you can expect that there will be not too many collisions (that is, different values that hash to the same integer) and you would expect each lookup to be (roughly) O(1). However, if there are a lot of collisions, then each lookup can be as bad as linear. Test cases can be constructed (for example, here) to try to make each lookup linear. On the other hand, map is guaranteed O(log n) in the worst case.

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

    Similar thing happened to me yesterday in a contest.

    scanf/printf: TLE

    cin/cout: AC

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

    unordered_map is not suitable for a small number of elements (which in this case is 10^5) as it works on hashing..(Probing slows it down.. due to collisions)...

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

Nice problems!

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

Can someone be generous enough to tell me how to decide whether to use normal map or unordered map ????

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

A hint for the next contests: Open all problem pages at first minute, at least you will be able to read the others problems and dont feel useless when the site crashs completely :(

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

What is WA in D on test 55, jqdai0815 also had this problem? :(

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

When you see second sample of problem A:

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

what is the solution of problem c. Thanks in advanced.

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

    I used prefix sum, and binary search.

    • »
      »
      »
      8 лет назад, # ^ |
      Rev. 2   Проголосовать: нравится +4 Проголосовать: не нравится

      Can you please tell me the idea of running binary search on prefix sum in detail.

      • »
        »
        »
        »
        8 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится
        1. calculate prefix sum in array D
        2. keep a map<long long, vector>, and for each element(E) in D, keep all indices (i) such that D[i] = E in the map[E].
        3. for the current power of k (pk), iterate through D with current index i, we have to look for D[i]+pk, because we want their differense to be pk.
        4. recall that map[d+pk] contains such indices, but we need the ones bigger than i, here the binary search comes to help.
  • »
    »
    8 лет назад, # ^ |
      Проголосовать: нравится +1 Проголосовать: не нравится

    Store all the numbers that should be found (k^0, k^1, ..., k^j) in the array (note that max number that can be found is 10^9 * 10^5 = 10^14). The size of this array is logarithmic (note that you should probbably treat k=1 and k=-1 as a special case and form the array manually).

    In order to find the ranges with sum x you can use the prefix sums. For each prefix sum p[i] you should find the amount of sums p[j] such that p[i] - p[j] = x. It can be done using a map.

    My code: link

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

Blue at last ,after a long wait .....

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

I got TLE for using unodered_map. But when I used "map" instead of "unordered_map" it passed.
with map 24943858
with unordered_map24939864
Can anyone please explain..

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

Had +17 in prev round, now -17 lmao.

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

Where is editorial?

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

"I'm fucked up,I'm black and blue"...

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

Problem:C -Mollys Chemical Hey, I am getting TLE on 13th tcase. While most of the solutions are based on similar logic. My time complexity is O(N*60*log(N)). Solution:http://codeforces.me/contest/776/submission/24941529

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

in Problem D

"You need to tell Sherlock, if there exists a way to unlock all doors at the same time."

So this doesn't mean that I need to find a way to toggle the switches so that the last move will toggle all the doors from locked to unlocked, and now they are all opened at the same time !!?

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

Wow. I waited for 20 minutes after making a submission, without being able to find out whether it got accepted or not or even read other problem statements. After that, I just went home, as it was clear the contest was going to be unrated and there's no point in waiting for Codeforces to work again. Now it turns out the contest is rated and my last submission got WA on E because I forgot the %mod operation.

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

#roadtoyellow

There's nothing really tricky in that, just add "unordered_" in C, change "sw" to "doors" in D and forget "+1" when sorting array in F :P. And before that, screw up similarly 6 previous contests.

Now I need to screw up few more contests as dreamoon_love_AA did to pretend I did everything on purpose :P.

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

    If only getting yellow is as easy from down here :(

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

    Actually I don't get it. Was wondering what you meant that adding "unordered" solves C — I used unordered map and it did not work. After reading this post (and looking on your solutions) I submitted it with normal map, and it passed... Perhaps there is some rule of thumb when use unordered_map, and when to use map? Isn't it actually a flaw of the tests? The programs should not fail due to small multiplicative constant, should they?

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

      He meant adding unordered gave him TLE — see his submissions. Also, its not multiplicative constant but O(n) worst case time for unordered map vs O(logn) for map.

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

        I know. Perhaps did not state it clearly enough. What I am asking is "Why is it so?". Appears stupid.

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

        Ah, and the complexity is constant on average and we perform many queries, so it should be faster.

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

          Complexity is constant on average in an ideal world(perfect hash functions, random data), but you can construct test-case against stl's implementation knowing the inbuilt hash function and clever test data.

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

            Ok, give me a test which makes a randomized quick-sort quadratic please...

            Anyways I believe the tasks should not be about using the correct implementation of map, but rather about a the Mathematical problem.

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

            Sorry, the difference is quite big.

            Then the question is not about the test but rather why the unordered map performs so horribly bad here?

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

      I wanted to explain how one can screw up contest in three simple steps. Adding unordered was simple trick to magically transform AC into TLE.

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

    Let's guess who will be Sorry_Swistakk.

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

Why this contest is rated? Is it because we have 10 more minutes to deal with the previous 30 minutes' trouble??

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

    Even then, it doesn't make sense. Those users who started working on a problem shortly before Codeforces stopped working, were almost completely unaffected. Whereas other users couldn't do anything during that time. 10 extra minutes for everyone won't fix the disadvantage some participants were already placed in.

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

      At this point I just try to open all the stataements asap. I mean, it doesn't excuse the lags but it helps in case they actually happen.

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

Deleted

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

D was a nice problem !!

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

Editorial??

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

Can anyone tell me why my problem C got TLE when I use unordered_map, but got accepted after I change unordered_map to map, and nothing else? Does it have constant as huge as O(logn)?????

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

    There is anti-hash test for C++ apparently. Ironically enough in Java it is the other way around, HashMap (unordered_map) is fast enough, and TreeMap (map) is too slow.

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

How to prove that phi(phi(...(phi(n))) will become 1 fast enough?

  • »
    »
    8 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится +26 Проголосовать: не нравится

    If n can be divided by 2, then we have phi(n)<=n/2, otherwise we will find phi(n) be divded by 2 if n>1.

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

    phi(even) number is atmost half of it. so in 2 steps a number decreases by atleast half of itself. there you go.. O(log N). EDIT : I did not see the others comment before me :P

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

    Note that, for n>2, phi(n) is always even. So, after the first step we will always have even numbers (except the last 1). For even numbers, phi(n)<=n/2 (because all even numbers below n are not coprime with n). So, at every step phi(n) reduces by at least half, which leads to log(n) time.

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

    Thanks guys, I've got it. Sorry for such a stupid question :)

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

D is almost the same as this one if we consider switches as nodes and doors as edges.

And in F, the coloring part is exactly the same as this one.

Such old ideas can hardly surprise me :(

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

    In problem F it wasn't trivial to come up with an easy implementation to build the tree. The coloring part is common by now, therefore I think the complexity wasn't so low.

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

    If somebody wants link for similar to D one where they can submit themselves, this is link.

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

B:failed system test on test 4 ... does the pretest have only 3 test cases?:||

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

The harder version of problem E was already used on Codeforces in our with riadwaw contest: http://codeforces.me/contest/396/problem/E. (One can say that today's E had a different idea, but no, it does not have an idea).

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

I think we should avoid problems with output Yes/No and small number of pretests. I saw really mad solutions in my room. To be honest they were completely bonkers and those solutions passed pretests. Unfortunately I didn't have the courage to hack them. For me they were equivalent to:

(rand()&1) ? puts("Yes") : puts("No").

On the other hand my solution in which I used n instead of m in one place passed pretests too, which costs me many points.

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

Could anyone explain solution of problem D?

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

How to get Prizes? I didn't receive any message.