text:
Neural architecture search with reinforcement learning Zoph & Le, ICLR’17

Earlier this year we looked at ‘Large scale evolution of image classifiers‘ which used an evolutionary algorithm to guide a search for the best network architectures. In today’s paper, Zoph & Le also demonstrate that learning network architectures (and also in their case recurrent cell designs) can be stunningly effective. Stunningly effective as in very close to the state of the art on the CIFAR-10 dataset (and 0.09% better and 1.05x faster than the previous state of the art using a similar architectural scheme), and exceeding the current state-of-the-art on Penn Treebank, having composed a novel recurrent cell that outperforms the widely-used LSTM cell!

Not that long ago architectures were comparatively straightforward, and a lot of effort went into feature design. At that time we might have said, “although it has become easier, designing features still requires a lot of expert knowledge and takes ample time.” As we learned to learn features this ceased to be the case and, a paradigm shift from feature designing to architecture designing took place.

Although it has become easier, designing architectures still requires a lot of expert knowledge and takes ample time.

Are now we at the very beginning of a paradigm shift from architecture design to architecture learning? If you’ve got the computational budget (about 15,000x more expensive in terms of compute!), these early results suggest you can get world class results. What kind of budget do you need to get world class deep learning experts working on your problem? And will the search time (and hence cost) come down as we get smarter at searching for architectures? How about a Bayesian Optimisation approach for example?

Here’s Neural Architecture Search in a nutshell:

Our work is based on the observation that the structure and connectivity of a neural network can be typically specified by a variable-length string. It is therefore possible to use a recurrent network – the controller – to generate such a string. Training the network specified by the string – the “child network” – on the real data will result in an accuracy on a validation set. Using this accuracy as the reward signal, we can compute the policy gradient to update the controller. As a result, in the next iteration, the controller will give higher probabilities to architectures that receive high accuracies. In other words, the controller will learn to improve its search over time.

Let’s look in turn at how Neural Architecture Search generates network architectures, how it trains the controller, and how it speeds up training through parallel evaluation of multiple architectures in mini-batches.

### Generating network architectures

Let’s begin by looking at how we can generate networks with only convolutional layers, and then build up to more sophisticated architectures. The controller that generates networks is implemented as a recurrent neural network.

#### Convolutional layers

Let’s suppose we would like to predict feedforward neural networks with only convolutional layers, we can use the controller to generate their hyperparameters as a sequence of tokens:

The number of layers in the generated architectures is controlled, and increases as training (of the controller) progresses.

#### Skip layers, pooling etc..

A set-selection type attention mechanism is used to predict skip connections.

At layer N, we add an anchor point which has N-1 content-based sigmoids to indicate the previous layers that need to be connected. Each sigmoid is a function of the current hidden state of the controller and the previous hidden states of the previous N-1 anchor points.

The controller samples from the sigmoids to decide what previous layers to be used as inputs to the current layer.

We can go further than just skip layers too:

It is possible to add learning rate as one of the predictions. Additionally, it is also possible to predict pooling, local contrast normalization, and batchnorm in the architectures. To be able to add more types of layers, we need to add an additional step in the controller RNN to predict the layer type, then other hyperparameters associated with it.

#### Recurrent cells

This is my favourite part! The controller is also set up to be able to generate novel recurrent cell designs.

The computations for basic RNN and LSTM cells can be generalized as a tree of steps that take $x_t$ and $h_{t-1}$ as inputs and produce $h_t$ as the final output. The controller RNN needs to label each node in the tree with a combination method (addition, elementwise multiplication, etc.) and an activation function (tanh, sigmoid, etc.) to merge two inputs and produce one output.

Two outputs are fed as inputs to the next node in the tree. There are also cell variables $c_{t-1}$ and $c_t$ to represent the memory states. The controller RNN predicts what nodes in the tree to connect these too.

### Training the controller

Once the controller RNN finishes generating an architecture, a neural network with this architecture is built and trained. At convergence, the accuracy of the network on a held-out validation set is recorded. The parameters of the controller RNN, $\theta_{c}$ are then optimized to maximize the expected validation accuracy of the proposed architectures.

If we view the list of tokens predicted by the controller as a list of actions to design an architecture for a child network, then we can cast training as a reinforcement learning problem. The accuracy R that a trained child achieves is used as the reward signal to train the controller. The controller seeks to maximise the expected value of the reward. Since the reward signal is non-differentiable, a policy gradient method is used to update $\theta_{c}$ – in this case the REINFORCE rule (Williams 1992).

The update is given by

Where m is the number of different architectures that the controller samples in one batch and T is the number of hyperparameters the controller must predict to design an architecture. b is a baseline function (exponential moving average of the previous architecture accuracies) employed to reduce variance.

### Accelerating training

As training a child network can take hours, we use distributed training and asynchronous parameter updates in order to speed up the learning process of the controller.

A parameter server of S shards stores shared parameters for K controller replicas. Each replica samples m different child architectures that are trained in parallel. Weights are updates across all controller replicas at the end of each batch.

### Experiments with CIFAR-10

Our search space consists of convolutional architectures, with rectified linear units as non-linearities, batch normalization, and skip connections between layers… The controller RNN is a two-layer LSTM with 35 hidden units on each layer. It is trained with the ADAM optimizer with a learning rate of 0.0006.

Each child model is trained for 50 epochs, with the reward function set to the validation accuracy of the last five epochs, cubed. After exploring 12,800 architectures, the best performing architecture is then run to convergence. “As can be seen from the table, Neural Architecture Search can design several promising architectures that perform as well as some of the best models on this dataset.

The learned “Neural Architecture Search v1” network from the above table looks like this:

### Experiments with Penn Treebank

The controller RNN predicts a combination method and an activation function for each node in the tree. Training is done with 400 networks being trained across 400 CPUs at any one point in time. Parameter updates to the parameter server are made once 10 gradients have been accumulated from replicas. Each child model is trained for 35 epochs.

After the controller RNN is done training, we take the best RNN cell according to the lowest validation perplexity and then run a grid search over learning rate, weight initialization, dropout rates, and decay epoch. The best cell found was then run with three different configurations and sizes to increase its capacity.

The models found outperform other state-of-the-art models on this dataset. “Not only is our cell better, the model that achieves 64 perplexity is also more than two times faster because the previous best network requires running a cell 10 times per time step.”

The newly discovered cell is visualized [below]. The visualization reveals that the new cell has many similarities to the LSTM cell in the first few steps, suchas it likes to compute $W-1 \times h_{t-1} + W_2 \times x_t$ several times and send them to different components in the cell.

### OK, but is it really better than random search

Checking performance against random search is an important sanity check. The best model found using the policy gradient approach in this paper is better than the best model found using random search, and the average of the top n models for several values of n is also found to be better.

1. May 10, 2017 7:30 am

It worth mentioning that resource usage is enormous – https://news.ycombinator.com/item?id=13440758

• May 10, 2017 7:55 am

Yes indeed! I do call that out in the fourth paragraph – somewhere around 15,000x more expensive!!!

2. May 12, 2017 12:22 am

Great write up, as always! Glad you mentioned the potential 15000x cost increase!

The idea sounds *so* cool, but I worry that some models tend to perform initially good but top out fast, while other models take more iterations to train but achieve higher maximum validation accuracy. –> That means that for your controller to be able to evaluate each child’s R (accuracy) value, the child will need to have been (I mean, ideally…) quite fully trained (e.g. the 50 epochs they used). This issue is a problem for human researchers too, but the resulting cost effect isn’t so huge.

When dealing with models that train of millions of observations, the sheer amount of \$ to do something like this using AWS sounds prohibitive (unless you’re, like, Google). 15000x is so high when x = 20% of a team’s budget :O.

May 28, 2017 3:50 am

We did some work on using BO for deep structure optimizxation. Take a look at this paper:

Ramachandram, D., Lisicki, M., Shields, T., Amer, M. and Taylor, G.W., “Structure optimization for deep multimodal fusion networks using graph-induced kernels”, Proc. of 25th European Symposium on Artificial Neural Networks, Computational Intelligence and Machine Learning (ESANN 2017), Apr 26-28, Bruges, Belgium.

4. July 7, 2017 9:41 pm

Questions:
1. What is the input to the Controller RNN at each time-step?
2. What is the embedding that is passed between layers, mentioned in the presentation(http://rll.berkeley.edu/deeprlcourse/docs/quoc_barret.pdf) on slide 7?


text:
# Electronic – How does a NAND gate work? (Very basic question)

circuit analysislogic-gates

I'll preface this question by saying that I am a software developer just starting to learn the basics of electronics, so it's very likely I'm missing some fundamental intuition here.

Below is a mechanical NAND gate with two switches. I think it's supposed to be obvious that when the switches are closed, the output Q is 0 rather than 1. I don't see why this is.

I see that when the two switches are closed, there is a path from V+ to ground, and that current will flow to ground. But there's also a path from V+ to Q, so won't some current still flow to the output, putting it in a 1 state?

The intuition I'm using (which may be totally wrong) is this:

• Current acts like water gushing from V+ down all available paths.
• At a junction, current will flow through both paths in an amount inversely proportional to resistance. In this case, both paths have no additional resistance so they should split the current equally.
• The boolean equivalent of a 1 is that current is flowing through a point.

Please help me understand what I'm missing! And if you can point me to a book or online resource explaining these fundamentals, that would be very helpful. I've tried looking at a lot of "circuit tutorial" content on Google, but surprisingly haven't been able to resolve my confusion here.

format: plain


text:
## Algebra 1: Common Core (15th Edition)

$S=13\frac{1}{3} mph$
$T=\frac{k}{S}$ where T is time and S is speed. (Calculate for k) $2=\frac{k}{10}$ (Multiply both sides by 10) k=20 (Plug k back into the original equation) $1.5=\frac{20}{S}$ (Multiply each side by S) $1.5S=20$ (Divide each side by 1.5) $S=13\frac{1}{3}$


text:
# perl file function

This topic is 1780 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

## Recommended Posts

my ($bumpFileVolume,$bumpFileDir,$name) = File::Spec->splitpath($bumpFile);
my @workDirArr = ($bumpFileVolume,$bumpFileDir);
my $workDir = File::Spec->catdir(@workDirArr); chdir$workDir or die "$0 failed to chdir to working dir$workDir";

system ("sort -k 1,1 -k 4n -T $workDir$name >tempLoc_$name")==0 or die "$0 failed to sort $name"; open (BRK, "tempLoc_$name") or die "$0 failed to open file tempLoc_$name";
open (OUTTWO, ">loc_analyze_$name") or die "$0 failed to open file loc_analyze_$name";  I'm a little confused as to whats happening here. What does it mean to create the variable$name attach it to the file I assume is $bumpfile and then use in as the part of loc_analyze_$name? Are they creating a new file or simply opening up an old one?

##### Share on other sites

Documentation says:

Splits a path in to volume, directory, and filename portions. On systems with no concept of volume, returns '' for volume.

1. ($volume,$directories,$file) = File::Spec->splitpath($path );
2. ($volume,$directories,$file) = File::Spec->splitpath($path, $no_file ); For systems with no syntax differentiating filenames from directories, assumes that the last file is a path unless$no_file is true or a
trailing separator or /. or /.. is present. On Unix, this means that $no_file true makes this return ( '',$path, '' ).

The directory portion may or may not be returned with a trailing '/'.

The results can be passed to catpath() to get back a path equivalent to (usually identical to) the original path.

So splitpath returns a tuple and the third element of the tuple is just the filename, as opposed to the entire file path. Presumably bumpFile contains the full path of the file not just a filename. They're basically just trying to change the working directory and to work no matter what was stored in bumpfile (i.e. an entire path, a file, a relative file path, etc). The code will work if you pass in "../../twizzlers.txt" or "./twizzlers.txt" and maybe just "twizzlers.txt".

The system command creates a new file which is based on just the filename from bumpFile. So if bumpFile contains "../../twizzlers.txt" then the system command creates the file tempLoc_twizzlers.txt in the same folder that twizzlers.txt exists in.

Then the perl script opens the already existing tempLoc_twizzlers.txt file (I *think* for read-only purposes seems to be the default when not specified) and then it opens the file loc_analyzer_twizzlers.txt for writing.


text:
Clearly I missed an entire week. I need to build a better system to make this easier…

Random notes.

• Kicked out NFS from the Tool Labs proxies (with 1). Yay! This hopefully explains the lockup of tools-proxy-01 yesterday night, maybe? It’s been restarted since, and I hope to no longer have instances randomly locoking on me. Infrastructure standards of 2009, here we come! :D I’ve also removed NFS from tools-redis, and migrated them to Jessie as well.
• Fixed up all the races in how kubernetes workers are setup with 2
• Another instance is ‘stuck’ again. Sigh. AAAAAAAAAAAAAAAAAAAAAAAAA. Paravoid helped debug this, tracking it down to NFS client issues in the 4.2 kernel (See phab). I moved k8s nodes back to a working 3.19 kernel (after filing issue about the other 3.19 kernel package I tried that didn’t work).
• Moved the tools proxies to 4.2 (lol?) after finding out huge ksoftirqd spikes in them. Let’s see if that improves things
• I split up the individual components of PAWS, and have a working nbserve in there now! Exciting times. Need to fixup nbserve to use traitlets for config
• Big Tool Labs outage (again!). Some tool accidentally sent about 12million job requests and crashed gridengine’s underlying backing store (BerkeleyDB). Reset to a clean slate after many hours (Thanks Coren!) and mostly things are back up now. I’m reading through the Berkeley DB reference manual now.
• Persistance failed for ores’s redises again, mostly because vm_overcommit was turned off. Fixed in the core redis module so it does not happen again.


text:
# Rigorous definition of a limit

1. Aug 19, 2010

### Noesis

These words have been pulled directly from Wikipedia, although I find the exact logical construction in my textbooks:

---
The (ε, δ)-definition of the limit of a function is as follows:

Let ƒ be a function defined on an open interval containing c (except possibly at c) and let L be a real number. Then the formula:

$$\lim_{x \to c} f(x)=L$$

means for each real ε > 0 there exists a real δ > 0 such that for all x with 0 < |x − c| < δ, we have |ƒ(x) − L| < ε.
---

My problem is that this seems to be an insufficient definition. A corresponding δ can be found for every positive value of ε even if δ is increasing as ε is decreasing. The inequalities can be satisfied for any limit L.

Say f(x) = 5x, and we claim the limit as x->3 is 20.

For every positive ε in |5x − 20| < ε, I can find a corresponding 0 < |x − 3| < δ, although in this case x will go to 4 in order to satisfy small ε.

My question is: should an added clause exist such that as ε tends to 0 so must δ, or that the product of their derivatives with respect to x must be greater than or equal to zero (so they both increase or decrease simultaneously), or is it implicitly assumed that one is choosing x closer to c. If it is the last case, it seems it would be more precise to explicitly mention this fact, as then there can only be one L.

I understand this question might be borderline, or full-line, pedantic, but I think we all understand the necessity for precision in mathematics and logic, and I'm concerned as to whether I am in fact missing a subtle nuance--say a subtle nuance that would indeed make the limit L unique despite what originally seems insufficient constraints.

2. Aug 19, 2010

### Noesis

I believe I've discovered the subtle nuance.

The inequality: 0 < |x − c| < δ does not admit the difference to be equal to zero, hence there is not a corresponding δ in my example for x = 3.

So it seems that the given logical construction is adequate.

If anyone can validate these thoughts and perhaps provide further insight or extensions, that would be awesome.

3. Aug 19, 2010

### Staff: Mentor

No, this won't work. Suppose ε = .1 is given, so I want 5x to be within .1 of 20.

|5x - 20| < .1 ==> 5|x - 4| < .1 ==> |x - 4| < .02
What does that tell me? It says that x is within .02 of 4, or that 3.98 < x < 4.02. That's not very close to 3.

If I take smaller values for ε, it turns out that x will be even closer to 4, hence farther away from 3. This suggests to me that
$$\lim_{x \to 3} 5x \neq 20$$.

In other words, if x is arbitrarily close to 3 (i.e., small δ), then 5x is NOT arbitrarily close to 20 (small ε).

As I'm sure you know,
$$\lim_{x \to 3} 5x = 15$$.

This is easy to prove. Let ε > 0 be given.

|5x - 15| < ε ==> 5|x - 3| < ε ==> |x - 3| < ε/5
Let δ = ε/5

So for any ε that is given, we can find a positive number δ, so that if x is within δ units of 3, then f(x) = 5x will be within ε units of 15.

4. Aug 20, 2010

### JThompson

We don't need to assume anything about the behavior of δ based upon that of ε.
Given an ε for |f(x)-L|<ε, can we find a δ>0 where -δ < x-c < δ?

|5x-20| < 2
-2 < 5x-20 < 2
.6 < x-3 < 1.4

In other words the x-interval where |5x-20| < 2 is always true is 3.6 < x < 4.4.
Can you find a δ such that 3.6 ≤ -δ+3 < x < δ+3 ≤ 4.4?

On the one hand 3.6 ≤ -δ+3,so δ ≤ -.6. But we' re looking for positive δ.
On the other hand δ+3 ≤4.4,so δ ≤1.4.We must have 3.6 ≤ -δ+3,but 3.6 > 1.6.In fact for any 0 <δ ≤ 1.4, 1.6 ≤ -δ+3 < 3.

There is no such δ,so lim(x→3) 5x ≠ 20. The definition says "for every number ε>0", it does not matter how close to zero.

If ε=.0000001, the x-interval is .99999998 < x-3 <1.00000002, and we cannot find δ to satisfy .999999998 ≤ -δ < x-3 < δ ≤ 1.00000002 either.

5. Nov 25, 2010

### Noesis

Thanks for the input. I was missing the line of: such that for all x with in the original definition and was only trying to find ordered pairs of epsilon-delta, which was why I thought their definition was insufficient.

That was an interesting way of looking at it JThompson.

6. Nov 25, 2010

### HallsofIvy

Note that if f(x) is a constant, say f(x)= C for all x, then $\displaytype\lim_{x\to c} f(x)= C$ for all c and by shown by observing that $|f(x)- C|= 0< \epsilon$ no matter what $\delta$ is. It is NOT necessary that "an added clause exist such that as ε tends to 0 so must δ".


text:
### MikeMirzayanov's blog

By MikeMirzayanov, 21 month(s) ago, translation, ,

ACM-ICPC World Finals 2017 will begin on May 24, 2017 at 15:00 (UTC). This event is the main event of the year in the world of sports programming!

This year ICPC Regional participation included 46,381 of the finest students and faculty in computing disciplines from 2,948 universities in 103 countries on six continents. A record 50,145 students and 5,073 coaches competed in ICPC and ICPC-assisted competitions this year, setting new records in participation.

Codeforces wishes the teams to show a vivid and interesting contest contest. We wish to find beautiful solutions, write without bugs and enjoy many accepted problems!

ACM ICPC World Finals 2017 English Broadcast:
ACM ICPC World Finals 2017 Indian Broadcast:
ACM ICPC World Finals 2017 Chinese Broadcast:
ACM ICPC World Finals 2017 Arabic Broadcast:
Broadcast from legends: Petr, tourist, Endagorion:

•
• +292
•

 » 21 month(s) ago, # |   +184 Is it rated?
•  » » 21 month(s) ago, # ^ | ← Rev. 2 →   -96
 » 21 month(s) ago, # |   +10 Is there a live contest?
•  » » 21 month(s) ago, # ^ |   +76 No, this is a repeat. Tsinghua University win with 11 solved problems.
•  » » » 21 month(s) ago, # ^ |   +32 Unfortunately they couldn't solve 11 in the replay
 » 21 month(s) ago, # |   +31 Does anyone know a link to current results?
•  » » 21 month(s) ago, # ^ |   +36
•  » » » 21 month(s) ago, # ^ |   +26 Thank you. I've updated the post.
•  » » » » 21 month(s) ago, # ^ |   +34 You're welcome :D
•  » » 21 month(s) ago, # ^ |   +33
•  » » 21 month(s) ago, # ^ | ← Rev. 2 →   0 Does anyone have link for the complete final ranklist? I found this but it only contains number of problems the teams solved.
•  » » » 21 month(s) ago, # ^ |   +12 On myicpc.
 » 21 month(s) ago, # |   +5 Is there any mirror where we can solve? Or atleast view the problems?
•  » » 21 month(s) ago, # ^ |   +1 here it says they will add problems after contest starts, maybe 30 mins after the start?
 » 21 month(s) ago, # |   +5 Are there problem statements available?
•  » » 21 month(s) ago, # ^ | ← Rev. 2 →   +31
 » 21 month(s) ago, # |   +15 rng_58 and other Atcoder officer's broadcast: link
 » 21 month(s) ago, # |   0 What is the public contest link where the legends are submitting their solutions?
•  » » 21 month(s) ago, # ^ |   0 Well watching the stream right now they are not submitting their solutions because they can't, I think they are waiting for this link to become valid just like everybody else.
•  » » » 21 month(s) ago, # ^ |   0 Problems are up on the kattis link now!
•  » » » » 21 month(s) ago, # ^ |   0 thanks!
 » 21 month(s) ago, # |   +5 Problems are available here: https://icpc.kattis.com/problems
•  » » 21 month(s) ago, # ^ | ← Rev. 2 →   +1 Submissions enabled there too.
 » 21 month(s) ago, # |   +46 when will the final results be out?
 » 21 month(s) ago, # |   +16 How to solve Problem F, is it a dp problem?
•  » » 21 month(s) ago, # ^ |   +3 yes, dp problem.
 » 21 month(s) ago, # |   +11 How to solve C?
•  » » 21 month(s) ago, # ^ |   +3 bipartite matching
•  » » » 21 month(s) ago, # ^ |   0 How is it a bipartite matching problem? Can you please elaborate a little more :D
•  » » » » 21 month(s) ago, # ^ |   +6 First of all, you need to see that a value > 1 should be present in the final grid if and only if it is the max in a row / column else you can replace it with 1 and it will be still be a valid solution.So, for each value which is max in some row/column you get a subset of rows(nr) and columns(nc) in which it is maximum. Now you can have atmost nr + nc numver of those values to get a valid answer but if we can put a value at some of their intersection such that 1 value satisfies 2 maximum condition, we can get less number of positions with that value. That is where maximum matching comes into picture. Lets say r1, r2,... r_nr and c1,c2,c_nc are the rows and columns such that their maximum is same. So we take all nr * nc intersections that is A(r1,c1) , .... A(r_nr,c_nc) and whenever A(i,j) > 0 we make an edge b/w i and j. Now this is because we cannot convert a zero value to a non zero value. If we find the maximum matching in this graph, some rows and columns are matched. So if we put the current macimum at their intersection, then we can refuce the number of maximum by macimum matching value. So, we need nr+nc-max_matching number of positions with current value.Also, we need to keep in mind that, there may be some non-zero values unaccounted for in the values, we need to make those values = 1.
•  » » » » » 21 month(s) ago, # ^ |   +5 Thanks I got it AC :D
 » 21 month(s) ago, # |   +67 ITMO wins!
 » 21 month(s) ago, # |   +30 Can someone explain to me the what was going on with the ASCII art bird with Russian text that was spammed in the Twitch chat (especially near the ending of the ceremony)? Foreign memes are always interesting to learn about :D
•  » » 21 month(s) ago, # ^ | ← Rev. 2 →   +19 It's just spam hype copy-paste meme. Russian version of Le Toucan has arrived goose spam memLAUNCH ░GOOSE▄▀▀▀▄░COMRADES ▄███▀░◐░░░▌░░░░░░░ ░░░░▌░░░░░▐░░░░░░░ ░░░░▐░░░░░▐░░░░░░░ ░░░░▌░░░░░▐▄▄░░░░░ ░░░░▌░░░░▄▀▒▒▀▀▀▀▄ ░░░▐░░░░▐▒▒▒▒▒▒▒▒▀▀▄ ░░░▐░░░░▐▄▒▒▒▒▒▒▒▒▒▒▀▄ ░░░░▀▄░░░░▀▄▒▒▒▒▒▒▒▒▒▒▀▄ ░░░░░░▀▄▄▄▄▄█▄▄▄▄▄▄▄▄▄▄▄▀▄ ░░░░░░░░░░░▌▌░▌▌░░░░░ ░░░░░░░░░░░▌▌░▌▌░░░░░ ░░░░░░░░░▄▄▌▌▄▌▌░░░░░  goose-hydra spam mem░░░░░░▄▀▀▀▄░░░░░░░░ ▄███▀░◐░▄▀▀▀▄░░░░░░ ░░▄███▀░◐░░░░▌░░░ ░░░▌░▄▀▀▀▄░░░▌░░░░ ▄███▀░◐░░░▌░░▌░░░░ ░░░░▌░░░░░▐▄▄▌░░░░░ ░░░░▌░░░░░▐▄▄░░░░░ ░░░░▌░░░░▄▀▒▒▀▀▀▀▄ ░░░▐░░░░▐▒▒▒▒▒▒▒▒▀▀▄ ░░░▐░░░░▐▄▒▒▒▒▒▒▒▒▒▒▀▄ ░░░░▀▄░░░░▀▄▒▒▒▒▒▒▒▒▒▒▀▄ ░░░░░░▀▄▄▄▄▄█▄▄▄▄▄▄▄▄▄▄▄▀▄ ░░░░░░░░░░░▌▌░▌▌░░░░░ ░░░░░░░░░░░▌▌░▌▌░░░░░ ░░░░░░░░░▄▄▌▌▄▌▌░░░░░
 » 21 month(s) ago, # |   +283 I find it weird that announcing National Taiwan University as the first to solve J (submitted at 296) already implicitly revealed that Warsaw University failed to solve J (submitted at 294).
 » 21 month(s) ago, # | ← Rev. 2 →   +38 What's the trick in J?We get the upper bound of F, the upper bound of W, and the upper bound of vF + W (by running normal flow three times). I think I proved that these are also sufficient conditions (by maxflow = mincut), then it's easy to compute the maximum of Fa * W(1 - a). To construct the solution we need to run another flow once more. Do I miss something?
•  » » 21 month(s) ago, # ^ |   +53 Exactly like that. No trick :)
•  » » 21 month(s) ago, # ^ |   +17 I think these were few reasons of only 1 ACd solution: 1) scary objective function, might create an impression of requiring hard math 2) actual solving of problem <=> realizing what is a set of reachable flows (F, W) (rectangle with cut corner). If you start solving this problem it is not obvious that this works this way, but as soon as you realize this it really is easier than it seemed to be 3) medium problems were harder than usual (at least in my opinion), they took more time to solve them, so not much time was left for harder ones (or at least, harder looking ones :p)We got the right idea, but sadly apparently made some implementation bug along the way, got no time to debug
•  » » » 21 month(s) ago, # ^ |   +48 Yup, rng's solution was pretty much the intended one, and it's relatively straightforward (as flow problems go). I was personally rather surprised how few teams attempted J. To your reasons I would add 4) the usual contest groupthink: nobody solved it early, so everyone assumed it was hard. :)
•  » » 11 months ago, # ^ |   0 Yes, but how exactly do I reconstruct the flubber and water flow?
•  » » » 11 months ago, # ^ |   +2 Once you know how much flubber and water you need to send, you set the capacities from the super source to the flubber source and water source accordingly and construct a flow. Then you reduce the capacities of the edges to the value of this flow, and run flow once more, this time reducing the capacity of the edge (super-source, flubber source) to 0. This yields the water flow. Flubber can be found by substracting those two.
•  » » » » 11 months ago, # ^ |   0 yeah, but how to know the direction of flubber for those edges with no water flowing at all?
•  » » » » » 11 months ago, # ^ |   0 From the first flow. It tells you how much stuff (water+flubber) goes in which direction. In particular, on every directed edge it holdsfflubber(e) + fwater(e) = fwater + flubber(e)
•  » » » » » » 10 months ago, # ^ |   0 ACC, thanks!!
•  » » » » 9 months ago, # ^ |   -8 ACC, Thanks!!
 » 21 month(s) ago, # |   +24 I think this was a very good chance to stop Russian domination on ICPC with Warsaw and seoul at their peak :D . Seems they will continue their domination for a little upcoming years before current chinese 17 years old lengendary grandmasters focus on ->training on problemsets that consist in half of only ugly geometric problems and the rest somehow distributed between problems like "translate directly very chaotic statement into C++", some problems requiring backtracks filled with weird heuristics, some obvious problems requiring heavy library algorithms and one or at most two problems requiring some thinking Credits : swistakk
•  » » 21 month(s) ago, # ^ |   +39 Heh, I actually really liked this problemset, a lot of problems required really nice ideas, no library problems, just one geo problem that was on the easy side (however I personally would prefer more ;p). B falls into both reading complicated statement and backtracks with heuristics, but I heard it was not that painful (didn't read lol).
•  » » » 21 month(s) ago, # ^ |   0 This problemset contained some nice problems.(Of course I didn't solve all of these nice:v). I mean by nice something not belonging to the category above and you may see in an IOI or CF contest.At the same time, some of them were unfair I think and gave advantage to some teams. I believe problem A was discussed\encountered by a lot of experienced contestants as I saw some variations of it before (even I am not a geometry fan but I saw). Problem D I believe is pasting from library.
•  » » » » 21 month(s) ago, # ^ |   +3 Yeah, A was kinda a fail, I solved exactly the same problem 1-2 months ago from old Petrozavodsk camp. That helped me getting first solve on this one xD.I don't know why are you stating that D was pasting from library. It looked like it can be well known, but nobody from our team knew this. If you meant that main difficulty of D was writing D&C trick then I will definitely disagree (meaning that coming up with it was much harder). Inb4, if you ask then we don't have convex hull of hyperbolas in out library xD.
•  » » » » » 21 month(s) ago, # ^ |   +2 Regarding problem D, does this one look familiar?
•  » » » » » » 21 month(s) ago, # ^ |   +20 Yes, it does :). Funnily enough, mnbvnar gave me this problem few months ago and I couldn't solve it (he solved it, but I didn't learn solution), but today he hadn't got an idea and I came up with same weird trick with hyperbolas :pp. When I explained my solution to him he immediately recalled that problem and said it is basically same solution :p.
•  » » » » » » » 21 month(s) ago, # ^ | ← Rev. 3 →   +25 http://codeforces.com/gym/100886/problem/IA problem mentioned in a blog is not that big deal. I mean every problem has a probability to be found on the internet in some chinese papers.But I have seen the problem of pairs (a , b) and queries (x , y) and asking for max ax + by like three times. One of them is in this petrozavodsk camp [problem:http://codeforces.com/gym/100886/problem/I]and another variation in our region and another one in a chinese regional (I don't remember unfortunately). It's really unfair to pick problems just found that easy way. Even petrozavodsk version is slightly different, But I don't think it will make that big difference. (anyway my friend solved this back in the virtual and I am just too lazy to think of these stuff) :D Another thing that I came acrosshttp://codeforces.com/gym/101047/problem/FThis is from a 2015 regional and exactly the same problem (even harder) as ICPC 2016 problem L (If not mistaken , it was easy anyway but still). It's from a regional qualifying to 2016 and surprise , same problem.Like I have seen a lot of problems in ICPC that just requires a straight forward approach of something. Not a variation , the really straight one.2015 , 2016 was no difference.There are some things that I don't understand, Why problems in ICPC are different than stuff we see in IOI/POI/CF. I bet like most of teams in the contest spent their time sweating and debugging and arguing with each other. and nobody felt like he had fun solving the problems. Like POI problems for example or even CERC even are much more fun than ICPC problems and hard the same. Even though , you need simple stuff to solve the problem and so much creativity. It's just more fun than solving linear programming and a geometry problem that any code with less than 69 if statements is wa and still missing tests.I haven't solved a really hard problem of past ICPCs but most of (easy->medium) problems are just like this.
•  » » » » » » » » 21 month(s) ago, # ^ |   +8 Having creative challenges is nice, but the point of those Easy->Medium problems might be different. It's a problem solving contest after all, not a "hey I'm smarter!!" contest.
•  » » » » » » 21 month(s) ago, # ^ |   +10 Also, given the speed of some Japanese teams solving G, it was probably similar to some local contest. My utmost concern as a judge in an ACM regional was 'what if one of our problems exists elsewhere?'. I don't believe the judges knew about those problems, it's impossible to be sure that a problem never existed elsewhere.I think this keeps coming up every year. This is basically unavoidable given the thousands of existing contest problems.
•  » » » » » » » 21 month(s) ago, # ^ |   0 It's not about existence of a problem. 2 problems were "traditional" problems. I don't know if there was more. Same thing every year.The same situation of giving a maximum bipartite matching problem in a beginners qualifying contest in your university.
•  » » » » » » » 21 month(s) ago, # ^ |   +76 I'm Japanese but I've never seen similar problem to G. The only cause that Keio University took FA of G is this team contained me:DThe problem G seemed interesting and actually it was very interesting. I like others in this problem set too (except A). Thank you very much for problem setters! Also, thank you very much for all who supported this wonderful contest!
•  » » » » » » » » 21 month(s) ago, # ^ |   +20 Heh, it was kinda suspicious to see that first accepted solution to G came from a team whose first accepted submission was on that very problem (before E and I) and which places around ~120th spot :P. Such situations usually mean that they managed to get away with some naive heuristics and maybe our team was first one to "really solve" this problem, but on the other hand this problem didn't look like one that could be solved using approaches that are not fully correct, so I was a bit confused. When after contest I noted that Keio team has snuke everything became clear :).
•  » » » » » » » » » 21 month(s) ago, # ^ |   +10 Sorry to confuse you & congratulations for gold medal!
•  » » » » » » » » » 21 month(s) ago, # ^ |   +10 Haha, no need to be sorry :D. Thanks to you we started thinking about that problem pretty quickly instead of being stuck on D which turned out to be a good decision ;).
•  » » » » » » » » » 21 month(s) ago, # ^ |   0 snuke, what strategy did you use during WF? I am confused...
•  » » » » » » » » » 21 month(s) ago, # ^ |   +5 I guess he used strategy "Screw overall result, let's have some fun solving nice problems and maybe getting some cash for First To Solve's" ;p
•  » » » » » » » » » 21 month(s) ago, # ^ |   +15 Yes. We ignored time penalty and aimed to FA in problems of my favorite genre (graph theory or some kind of puzzles).The problems in the World Finals need much more thinking than Asia Regionals. The computer becomes vacant while I'm thinking because our team contains only one active competitive programmer. peryaudo was a blue coder but not so active now. So we are no match for the other teams at World Finals (especially in time penalty). This is the reason of my strategy.In the contest, I read J and G at first. I misread J and it seemed impossible one. (I thought v is given for each edge. Without misreading, I would try to solve J instead of B.) I read G next and thought of solution for some minutes and got FA. I tried to solve B next. The written rule seemed almost same as a board game "Cluedo" but solution was not so obvious. (the intended solution seems using pruning in brute force... all writers must read this blog. I'll post about my solution.) I thought of solution for few minutes and implemented/debugged for long time. However I could not get FA. Finally we switched to solve easier problems but I was too tired to solve more problems. In parallel, my teammate solved E,I by himself and F with my hint.As a result, we solved 4 problems and got WA/RE on B and C. To be honest, I think this result is lower than I expected. But I'm satisfied that we could complete our first goal "get FA" because I know it's difficult to perform perfectly in the crucial contest. Anyway the World Finals was very exciting. I wanna go next year too but I'm already not a student now(;_;) See you again at some contests!
 » 21 month(s) ago, # |   0 How to solve G?
•  » » 21 month(s) ago, # ^ | ← Rev. 2 →   0 This came partially from my own attempt at the problem and partially from listening to the solution on the livestream, so it might be corrupted, but I hope it's close enough and easy to follow.Firstly, a little mathy rant: we can treat the state of the 300*300 squares as a column matrix C of size 1*(300^2). Then the reproduction without errors is simply multiplying by some (mostly 0) matrix M over Z_2 (just take mod 2 after multiplication). Hence, we have some sort of homomorphism: if f() brings us to the next state, then we have f(a+b) = f(a) + f(b), where a and b are states.So now we can think of errors as toggling the state of 1 square, and hence 1 generation later, this will toggle the state of exactly 9 squares. This gives rise to a crucial observation that gives a trivial polynomial time solution: if a configuration has a possible previous state, then that state is unique.Justification: Let E() denote possibly a mutation of 1 square. Suppose on contrary that E(f(a))= E(f(b)). Then E(E(f(a) — f(b))) = E(E(f(a-b))) = 0 (possibly), but (proof omitted, but loosely speaking I think considering 'corners' can prove this) there is no nonempty state s such that f(s) has less than or equal to 2 cells.Furthermore, the bounding box of a figure increases by 2 in each dimension each iteration, so the question is just to find f^-1 of a state repeatedly, if it exists. Also, we need to do this at most 150 times, so this admits a trivial polynomial solution contingent on how fast we can find f^-1 of a state.Let A be the current state we are given. We want to find (if exists) B=f^-1(E(A)).It turns out we can easily check whether the top row of A contains a mutation: if there is no mutation, then we can recover the row from the top left corner onwards. Then, there is an error iff the top right hand corner has an invalid parity checker. Through a similar process, we may check the second row next and so on. Repeating for columns, we can find the row and column of the mutation, and once we know the location of the mutation, finding f^-1 is easy. (I'm rushing for time, maybe someone else can furnish a more coherent explanation for this part later?)Since this process takes O(N^2), we have overall algorithm time O(N^3) and we are done.
•  » » » 21 month(s) ago, # ^ |   0 I think you meant "Then, there is an error iff the top right hand corner has a invalid parity checker", or did I miss something?
•  » » » » 21 month(s) ago, # ^ |   0 Whoops. Fixed.
 » 21 month(s) ago, # | ← Rev. 2 →   +6 Final ranklist ?? https://icpc.baylor.edu/scoreboard/ is frozemEDIT : GOT IT !! https://icpc.baylor.edu/worldfinals/results
•  » » 21 month(s) ago, # ^ |   0 Thanks. How about scoreboard with time penalty?
•  » » » 21 month(s) ago, # ^ |   +10
 » 21 month(s) ago, # | ← Rev. 2 →   0 Could anyone tell me the solution to Problem E?Thanks! UPD：I was confused by the data range n<=1000 and now I got it.Please ignore.
•  » » 21 month(s) ago, # ^ |   0 Can you share your idea?
•  » » » 21 month(s) ago, # ^ |   0 Just do binary search on the answer,and you can pass in O(nlogn) time.
•  » » » » 21 month(s) ago, # ^ |   0 Actually I did it.But it got tle on some cases. code
•  » » » » » 21 month(s) ago, # ^ |   0 In binary search on doubles, limit the number of steps to say 100, cause there will be precision issues comparing doubles.
 » 21 month(s) ago, # |   -16 How to solve H?
 » 21 month(s) ago, # |   0 How to solve C?I tried moving the max in a row/column to cover a row and a column (simultaneously) if possible, but I get WA test 7.
•  » » 21 month(s) ago, # ^ |   +3 The only constraints are: Every 0 must stay a 0 Every nonzero must stay nonzero Every row must have its maximum somewhere Every column must have its maximum somewhere The first two are easy to satisfy by placing 0s and 1s. For 3 and 4, you want to satisfy both with the minimum amount of "placements" of values. You can save a value if you use it for both a row and a column. So try matching as many as you can!
•  » » » 21 month(s) ago, # ^ |   0 Thank you for the hint :)
 » 21 month(s) ago, # |   +83
•  » » 21 month(s) ago, # ^ |   +10 There are also video solutions on the ICPC News YouTube channel.https://www.youtube.com/user/ICPCNews/videos
 » 21 month(s) ago, # | ← Rev. 4 →   0 Nice contest, I solved one problem I have been struggling with for days.
 » 21 month(s) ago, # |   +8 Why sharif fut didn't participate?
•  » » 21 month(s) ago, # ^ |   +10 I guess visa issues.
•  » » » 21 month(s) ago, # ^ |   0 So why Tehran University participated?
•  » » » » 21 month(s) ago, # ^ |   +28 I have no idea, probably because they got visas :P. For every number in set {0, 1, 2, 3} there was at least one team that had that many participants because of visa issues. Sad, but true.
•  » » » » » 21 month(s) ago, # ^ |   +38 There were teams with 3 members because of visa issues? :P
 » 21 month(s) ago, # |   -22 Give me some of your's ACM world finals t-shirts
•  » » 21 month(s) ago, # ^ |   +8 How much can you afford to pay for it?
 » 21 month(s) ago, # |   +18 My solution for B (without pruning and its time complexity can be estimate easily):Brute force search for "which cards are removed" and "for each people/weapon card who has it". There are at most (6^2 * 9) * ((3^5)^2) ≒ 20,000,000 cases.Before fix the distribution of people/weapon, the clue '*' is ambiguous. After fix, the clue '*' can be regarded as "if the player has suggested people/weapon card, this clue is no more information, otherwise the player has suggested room card".Then for each pair of (player,card) can have one of three state "player has card", "player doesn't have card" or "player can have card". The distribution is possible if there exists an assignment for "can" state (to "has" or "doesn't"). The existence of assignment can be calculated by simple maxflow.TL was tight so it was needed to implement carefully. source code (3.37s on Kattis)
 » 21 month(s) ago, # |   -73 Thanks for sharing. Adobe Support Number UK
 » 21 month(s) ago, # |   +13 I'm wondering how teams solved problem A. The computations regarding whether lines cross the polygon boundaries need to be done exactly, which — I believe — requires the use of exact arithmetic. The input coordinates are given with 21 bits. I think that means that you can, for instance, compute intersection points (42 bits), but not for instance midpoints between intersection points (84 bits).What is the general technique for implementing these calculations exactly using only 64 bit integers?(PS: I have a "naive" AC solution that uses C++'s "__int128" type and computes midpoints — but I'm certain it's not necessary).
•  » » 20 months ago, # ^ |   0 I don't know why are you so afraid of (long) doubles here, they work well. General setting when doubles can be bad is when perturbing slightly can change answer a lot in a not continuous way (here for example "does this point lie on this line?"), but here all points involved in such questions have integer coordinates, so it is very unlikely doubles will give significant errors.
•  » » » 20 months ago, # ^ |   0 Can you explain this a little more?Are you saying that using long doubles (with a 64-bit mantissa) would allow you to compute the line between any two vertices exactly (using 42bits), and it would also allow you to determine exactly whether another polygon vertex lies on that line (using 42+21 = 63 bits?)? But that if the other polygon vertex does not lie on the line then you'll conclude it's either not touching or crossing a polygon boundary anyway? And if crosses, it'll only influence the distance you report as answer, so rounding error does not matter? You determine whether it crosses using the sign of the result of the incidence test?
•  » » » » 20 months ago, # ^ |   0 Are you familiar with concept of using epsilons in geometry tasks? Since non-integer computations show up all the time in geometry we need to operate on real numbers and we can't expect doubles to satisfy conditions like a==b even if they are really the same number. If you want to check that A, B, C lie on same line you can check whether CrossProd(A, B, C) =  = 0 if you have everything implemented on integers, but you can't do it like that if they have real coordinates and in such case we check whether abs(CrossProd(A, B, C)) < ε, where epsilon is chosen wisely, for example ε = 10 - 9. Here is my code for reference that gets accepted on Kattis: http://ideone.com/08pisZ
•  » » » » » 20 months ago, # ^ |   +53 wisely LOL
•  » » » » » 20 months ago, # ^ |   0 Thank you. I'll take a deeper look at your code.I note that the only place where you require the epsilon check in this problem is your ptOnSegment (due to the use of the sqrt() function.) If you remove the epsilon check from the other tests, your program will still pass. That said, this version of ptOnSegment was new to me, thank you.For fun, I tried my solution (which avoids division and sqrt) with double and long double, and __int128 — it passes with all three choices: http://ideone.com/zy3uG9 (and no epsilon).
•  » » » 20 months ago, # ^ | ← Rev. 2 →   +13 IMO, it's reasonable to be scared of using doubles on a question like this, despite the integral coordinates. You identified the main issue: that a candidate line could just barely work or not work depending on how close a polygon vertex gets to it. The problem is inherently unstable (that is, there are valid input cases for which permuting the vertices by a small epsilon leads to a large delta in the answer). Thus care is warranted.Unfortunately, it's not trivial to see what the worst-case epsilon is. With coordinates bounded by 10^6, how close can a lattice point get to a lattice line without lying on it? If I remember correctly, the actual answer is 7*10^-7, for the simple case of (1,1) and (0,0)-(10^6,10^6-1). But it's not obvious (to me, anyway) why another less-simple example couldn't come closer. EDIT: I guess Pick's Theorem is the way to prove it. :)So for this problem you need an epsilon on the order of 10^-7, for coordinates ranging up to 10^6. 13 decimal digits of precision are required, and doubles have 15, so they're good enough. But it's close. In a contest I'd still try to use integer arithmetic (well, doubles guaranteed to be integral) whenever possible.
•  » » » » 20 months ago, # ^ |   0 Actually it's quite easy to estimate how close can point be to a line. Let point A be really close to line BC. (B-A)x(C-A) is integer, so its abs is >=1. However |BC| is not larger than 3e6 and crossprod is base times height, so height is at least 3e-7.However that's rather irrelevant to why my code works. I do not test whether point lies on line by checking if it close to that line, I test it by checking if crossprod is 0, so for that part even epsilon=0.5 would work :). What requires doubles computations in my code is computing intersections of an arbitrary line (determined by two vertices of polygon) with sides and then checking whether that point lies on that segment. That can also be estimated properly, but epsilon 1e-9 sounds sufficiently fair enough for me here ;p.
•  » » » » » 20 months ago, # ^ |   0 I was answering your comment "I don't know why are you so afraid of (long) doubles here". I explained why someone could (and should) be afraid. :) Good for you; using integers for the intersection test is the best way to avoid any such issues.Ok, I was being dumb using Pick's Theorem. Your cross-product explanation is much simpler!
•  » » » » » » 20 months ago, # ^ | ← Rev. 6 →   0 My solution is based on integers, i only use double for comparing angles and storing intersection points. Solution#include using namespace std; typedef long double ld; #define PI ((ld)(3.14159267)) struct point { int64_t x, y; point() {} point(int64_t x, int64_t y): x(x), y(y) {} ld angle() { if (y < 0) return 2 * PI + atan2(y, x); return atan2(y, x); } bool operator == (point a) { return x == a.x && y == a.y; } }; point operator-(point a, point b) { return point(a.x - b.x, a.y - b.y); } point operator^(point a, point b) { return b - a; } point operator*(point a, point b) { return point(a.x * b.x - a.y * b.y, a.x * b.y + a.y * b.x); } int64_t dotP(point a, point b) { return (int64_t)a.x * (int64_t)b.x + (int64_t)a.y * (int64_t)b.y; } int64_t crossP(point a, point b) { return (int64_t)a.x * (int64_t)b.y - (int64_t)b.x * (int64_t)a.y; } bool inAngle(point b, point a1, point a2) { point fi = point(a1.x, -a1.y); point b1 = b * fi; point b2 = a2 * fi; return b1.angle() <= b2.angle(); } bool Crosses(point a1, point a2, point b1, point b2) { point x = a1; point y = b1; point a = a1 ^ a2; point b = b1 ^ b2; int64_t T = crossP(y - x, b); int64_t t = crossP(a, b); int64_t S = crossP(x - y, a); int64_t s = crossP(b, a); if (t < 0) { T *= -1; t *= -1; } if (s < 0) { S *= -1; s *= -1; } return ((0 < T && T < t) && (0 < S && S < s)); } bool CrossesRay(point a1, point a2, point b1, point b2) { point x = a1; point y = b1; point a = a1 ^ a2; point b = b1 ^ b2; int64_t T = crossP(y - x, b); int64_t t = crossP(a, b); int64_t S = crossP(x - y, a); int64_t s = crossP(b, a); if (t < 0) { T *= -1; t *= -1; } if (s < 0) { S *= -1; s *= -1; } if (t == 0 or s == 0) return false; return ((0 < T) && (0 < S && S < s)); } ld TT(point a1, point a2, point b1, point b2) { point x = a1; point y = b1; point a = a1 ^ a2; point b = b1 ^ b2; int64_t T = crossP(y - x, b); int64_t t = crossP(a, b); return (ld) T / (ld) t; } bool inLine(point i, point j, point k) { if (crossP(i ^ k, i ^ j) != 0) return false; if (i == j or j == k) return false; return ( (min(i.x, j.x) <= k.x && k.x <= max(i.x, j.x)) && (min(i.y, j.y) <= k.y && k.y <= max(i.y, j.y)) ); } bool inRay(point i, point j, point k) { return inLine(i, k, j); } int main() { int64_t N; cin >> N; point A[N + 2]; for (int64_t i = 1; i <= N; i++) cin >> A[i].x >> A[i].y; A[0] = A[N]; A[N + 1] = A[1]; ld answ = 0; for (int64_t i = 1; i <= N; i++) for (int64_t j = i + 1; j <= N; j++) { if (!inAngle(A[i]^A[j], A[i]^A[i + 1], A[i]^A[i - 1])) continue; if (!inAngle(A[j]^A[i], A[j]^A[j + 1], A[j]^A[j - 1])) continue; bool stop = false; for (int64_t k = 1; k <= N; k++) { if (Crosses(A[i], A[j], A[k], A[k - 1])) stop = true; if (inLine(A[i], A[j], A[k])) { if (!inAngle(A[k]^A[j], A[k]^A[k + 1], A[k]^A[k - 1])) stop = true; if (!inAngle(A[k]^A[i], A[k]^A[k + 1], A[k]^A[k - 1])) stop = true; } } if (stop) continue; vector X; vector Y; X.push_back(A[i].x); Y.push_back(A[i].y); X.push_back(A[j].x); Y.push_back(A[j].y); for (int Q = 0; Q < 2; Q++) { swap(i, j); if (!inAngle(A[i]^A[j], A[j]^A[j + 1], A[j]^A[j - 1])) continue; ld t = DBL_MAX; bool flag = false; for (int k = 1; k <= N; k++) { if (inRay(A[i], A[j], A[k])) { if (!( inAngle(A[i]^A[j], A[k]^A[k + 1], A[k]^A[k - 1]) && inAngle(A[j]^A[i], A[k]^A[k + 1], A[k]^A[k - 1]))) { flag = true; ld T = (ld) dotP(A[i] ^ A[j], A[i] ^ A[k]) / (ld) dotP(A[i] ^ A[j], A[i] ^ A[j]); t = min(t, T); } } if (CrossesRay(A[i], A[j], A[k], A[k + 1])) { flag = true; t = min(t, TT(A[i], A[j], A[k], A[k + 1])); } } if (flag) { X.push_back((ld) (A[i] ^ A[j]).x * (ld) t + (ld) A[i].x); Y.push_back((ld) (A[i] ^ A[j]).y * (ld) t + (ld) A[i].y); } } for (int i = 0; i < X.size(); i++) for (int j = i + 1; j < X.size(); j++) answ = max(answ, sqrtl(powl(X[i] - X[j], 2) + powl(Y[i] - Y[j], 2))); } cout << fixed << setprecision(15) << answ; }


text:
# The Balance Sheet

### The Accounting Equation

The accounting equation balances assets to the total of liabilities and equity.

The balance sheet is a snapshot of a company's financial condition at a point in time, traditionally at the end of a period. Two classes of information reveal the company's financial condition: (1) the company's assets and (2) the company's liabilities. An asset is an economic resource of value that a business owns and that is expected to provide future benefits. Assets may be tangible items, such as inventory, or they can be intangible items, such as intellectual property, owned by the company.

A company's debts are its liabilities. A liability is an obligation or amount owed to another individual or entity as a result of a past transaction. The portion of the assets belonging to shareholders is referred to as shareholders' equity. Shareholders' equity, sometimes also referred to as stockholders’ equity, is the value left to owners after debts and obligations have been accounted for, or the business's total assets minus its total liabilities. Accordingly, investors view shareholders' equity as their outstanding claim on the company.

The accounting equation is a company's assets equal to its liabilities plus the shareholders' equity.
${\text{Assets}}={\text{Liabilities}}+{\text{Shareholders' Equity}}$
The accounting equation demonstrates that a company's assets are financed by liabilities, shareholders' equity, or a blend of both. In practical terms, the accounting equation demonstrates two things. First, the total assets are the sum of what a company owns. Second, liabilities are contractual obligations to deliver cash or another financial asset to an entity while shareholders’ equity is the difference between total assets and total liabilities. It is also the share capital retained in the company in addition to the retained earnings minus the treasury shares.

### Components of the Balance Sheet

The balance sheet gives a snapshot of a company's assets and liabilities at a given point in time; it includes current assets, fixed assets, intangible assets such as goodwill, current and long-term liabilities, and shareholders' equity.
The balance sheet is a snapshot of a company's assets and liabilities at a given point in time. This information is revealed through the accounting equation.
${\text{Assets}}={\text{Liabilities}+\text{Shareholders' Equity}}$
The balance sheet begins with asset entries. These entries appear in descending order by liquidity. The company sorts its liquid assets into current assets and its illiquid assets into fixed assets. Current assets include a company's cash, short-term investments, and items of value that can be converted to cash within a year. For example, current assets include cash and cash equivalents, accounts receivable, and inventory.

The next item to appear on a company's balance sheet is its net fixed assets. A fixed asset is a tangible piece of property used in the normal course of business to generate revenue, such as property, plant, or equipment. After recording fixed assets, a company records its intangible assets. Intangible assets include intellectual property and goodwill. Goodwill is the premium paid over the market value of net assets (market value of identifiable assets minus the market value of identifiable liabilities) in an enterprise acquisition. The company totals all of these entries to calculate its total assets.

The company's liabilities, as either current or long term, will appear next on the balance sheet. Current liabilities are the amounts owed by a business to payees that are expected to be paid within one year or during the operating cycle, whichever is longer. For example, current liability entries might include short-term debt, accounts payable, or income taxes payable. Next, the company records its long-term debt and any other unaccounted-for debt. The company totals the liability entries to calculate its total liabilities.

The final item the company includes on the balance sheet is its shareholders' equity. A company calculates its shareholders' equity by subtracting its total liabilities from its total assets. Three categories represent shareholders' equity: preferred stock, common stock, and retained earnings.


text:
Identifiers
CAS number 56-65-5
PubChem 5957
ChemSpider 5742
UNII 8L70Q75FXE
DrugBank DB00171
KEGG C00002
ChEBI CHEBI:15422
ChEMBL CHEMBL14249
IUPHAR ligand 1713
Jmol-3D images Image 1
Image 2
Properties
Molecular formula C10H16N5O13P3
Molar mass 507.18 g mol−1
Density 1.04 g/cm3 (disodium salt)
Melting point 187 °C (369 °F; 460 K) disodium salt; decomposes
Acidity (pKa) 6.5
Except where noted otherwise, data are given for materials in their standard state (at 25 °C (77 °F), 100 kPa)
(verify) (what is: /?)
Infobox references

Adenosine triphosphate (ATP) is a nucleoside triphosphate used in cells as a coenzyme.

It is often called the "molecular unit of currency" of intracellular energy transfer.[1] ATP transports chemical energy within cells for metabolism. It is one of the end products of photophosphorylation, cellular respiration, and fermentation and used by enzymes and structural proteins in many cellular processes, including biosynthetic reactions, motility, and cell division.[2] One molecule of ATP contains three phosphate groups, and it is produced by a wide variety of enzymes, including ATP synthase, from adenosine diphosphate (ADP) or adenosine monophosphate (AMP) and various phosphate group donors. Substrate-level phosphorylation, oxidative phosphorylation in cellular respiration, and photophosphorylation in photosynthesis are three major mechanisms of ATP biosynthesis.

Metabolic processes that use ATP as an energy source convert it back into its precursors. ATP is therefore continuously recycled in organisms: the human body, which on average contains only 250 grams (8.8 oz) of ATP,[3] turns over its own body weight equivalent in ATP each day.[4]

ATP is used as a substrate in signal transduction pathways by kinases that phosphorylate proteins and lipids. It is also used by adenylate cyclase, which uses ATP to produce the second messenger molecule cyclic AMP. The ratio between ATP and AMP is used as a way for a cell to sense how much energy is available and control the metabolic pathways that produce and consume ATP.[5] Apart from its roles in signaling and energy metabolism, ATP is also incorporated into nucleic acids by polymerases in the process of transcription. ATP is the neurotransmitter believed to signal the sense of taste.[6]

The structure of this molecule consists of a purine base (adenine) attached to the 1' carbon atom of a pentose sugar (ribose). Three phosphate groups are attached at the 5' carbon atom of the pentose sugar. It is the addition and removal of these phosphate groups that inter-convert ATP, ADP and AMP. When ATP is used in DNA synthesis, the ribose sugar is first converted to deoxyribose by ribonucleotide reductase.

ATP was discovered in 1929 by Karl Lohmann, Fiske and Y. Subbarow of Harvard Medical School[7] but its correct structure was not determined until some years later.[citation needed] It was proposed to be the main energy transfer molecule in the cell by Fritz Albert Lipmann in 1941, that is, being the intermediary molecule between energy-yielding (exergonic) and energy-requiring (endergonic) reactions.[8] It was first artificially synthesized by Alexander Todd in 1948.[9]

## Physical and chemical properties

ATP consists of adenosine — composed of an adenine ring and a ribose sugar — and three phosphate groups (triphosphate). The phosphoryl groups, starting with the group closest to the ribose, are referred to as the alpha (α), beta (β), and gamma (γ) phosphates. Consequently, it is closely related to the adenosine nucleotide, a monomer of RNA. ATP is highly soluble in water and is quite stable in solutions between pH 6.8 and 7.4, but is rapidly hydrolysed at extreme pH. Consequently, ATP is best stored as an anhydrous salt.[10]

ATP is an unstable molecule in unbuffered water, in which it hydrolyses to ADP and phosphate. This is because the strength of the bonds between the phosphate groups in ATP is less than the strength of the hydrogen bonds (hydration bonds), between its products (ADP + phosphate), and water. Thus, if ATP and ADP are in chemical equilibrium in water, almost all of the ATP will eventually be converted to ADP. A system that is far from equilibrium contains Gibbs free energy, and is capable of doing work. Living cells maintain the ratio of ATP to ADP at a point ten orders of magnitude from equilibrium, with ATP concentrations fivefold higher than the concentration of ADP. This displacement from equilibrium means that the hydrolysis of ATP in the cell releases a large amount of free energy.[11]

Two phosphoanhydride bonds (those that connect adjacent phosphates) in an ATP molecule are responsible for the high energy content of this molecule.[12] In the context of biochemical reactions, these anhydride bonds are frequently—and sometimes controversially—referred to as high-energy bonds (despite the fact it takes energy to break bonds).[13] Energy stored in ATP may be released upon hydrolysis of the anhydride bonds.[12] The primary phosphate group on the ATP molecule that is hydrolyzed when energy is needed to drive anabolic reactions is the γ-phosphate group. Located the farthest from the ribose sugar, it has a higher energy of hydrolysis than either the α- or β-phosphate. The bonds formed after hydrolysis—or the phosphorylation of a residue by ATP—are lower in energy than the phosphoanhydride bonds of ATP. During enzyme-catalyzed hydrolysis of ATP or phosphorylation by ATP, the available free energy can be harnessed by a living system to do work.[14][15]

Any unstable system of potentially reactive molecules could potentially serve as a way of storing free energy, if the cell maintained their concentration far from the equilibrium point of the reaction.[11] However, as is the case with most polymeric biomolecules, the breakdown of RNA, DNA, and ATP into simpler monomers is driven by both energy-release and entropy-increase considerations, in both standard concentrations, and also those concentrations encountered within the cell.

The standard amount of energy released from hydrolysis of ATP can be calculated from the changes in energy under non-natural (standard) conditions, then correcting to biological concentrations. The net change in heat energy (enthalpy) at standard temperature and pressure of the decomposition of ATP into hydrated ADP and hydrated inorganic phosphate is −20.5 kJ/mol, with a change in free energy of 3.4 kJ/mol.[16] The energy released by cleaving either a phosphate (Pi) or pyrophosphate (PPi) unit from ATP at standard state of 1 M are:[17]

ATP + H
2
O
→ ADP + Pi   ΔG˚ = −30.5 kJ/mol (−7.3 kcal/mol)
ATP + H
2
O
→ AMP + PPi   ΔG˚ = −45.6 kJ/mol (−10.9 kcal/mol)

These values can be used to calculate the change in energy under physiological conditions and the cellular ATP/ADP ratio. However, a more representative value (which takes AMP into consideration) called the Energy charge is increasingly being employed. The values given for the Gibbs free energy for this reaction are dependent on a number of factors, including overall ionic strength and the presence of alkaline earth metal ions such as Mg2+
and Ca2+
. Under typical cellular conditions, ΔG is approximately −57 kJ/mol (−14 kcal/mol).[18]

### Ionization in biological systems

ATP (adenosine triphosphate) has multiple groups with different acid dissociation constants. In neutral solution, ATP is ionized exists mostly as ATP4−, with a small proportion of ATP3−.[19] As ATP has several negatively charged groups in neutral solution, it can chelate metals with very high affinity. The binding constant for various metal ions are (given as per mole) as Mg2+
(9 554), Na+
(13), Ca2+
(3 722), K+
(8), Sr2+
(1 381) and Li+
(25).[20] Due to the strength of these interactions, ATP exists in the cell mostly in a complex with Mg2+
.[19][21]

## Biosynthesis

The ATP concentration inside the cell is typically 1–10 mM.[22] ATP can be produced by redox reactions using simple and complex sugars (carbohydrates) or lipids as an energy source. For complex fuels to be synthesized into ATP, they first need to be broken down into smaller, more simple molecules. Carbohydrates are hydrolysed into simple sugars, such as glucose and fructose. Fats (triglycerides) are metabolised to give fatty acids and glycerol.

The overall process of oxidizing glucose to carbon dioxide is known as cellular respiration and can produce about 30 molecules of ATP from a single molecule of glucose.[23] ATP can be produced by a number of distinct cellular processes; the three main pathways used to generate energy in eukaryotic organisms are glycolysis and the citric acid cycle/oxidative phosphorylation, both components of cellular respiration; and beta-oxidation. The majority of this ATP production by a non-photosynthetic aerobic eukaryote takes place in the mitochondria, which can make up nearly 25% of the total volume of a typical cell.[24]

### Glycolysis

Main article: glycolysis

In glycolysis, glucose and glycerol are metabolized to pyruvate via the glycolytic pathway. In most organisms, this process occurs in the cytosol, but, in some protozoa such as the kinetoplastids, this is carried out in a specialized organelle called the glycosome.[25] Glycolysis generates a net two molecules of ATP through substrate phosphorylation catalyzed by two enzymes: PGK and pyruvate kinase. Two molecules of NADH are also produced, which can be oxidized via the electron transport chain and result in the generation of additional ATP by ATP synthase. The pyruvate generated as an end-product of glycolysis is a substrate for the Krebs Cycle.[26]

### Glucose

In the mitochondrion, pyruvate is oxidized by the pyruvate dehydrogenase complex to Acetyl group, which is fully oxidized to carbon dioxide by the citric acid cycle (also known as the Krebs Cycle). Every "turn" of the citric acid cycle produces two molecules of carbon dioxide, one molecule of the ATP equivalent guanosine triphosphate (GTP) through substrate-level phosphorylation catalyzed by succinyl-CoA synthetase, three molecules of the reduced coenzyme NADH, and one molecule of the reduced coenzyme FADH2. Both of these latter molecules are recycled to their oxidized states (NAD+ and FAD, respectively) via the electron transport chain, which generates additional ATP by oxidative phosphorylation. The oxidation of an NADH molecule results in the synthesis of 2–3 ATP molecules, and the oxidation of one FADH2 yields between 1–2 ATP molecules.[23] The majority of cellular ATP is generated by this process. Although the citric acid cycle itself does not involve molecular oxygen, it is an obligately aerobic process because O
2
is needed to recycle the reduced NADH and FADH2 to their oxidized states. In the absence of oxygen the citric acid cycle will cease to function due to the lack of available NAD+ and FAD.[24]

The generation of ATP by the mitochondrion from cytosolic NADH relies on the malate-aspartate shuttle (and to a lesser extent, the glycerol-phosphate shuttle) because the inner mitochondrial membrane is impermeable to NADH and NAD+. Instead of transferring the generated NADH, a malate dehydrogenase enzyme converts oxaloacetate to malate, which is translocated to the mitochondrial matrix. Another malate dehydrogenase-catalyzed reaction occurs in the opposite direction, producing oxaloacetate and NADH from the newly transported malate and the mitochondrion's interior store of NAD+. A transaminase converts the oxaloacetate to aspartate for transport back across the membrane and into the intermembrane space.[24]

In oxidative phosphorylation, the passage of electrons from NADH and FADH2 through the electron transport chain powers the pumping of protons out of the mitochondrial matrix and into the intermembrane space. This creates a proton motive force that is the net effect of a pH gradient and an electric potential gradient across the inner mitochondrial membrane. Flow of protons down this potential gradient — that is, from the intermembrane space to the matrix — provides the driving force for ATP synthesis by ATP synthase. This enzyme contains a rotor subunit that physically rotates relative to the static portions of the protein during ATP synthesis.[27]

Most of the ATP synthesized in the mitochondria will be used for cellular processes in the cytosol; thus it must be exported from its site of synthesis in the mitochondrial matrix. The inner membrane contains an antiporter, the ADP/ATP translocase, which is an integral membrane protein used to exchange newly synthesized ATP in the matrix for ADP in the intermembrane space.[28] This translocase is driven by the membrane potential, as it results in the movement of about 4 negative charges out of the mitochondrial membrane in exchange for 3 negative charges moved inside. However, it is also necessary to transport phosphate into the mitochondrion; the phosphate carrier moves a proton in with each phosphate, partially dissipating the proton gradient.

### Beta oxidation

Main article: beta-oxidation

Fatty acids can also be broken down to acetyl-CoA by beta-oxidation. Each round of this cycle reduces the length of the acyl chain by two carbon atoms and produces one NADH and one FADH2 molecule, which are used to generate ATP by oxidative phosphorylation. Because NADH and FADH2 are energy-rich molecules, dozens of ATP molecules can be generated by the beta-oxidation of a single long acyl chain. The high energy yield of this process and the compact storage of fat explain why it is the most dense source of dietary calories.[29]

### Fermentation

Fermentation entails the generation of energy via the process of substrate-level phosphorylation in the absence of a respiratory electron transport chain. In most eukaryotes, glucose is used as both an energy store and an electron donor. The equation for the oxidation of glucose to lactic acid is:

C
6
H
12
O
6
$\to$ 2CH
3
CH(OH)COOH
+ 2 ATP

### Anaerobic respiration

Main article: anaerobic respiration

Anaerobic respiration is the process of respiration using an electron acceptor other than O
2
. In prokaryotes, multiple electron acceptors can be used in anaerobic respiration. These include nitrate, sulfate or carbon dioxide. These processes lead to the ecologically important processes of denitrification, sulfate reduction and acetogenesis, respectively.[30][31]

### ATP replenishment by nucleoside diphosphate kinases

ATP can also be synthesized through several so-called "replenishment" reactions catalyzed by the enzyme families of nucleoside diphosphate kinases (NDKs), which use other nucleoside triphosphates as a high-energy phosphate donor, and the ATP:guanido-phosphotransferase family,

### ATP production during photosynthesis

In plants, ATP is synthesized in thylakoid membrane of the chloroplast during the light-dependent reactions of photosynthesis in a process called photophosphorylation. Here, light energy is used to pump protons across the chloroplast membrane. This produces a proton-motive force and this drives the ATP synthase, exactly as in oxidative phosphorylation.[32] Some of the ATP produced in the chloroplasts is consumed in the Calvin cycle, which produces triose sugars.

### ATP recycling

The total quantity of ATP in the human body is about 0.2 mole. The majority of ATP is not usually synthesised de novo, but is generated from ADP by the aforementioned processes. Thus, at any given time, the total amount of ATP + ADP remains fairly constant.

The energy used by human cells requires the hydrolysis of 100 to 150 moles of ATP daily, which is around 50 to 75 kg. A human will typically use up his or her body weight of ATP over the course of the day.[33] This means that each ATP molecule is recycled 500 to 750 times during a single day (100 / 0.2 = 500). ATP cannot be stored, hence its consumption closely follows its synthesis. However a total of around 5g of ATP is used by cell processes at any time in the body.

## Regulation of biosynthesis

ATP production in an aerobic eukaryotic cell is tightly regulated by allosteric mechanisms, by feedback effects, and by the substrate concentration dependence of individual enzymes within the glycolysis and oxidative phosphorylation pathways. Key control points occur in enzymatic reactions that are so energetically favorable that they are effectively irreversible under physiological conditions.

In glycolysis, hexokinase is directly inhibited by its product, glucose-6-phosphate, and pyruvate kinase is inhibited by ATP itself. The main control point for the glycolytic pathway is phosphofructokinase (PFK), which is allosterically inhibited by high concentrations of ATP and activated by high concentrations of AMP. The inhibition of PFK by ATP is unusual, since ATP is also a substrate in the reaction catalyzed by PFK; the biologically active form of the enzyme is a tetramer that exists in two possible conformations, only one of which binds the second substrate fructose-6-phosphate (F6P). The protein has two binding sites for ATP — the active site is accessible in either protein conformation, but ATP binding to the inhibitor site stabilizes the conformation that binds F6P poorly.[26] A number of other small molecules can compensate for the ATP-induced shift in equilibrium conformation and reactivate PFK, including cyclic AMP, ammonium ions, inorganic phosphate, and fructose 1,6 and 2,6 biphosphate.[26]

The citric acid cycle is regulated mainly by the availability of key substrates, particularly the ratio of NAD+ to NADH and the concentrations of calcium, inorganic phosphate, ATP, ADP, and AMP. Citrate — the molecule that gives its name to the cycle — is a feedback inhibitor of citrate synthase and also inhibits PFK, providing a direct link between the regulation of the citric acid cycle and glycolysis.[26]

In oxidative phosphorylation, the key control point is the reaction catalyzed by cytochrome c oxidase, which is regulated by the availability of its substrate—the reduced form of cytochrome c. The amount of reduced cytochrome c available is directly related to the amounts of other substrates:

$\frac{1}{2}\mathrm{NADH} + \mathrm{cyt~c_{ox}} + \mathrm{ADP} + P_i \iff \frac{1}{2}\mathrm{NAD^{+}} + \mathrm{cyt~c_{red}} + \mathrm{ATP}$

which directly implies this equation:

$\frac{\mathrm{cyt~c_{red}}}{\mathrm{cyt~c_{ox}}} = \left(\frac{[\mathrm{NADH}]}{[\mathrm{NAD}]^{+}}\right)^{\frac{1}{2}}\left(\frac{[\mathrm{ADP}] [P_i]}{[\mathrm{ATP}]}\right)K_{eq}$

Thus, a high ratio of [NADH] to [NAD+] or a low ratio of [ADP] [Pi] to [ATP] imply a high amount of reduced cytochrome c and a high level of cytochrome c oxidase activity.[26] An additional level of regulation is introduced by the transport rates of ATP and NADH between the mitochondrial matrix and the cytoplasm.[28]

## Functions in cells

### Metabolism, synthesis, and active transport

ATP is consumed in the cell by energy-requiring (endothermic) processes and can be generated by energy-releasing (exothermic) processes. In this way ATP transfers energy between spatially separate metabolic reactions. ATP is the main energy source for the majority of cellular functions. This includes the synthesis of macromolecules, including DNA and RNA (see below), and proteins. ATP also plays a critical role in the transport of macromolecules across cell membranes, e.g. exocytosis and endocytosis.

### Roles in cell structure and locomotion

ATP is critically involved in maintaining cell structure by facilitating assembly and disassembly of elements of the cytoskeleton. In a related process, ATP is required for the shortening of actin and myosin filament crossbridges required for muscle contraction. This latter process is one of the main energy requirements of animals and is essential for locomotion and respiration.

### Cell signalling

#### Extracellular signalling

ATP is also a signalling molecule. ATP, ADP, or adenosine are recognised by purinergic receptors. Purinoreceptors might be the most abundant receptors in mammalian tissues.[34]

In humans, this signalling role is important in both the central and peripheral nervous system.[35] Activity-dependent release of ATP from synapses, axons and glia activates purinergic membrane receptors known as P2.[36] The P2Y receptors are metabotropic, i.e. G protein-coupled and modulate mainly intracellular calcium and sometimes cyclic AMP levels. Though named between P2Y1 and P2Y15, only nine members of the P2Y family have been cloned, and some are only related through weak homology and several (P2Y5, P2Y7, P2Y9, P2Y10) do not function as receptors that raise cytosolic calcium. The P2X ionotropic receptor subgroup comprises seven members (P2X1–P2X7), which are ligand-gated Ca2+
-permeable ion channels that open when bound to an extracellular purine nucleotide. In contrast to P2 receptors (agonist order ATP > ADP > AMP > ADO), purinergic nucleoside triphosphates like ATP are not strong agonists of P1 receptors, which are strongly activated by adenosine and other nucleosides (ADO > AMP > ADP > ATP). P1 receptors have A1, A2a, A2b, and A3 subtypes ("A" as a remnant of old nomenclature of adenosine receptor), all of which are G protein-coupled receptors, A1 and A3 being coupled to Gi, and A2a and A2b being coupled to Gs.[37] All adenosine receptors were shown to activate at least one subfamily of mitogen-activated protein kinases. The actions of adenosine are often antagonistic or synergistic to the actions of ATP. In the CNS, adenosine has multiple functions, such as modulation of neural development, neuron and glial signalling and the control of innate and adaptive immune systems.[34]

#### Intracellular signaling

ATP is critical in signal transduction processes. It is used by kinases as the source of phosphate groups in their phosphate transfer reactions. Kinase activity on substrates such as proteins or membrane lipids are a common form of signal transduction. Phosphorylation of a protein by a kinase can activate this cascade such as the mitogen-activated protein kinase cascade.[38]

ATP is also used by adenylate cyclase and is transformed to the second messenger molecule cyclic AMP, which is involved in triggering calcium signals by the release of calcium from intracellular stores.[39] This form of signal transduction is particularly important in brain function, although it is involved in the regulation of a multitude of other cellular processes.[40]

### DNA and RNA synthesis

In all known organisms, the Deoxyribonucleotides that make up DNA are synthesized by the action of ribonucleotide reductase (RNR) enzymes on their corresponding ribonucleotides.[41] These enzymes reduce the sugar residue from ribose to deoxyribose by removing oxygen from the 2' hydroxyl group; the substrates are ribonucleoside diphosphates and the products deoxyribonucleoside diphosphates (the latter are denoted dADP, dCDP, dGDP, and dUDP respectively.) All ribonucleotide reductase enzymes use a common sulfhydryl radical mechanism reliant on reactive cysteine residues that oxidize to form disulfide bonds in the course of the reaction.[41] RNR enzymes are recycled by reaction with thioredoxin or glutaredoxin.[26]

The regulation of RNR and related enzymes maintains a balance of dNTPs relative to each other and relative to NTPs in the cell. Very low dNTP concentration inhibits DNA synthesis and DNA repair and is lethal to the cell, while an abnormal ratio of dNTPs is mutagenic due to the increased likelihood of the DNA polymerase incorporating the wrong dNTP during DNA synthesis.[26] Regulation of or differential specificity of RNR has been proposed as a mechanism for alterations in the relative sizes of intracellular dNTP pools under cellular stress such as hypoxia.[42]

In the synthesis of the nucleic acid RNA, adenosine derived from ATP is one of the four nucleotides incorporated directly into RNA molecules by RNA polymerases. The energy driving this polymerization comes from cleaving off a pyrophosphate (two phosphate groups).[43] The process is similar in DNA biosynthesis, except that ATP is reduced to the deoxyribonucleotide dATP, before incorporation into DNA.

## Amino acid activation in protein synthesis

Main article: Amino acid activation

Aminoacyl-tRNA synthetase enzymes utilise ATP as an energy source to attach a tRNA molecule to its specific amino acid, forming an aminoacyl-tRNA complex, ready for translation at ribosomes. The energy is made available by ATP hydrolysis to adenosine monophosphate (AMP) as two phosphate groups are removed.[44]

## Binding to proteins

Some proteins that bind ATP do so in a characteristic protein fold known as the Rossmann fold, which is a general nucleotide-binding structural domain that can also bind the coenzyme NAD.[45] The most common ATP-binding proteins, known as kinases, share a small number of common folds; the protein kinases, the largest kinase superfamily, all share common structural features specialized for ATP binding and phosphate transfer.[46]

ATP in complexes with proteins, in general, requires the presence of a divalent cation, almost always magnesium, which binds to the ATP phosphate groups. The presence of magnesium greatly decreases the dissociation constant of ATP from its protein binding partner without affecting the ability of the enzyme to catalyze its reaction once the ATP has bound.[47] The presence of magnesium ions can serve as a mechanism for kinase regulation.[48]

An example of the Rossmann fold, a structural domain of a decarboxylase enzyme from the bacterium Staphylococcus epidermidis (PDB ID 1G5Q) with a bound flavin mononucleotide cofactor.

## ATP analogues

Biochemistry laboratories often use in vitro studies to explore ATP-dependent molecular processes. Enzyme inhibitors of ATP-dependent enzymes such as kinases are needed to examine the binding sites and transition states involved in ATP-dependent reactions. ATP analogs are also used in X-ray crystallography to determine a protein structure in complex with ATP, often together with other substrates. Most useful ATP analogs cannot be hydrolyzed as ATP would be; instead they trap the enzyme in a structure closely related to the ATP-bound state. Adenosine 5'-(gamma-thiotriphosphate) is an extremely common ATP analog in which one of the gamma-phosphate oxygens is replaced by a sulfur atom; this molecule is hydrolyzed at a dramatically slower rate than ATP itself and functions as an inhibitor of ATP-dependent processes. In crystallographic studies, hydrolysis transition states are modeled by the bound vanadate ion. However, caution is warranted in interpreting the results of experiments using ATP analogs, since some enzymes can hydrolyze them at appreciable rates at high concentration.[49]

## References

1. ^ Knowles JR (1980). "Enzyme-catalyzed phosphoryl transfer reactions". Annu. Rev. Biochem. 49: 877–919. doi:10.1146/annurev.bi.49.070180.004305. PMID 6250450.
2. ^ Campbell, Neil A.; Brad Williamson; Robin J. Heyden (2006). Biology: Exploring Life. Boston, Massachusetts: Pearson Prentice Hall. ISBN 0-13-250882-6.
3. ^ "'Nature's Batteries' May Have Helped Power Early Lifeforms". Science Daily. May 25, 2010. Archived from the original on 27 May 2010. Retrieved 2010-05-26. "At any one time, the human body contains just 250g of ATP — this provides roughly the same amount of energy as a single AA battery. This ATP store is being constantly used and regenerated in cells via a process known as respiration, which is driven by natural catalysts called enzymes."
4. ^ Törnroth-Horsefield S, Neutze R (December 2008). "Opening and closing the metabolite gate". Proc. Natl. Acad. Sci. U.S.A. 105 (50): 19565–6. doi:10.1073/pnas.0810654106. PMC 2604989. PMID 19073922.
5. ^ Hardie DG, Hawley SA (December 2001). "AMP-activated protein kinase: the energy charge hypothesis revisited". BioEssays 23 (12): 1112–9. doi:10.1002/bies.10009. PMID 11746230.
6. ^ Tim Jacob. "Taste(gustation)". Retrieved July 14, 2012.
7. ^ Lohmann K (August 1929). "Über die Pyrophosphatfraktion im Muskel". Naturwissenschaften (in German) 17 (31): 624–5. doi:10.1007/BF01506215.
8. ^ Lipmann F (1941). Adv. Enzymol. 1: 99–162. ISSN 0196-7398.
9. ^ "History: ATP first discovered in 1929". The Nobel Prize in Chemistry 1997. Nobel Foundation. Retrieved 2010-05-26.
10. ^ Stecher, P. G., ed. (1968). The Merck Index: an encyclopedia of chemicals and drugs 8th edition. Merck and Co. Ltd.
11. ^ a b Ferguson, S. J.; Nicholls, David; Ferguson, Stuart (2002). Bioenergetics 3 (3rd ed.). San Diego: Academic. ISBN 0-12-518121-3.
12. ^ a b JM Berg, JL Tymoczko, L Stryer (2003). Biochemistry. New York: WH Freeman. p. 376. ISBN 0-7167-4684-0.
13. ^ Chance, B.; Lees, H.; Postgate, J. G. (1972). "The Meaning of "Reversed Electron Flow" and "High Energy Electron" in Biochemistry". Nature 238 (5363): 330–1. doi:10.1038/238330a0. PMID 4561837.
14. ^ Koolman, J.; K. H. Roehm (2005). Color Atlas of Biochemistry. Stuttgart, Germany: Georg Thieme Verlag. p. 122. ISBN 3-13-100372-3.
15. ^ John Daintith, ed. (2004). Oxford Dictionary of Chemistry. Oxford, England: Oxford University Press. p. 435. ISBN 0-19-860918-3.
16. ^ Gajewski E, Steckler D, Goldberg R (1986). "Thermodynamics of the hydrolysis of adenosine 5'-triphosphate to adenosine 5'-diphosphate" (PDF). J Biol Chem 261 (27): 12733–7. PMID 3528161.
17. ^ Berg, Jeremy M.; Tymoczko, John L.; Stryer, Lubert (2007). Biochemistry (6th ed.). New York: W. H. Freeman. p. 413. ISBN 0-7167-8724-5.
18. ^ Stryer, Lubert (2002). Biochemistry (5th ed.). New York: W.H. Freeman and Company. ISBN 0-7167-1843-X.
19. ^ a b Storer A, Cornish-Bowden A (1976). "Concentration of MgATP2− and other ions in solution. Calculation of the true concentrations of species present in mixtures of associating ions". Biochem J 159 (1): 1–5. PMC 1164030. PMID 11772.
20. ^ Wilson J, Chin A (1991). "Chelation of divalent cations by ATP, studied by titration calorimetry". Anal Biochem 193 (1): 16–9. doi:10.1016/0003-2697(91)90036-S. PMID 1645933.
21. ^ Garfinkel L, Altschuld R, Garfinkel D (1986). "Magnesium in cardiac energy metabolism". J Mol Cell Cardiol 18 (10): 1003–13. doi:10.1016/S0022-2828(86)80289-9. PMID 3537318.
22. ^ Beis I.; Newsholme E. A. (October 1, 1975). "The contents of adenine nucleotides, phosphagens and some glycolytic intermediates in resting muscles from vertebrates and invertebrates". Biochem J 152 (1): 23–32. PMC 1172435. PMID 1212224.
23. ^ a b Rich PR (2003). "The molecular machinery of Keilin's respiratory chain". Biochem. Soc. Trans. 31 (Pt 6): 1095–105. doi:10.1042/BST0311095. PMID 14641005.
24. ^ a b c Lodish H Berk A, Matsudaira P, Kaiser CA, Krieger M, Scott MP, Zipursky SL, Darnell J. (2004). Molecular Cell Biology (5th ed.). New York: WH Freeman. ISBN 978-0-7167-4366-8.
25. ^ Parsons M (2004). "Glycosomes: parasites and the divergence of peroxisomal purpose". Mol Microbiol 53 (3): 717–24. doi:10.1111/j.1365-2958.2004.04203.x. PMID 15255886.
26. Voet D, Voet JG. (2004). Biochemistry 1 (3rd ed.). Hoboken, NJ.: Wiley. ISBN 978-0-471-19350-0.
27. ^ Abrahams J, Leslie A, Lutter R, Walker J (1994). "Structure at 2.8 Å resolution of F1-ATPase from bovine heart mitochondria". Nature 370 (6491): 621–8. doi:10.1038/370621a0. PMID 8065448.
28. ^ a b Dahout-Gonzalez C, Nury H, Trézéguet V, Lauquin G, Pebay-Peyroula E, Brandolin G (2006). "Molecular, functional, and pathological aspects of the mitochondrial ADP/ATP carrier". Physiology (Bethesda) 21 (4): 242–9. doi:10.1152/physiol.00005.2006. PMID 16868313.
29. ^ Ronnett G, Kim E, Landree L, Tu Y (2005). "Fatty acid metabolism as a target for obesity treatment". Physiol Behav 85 (1): 25–35. doi:10.1016/j.physbeh.2005.04.014. PMID 15878185.
30. ^ Zumft W (1 December 1997). "Cell biology and molecular basis of denitrification". Microbiol Mol Biol Rev 61 (4): 533–616. PMC 232623. PMID 9409151.
31. ^ Drake H, Daniel S, Küsel K, Matthies C, Kuhner C, Braus-Stromeyer S (1997). "Acetogenic bacteria: what are the in situ consequences of their diverse metabolic versatilities?". BioFactors 6 (1): 13–24. doi:10.1002/biof.5520060103. PMID 9233536.
32. ^ Allen J (2002). "Photosynthesis of ATP-electrons, proton pumps, rotors, and poise". Cell 110 (3): 273–6. doi:10.1016/S0092-8674(02)00870-X. PMID 12176312.
33. ^ Di Carlo, S. E. and Collins, H. L. (June 1, 2001). "Submitting illuminations for review". Advan. Physiol. Edu. 25 (2): 70–1.
34. ^ a b Abbracchio MP, Burnstock G, Verkhratsky A, Zimmermann H (January 2009). "Purinergic signalling in the nervous system: an overview". Trends Neurosci. 32 (1): 19–29. doi:10.1016/j.tins.2008.10.001. PMID 19008000.
35. ^ Chris Byrnes (January 5, 2012). "Treating Small Fiber Neuropathy Symptoms With ATP". Working toward Wellness. Retrieved January 6, 2014.
36. ^ Fields, R. D.; Burnstock, G. (2006). "Purinergic signalling in neuron-glia interactions". Nature Reviews Neuroscience 7 (6): 423–36. doi:10.1038/nrn1928. PMC 2062484. PMID 16715052.
37. ^ Fredholm, BB; Abbracchio, MP; Burnstock, G; Daly, JW; Harden, TK; Jacobson, KA; Leff, P; Williams, M (June 1, 1994). "Nomenclature and classification of purinoceptors". Pharmacol Rev 46 (2): 143–156. PMID 7938164.
38. ^ Mishra N, Tuteja R, Tuteja N (2006). "Signaling through MAP kinase networks in plants". Arch Biochem Biophys 452 (1): 55–68. doi:10.1016/j.abb.2006.05.001. PMID 16806044.
39. ^ Kamenetsky M, Middelhaufe S, Bank E, Levin L, Buck J, Steegborn C (2006). "Molecular details of cAMP generation in mammalian cells: a tale of two systems". J Mol Biol 362 (4): 623–39. doi:10.1016/j.jmb.2006.07.045. PMC 3662476. PMID 16934836.
40. ^ Hanoune J, Defer N (2001). "Regulation and role of adenylyl cyclase isoforms". Annu Rev Pharmacol Toxicol 41: 145–74. doi:10.1146/annurev.pharmtox.41.1.145. PMID 11264454.
41. ^ a b Stubbe J (5 April 1990). "Ribonucleotide reductases: amazing and confusing". J Biol Chem 265 (10): 5329–32. PMID 2180924.
42. ^ Chimploy K, Tassotto M, Mathews C (2000). "Ribonucleotide reductase, a possible agent in deoxyribonucleotide pool asymmetries induced by hypoxia". J Biol Chem 275 (50): 39267–71. doi:10.1074/jbc.M006233200. PMID 11006282.
43. ^ Joyce CM, Steitz TA (1995). "Polymerase structures and function: variations on a theme?". J. Bacteriol. 177 (22): 6321–9. PMC 177480. PMID 7592405.
44. ^ Eldra P. Solomon, Linda R. Berg, Diana W. Martin. Biology (8th Ed). ISBN 978-0-495-30978-9
45. ^ Rao S, Rossmann M (1973). "Comparison of super-secondary structures in proteins". J Mol Biol 76 (2): 241–56. doi:10.1016/0022-2836(73)90388-4. PMID 4737475.
46. ^ Scheeff E, Bourne P (2005). "Structural evolution of the protein kinase-like superfamily". PLoS Comput Biol 1 (5): e49. doi:10.1371/journal.pcbi.0010049. PMC 1261164. PMID 16244704.
47. ^ Saylor P, Wang C, Hirai T, Adams J (1998). "A second magnesium ion is critical for ATP binding in the kinase domain of the oncoprotein v-Fps". Biochemistry 37 (36): 12624–30. doi:10.1021/bi9812672. PMID 9730835.
48. ^ Lin X, Ayrapetov M, Sun G (2005). "Characterization of the interactions between the active site of a protein tyrosine kinase and a divalent metal activator". BMC Biochem 6: 25. doi:10.1186/1471-2091-6-25. PMC 1316873. PMID 16305747.
49. ^ Resetar AM, Chalovich JM (1995). "Adenosine 5'-(gamma-thiotriphosphate): an ATP analog that should be used with caution in muscle contraction studies". Biochemistry 34 (49): 16039–45. doi:10.1021/bi00049a018. PMID 8519760.


text:
sortmerna command not working
0
0
Entering edit mode
6.0 years ago

Dear All I need some help. I am getting an error in running sortmerna tool. I have successfully indexed the reference rRNA database. command used for indexing db

./indexdb_rna --ref ./rRNA_databases/silva-euk-28s-id98.fasta,./index/silva-euk-28s-db -v it made 4 files in the index folder named silva-euk-28s-db.bursttrie_0.dat
silva-euk-28s-db.kmer_0.dat
silva-euk-28s-db.pos_0.dat
silva-euk-28s-db.stats

Next step is to filter RNA-seq reads from rRNA indexed database command used for this was

./sortmerna --ref '/home/laptop/Desktop/NGS_tools/sortmerna-2.1/rRNA_databases','/home/laptop/Desktop/NGS_tools/sortmerna-2.1/index' --reads '/home/laptop/Desktop/RNA-seq/subdir1/output.fastq' --aligned sortmeout --fastx --other RNAsortme --log

this is resulting in following error

ERROR: The index '/home/laptop/Desktop/NGS_tools/sortmerna-2.1/index.stats' does not exist. Make sure you have constructed your index using the command indexdb'. Seeindexdb -h' for help.

RNA-Seq sortmerna NGS Bioinformatics • 4.7k views
1
Entering edit mode

I don't know the tool, but having glimpsed at the manual, should you not define a fasta file as a reference to the sortmerna tool (instead of just some folder like in your command)? Likewise, it looks to me like you're not defining the location of the index file correctly (also in error message). Shouldn't it be:

./sortmerna --ref /home/laptop/Desktop/NGS_tools/sortmerna-2.1/rRNA_databases/silva-euk-28s-id98.fasta,/home/laptop/Desktop/NGS_tools/sortmerna-2.1/index/silva-euk-28s-db --reads ..etc

0
Entering edit mode

Thank you @5heikki It solved my problem. Regards.


text:
# What is the differential Value-at-Risk?

I am currently working on a Machine Learning Project, implementing portfolio optimization algorithms according to different risk measures. I have found sufficient information on Sharpe Ratio optimisation, but not on Value-at-Risk.

My question is: What is the equation for differential VaR - the derivative taken with respect to a first-order exponential moving average decay rate?

It should be comparable to the differential Sharpe Ratio proposed by Moody & Safell. This formula was already discussed in: What’s the derivative of the sharpe ratio for one asset? Trying to optimize on it for a model

• Looking for something like this? $\frac{d \mathrm{VaR}_q\left(Y+\lambda X\right)}{d\lambda}=E\left[X|Y+\lambda X=\mathrm{VaR}_q\left(Y+\lambda X\right)\right]$ Jun 16 '20 at 18:01
• Yes, thank you! I also found additional information I needed.
– Nick
Jun 16 '20 at 23:18


text:
i need help trying to open an .exe file then opening a file in said exe program i.e i wanna open a file in flash after opening flash.

so far i can open the exe file with no problem but from there I'm stuck.

this is what i have

import os
os.system("flash.exe")

Flash can take command-line arguments. So you can do os.system("flash.exe myFileToOpen.fla") . That'll open Flash and have it open the document "myFileToOpen.fla".

If the FLA is in a different directory however, you'll need to give the path in front of the filename in the command line argument. It …

## All 4 Replies

Flash can take command-line arguments. So you can do os.system("flash.exe myFileToOpen.fla") . That'll open Flash and have it open the document "myFileToOpen.fla".

If the FLA is in a different directory however, you'll need to give the path in front of the filename in the command line argument. It can be relative or absolute. And if it contains spaces, you'll need to wrap it in quotes.

# absolute path and with quotes because of spaces
os.system("flash.exe 'C:\the\directory\to my file\here.fla'")
# or for relative, using just the .. syntax
os.system("flash.exe ../doc.fla")

i tried that and am getting can not open file. and i wanna be able to run a jsfl file after that

i figured it out thanks so much

Just for my confirmation, try this if it works:

import subprocess

subprocess.call(["flash.exe",the location of the file])
Be a part of the DaniWeb community

We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts learning and sharing knowledge.